:

## Carpet of Baron Munchausen

Maple

I accidentally stumbled on this problem in the list of tasks for mathematical olympiads. I quote its text in Russian-English translation:

"The floor in the drawing room of Baron Munchausen is paved with the identical square stone plates.
Baron claims that his new carpet (made of one piece of a material ) covers exactly 24 plates and
at the same time each vertical and each horizontal row of plates in the living room contains
exactly 4 plates covered with carpet. Is not the Baron deceiving?"

At first glance this seems impossible, but in fact the Baron is right. Several examples can be obtained simply by hand, for example or The problem is to find all solutions. This post is dedicated to this problem.

We put in correspondence to each such carpet a matrix of zeros and ones, such that in each row and in each column there are exactly 2 zeros and 4 ones. The problem to generate all such the matrices was already discussed here and Carl found a very effective solution. I propose another solution (based on the method of branches and boundaries), it is less effective, but more universal. I've used this method several times, for example here and here.
There will be a lot of such matrices (total 67950), so we will impose natural limitations. We require that the carpet be a simply connected set that has as its boundary a simple polygon (non-self-intersecting).

Below we give a complete solution to the problem.

restart;
R:=combinat:-permute([0,0,1,1,1,1]);
# All lists of two zeros and four units

# In the procedure OneStep, the matrices are presented as lists of lists. The procedure adds one row to each matrix so that in each column there are no more than 2 zeros and not more than 4 ones

OneStep:=proc(L::listlist)
local m, k, l, r, a, L1;
m:=nops(L); k:=0;
for l in L do
for r in R do
a:=[op(l),r];
if `and`(seq(add(a[..,j])<=4, j=1..6)) and `and`(seq(m-add(a[..,j])<=2, j=1..6)) then k:=k+1; L1[k]:=a fi;
od; od;
convert(L1, list);
end proc:

# M is a list of all matrices, each of which has exactly 2 zeros and 4 units in each row and column

L:=map(t->[t], R):
M:=(OneStep@@5)(L):
nops(M);

67950

M1:=map(Matrix, M):

# From the list of M1 we delete those matrices that contain <1,0;0,1> and <0,1;1,0> submatrices. This means that the boundaries of the corresponding carpets will be simple non-self-intersecting curves

k:=0:
for m in M1 do
s:=1;
for i from 2 to 6 do
for j from 2 to 6 do
if (m[i,j]=0 and m[i-1,j-1]=0 and m[i,j-1]=1 and m[i-1,j]=1) or (m[i,j]=1 and m[i-1,j-1]=1 and m[i,j-1]=0 and m[i-1,j]=0) then s:=0; break fi;
od: if s=0 then break fi; od:
if s=1 then k:=k+1; M2[k]:=m fi;
od:
M2:=convert(M2, list):
nops(M2);

394

# We find the list T of all segments from which the boundary consists

T:='T':
n:=0:
for m in M2 do
k:=0: S:='S':
for i from 1 to 6 do
for j from 1 to 6 do
if m[i,j]=1 then
if j=1 or (j>1 and m[i,j-1]=0) then k:=k+1; S[k]:={[j-1/2,7-i-1/2],[j-1/2,7-i+1/2]} fi;
if i=1 or (i>1 and m[i-1,j]=0) then k:=k+1; S[k]:={[j-1/2,7-i+1/2],[j+1/2,7-i+1/2]} fi;
if j=6 or (j<6 and m[i,j+1]=0) then k:=k+1; S[k]:={[j+1/2,7-i+1/2],[j+1/2,7-i-1/2]} fi;
if i=6 or (i<6 and m[i+1,j]=0) then k:=k+1; S[k]:={[j+1/2,7-i-1/2],[j-1/2,7-i-1/2]} fi;
fi;
od: od:
n:=n+1; T[n]:=[m,convert(S,set)];
od:
T:=convert(T, list):

# Choose carpets with a connected border

C:='C': k:=0:
for t in T do
a:=t; v:=op~(a);
G:=GraphTheory:-Graph([\$1..nops(v)], subs([seq(v[i]=i,i=1..nops(v))],a));
if GraphTheory:-IsConnected(G) then k:=k+1; C[k]:=t fi;
od:
C:=convert(C,list):
nops(C);

208

# Sort the list of border segments so that they go one by one and form a polygon

k:=0: P:='P':
for c in C do
a:=c: v:=op~(a);
G1:=GraphTheory:-Graph([\$1..nops(v)], subs([seq(v[i]=i,i=1..nops(v))],a));
GraphTheory:-IsEulerian(G1,'U');
U; s:=[op(U)];
k:=k+1; P[k]:=[seq(v[i],i=s[1..-2])];
od:
P:=convert(P, list):

# We apply AreIsometric procedure from here to remove solutions that coincide under a rotation or reflection

P1:=[ListTools:-Categorize( AreIsometric, P)]:
nops(P1);

28

We get 28 unique solutions to this problem.

Visualization of all these solutions:

interface(rtablesize=100):
E1:=seq(plottools:-line([1/2,i],[13/2,i], color=red),i=1/2..13/2,1):
E2:=seq(plottools:-line([i,1/2],[i,13/2], color=red),i=1/2..13/2,1):
F:=plottools:-polygon([[1/2,1/2],[1/2,13/2],[13/2,13/2],[13/2,1/2]], color=yellow):
plots:-display(Matrix(4,7,[seq(plots:-display(plottools:-polygon(p,color=red),F, E1,E2), p=[seq(i,i=P1)])]), scaling=constrained, axes=none, size=[800,700]); Carpet1.mw

The code was edited. ﻿