Kitonum

21123 Reputation

26 Badges

16 years, 211 days

MaplePrimes Activity


These are Posts that have been published by Kitonum

 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[1]); 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[2]; 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[2]: 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[1],i=P1)])]), scaling=constrained, axes=none, size=[800,700]);

 

 

Carpet1.mw

The code was edited.

 

 

This post is the answer to this question.

The procedure named  IntOverDomain  finds a double integral over an arbitrary domain bounded by a non-selfintersecting piecewise smooth curve. The code of the procedure uses the well-known Green's theorem.

Each section in the border should be specified by a list in the following formats :    
1. If a section is given parametrically, then  [[f(t), g(t)], t=t1..t2]    
2. If several consecutive sections of the border or the entire border is a broken line, then it is sufficient to set vertices of this broken line  [ [x1,y1], [x2,y2], .., [xn,yn] ] (for the entire border should be  [xn,yn]=[x1,y1] ).

Required parameters of the procedure:  f  is an expression in variables  x  and  y , L  is the list of all the sections. The sublists of the list  L  must follow in the positive direction (counterclockwise).

The code of the procedure:

restart;
IntOverDomain := proc(f, L) 
local n, i, j, m, yk, yb, xk, xb, Q, p, P, var;
n:=nops(L);
Q:=int(f,x);  
for i from 1 to n do 
if type(L[i], listlist(algebraic)) then
m:=nops(L[i]);
for j from 1 to m-1 do
yk:=L[i,j+1,2]-L[i,j,2]; yb:=L[i,j,2];
xk:=L[i,j+1,1]-L[i,j,1]; xb:=L[i,j,1];
p[j]:=int(eval(Q*yk,[y=yk*t+yb,x=xk*t+xb]),t=0..1);
od;
P[i]:=add(p[j],j=1..m-1) else
var := lhs(L[i, 2]);
P[i]:=int(eval(Q*diff(L[i,1,2],var),[x=L[i,1,1],y=L[i,1,2]]),L[i,2]) fi;
od; 
add(P[i], i = 1 .. n); 
end proc:

 

Examples of use.

1. In the first example, we integrate over a quadrilateral:

with(plottools): with(plots):
f:=x^2+y^2:
display(polygon([[0,0],[3,0],[0,3],[1,1]], color="LightBlue"));  
# Visualization of the domain of integration
IntOverDomain(x^2+y^2, [[[0,0],[3,0],[0,3],[1,1],[0,0]]]);  # The value of integral

 

2. In the second example, some sections of the boundary of the domain are curved lines:

display(inequal({{y<=sqrt(x),y>=sin(Pi*x/3)/2,y<=3-x}, {y>=-2*x+3,y>=sqrt(x),y<=3-x}}, x=0..3,y=0..3, color="LightGreen", nolines), plot([[t,sqrt(t),t=0..1],[t,-2*t+3,t=0..1],[t,3-t,t=0..3],[t,sin(Pi*t/3)/2,t=0..3]], color=black, thickness=2));
f:=x^2+y^2: L:=[[[t,sin(Pi*t/3)/2],t=0..3],[[3,0],[0,3],[1,1]], [[t,sqrt(t)],t=1..0]]:
IntOverDomain(f, L);

 

3. If  f=1  then the procedure returns the area of the domain:

IntOverDomain(1, L);  # The area of the above domain
evalf(%);

 

IntOverDomain.mw

Edit.

In the creation of this animation the technique from here  was used.

 

                    

 

The code of this animation:

with(plots): with(plottools):
SmallHeart:=plot([1/20*sin(t)^3, 1/20*(13*cos(t)/16-5*cos(2*t)/16-2*cos(3*t)/16-cos(4*t)/16), t = 0 .. 2*Pi], color = "Red", thickness=3, filled):
F:=t->[sin(t)^3, 13*cos(t)/16-5*cos(2*t)/16-2*cos(3*t)/16-cos(4*t)/16]:
Gf:=display(translate(SmallHeart, 0,0.37)):
Gl:=display(translate(SmallHeart, 0,-1)):
G:=t->display(translate(SmallHeart, F(t)[])):
A:=display(seq(display(op([Gf,seq(G(-Pi/20*t), t=3..k),seq(G(Pi/20*t), t=3..k)]))$4,k=2..17),display(op([Gf,seq(G(-Pi/20*t), t=3..17),seq(G(Pi/20*t), t=3..17),Gl]))$30, insequence=true, size=[600,600]):
B:=animate(textplot,[[-0.6,0.25, "Happy"[1..round(n)]],color="Orange", font=[times,bolditalic,40], align=right],n=0..5,frames=18, paraminfo=false):
C:=animate(textplot,[[-0.2,0, "Valentine's"[1..round(n)]],color=green, font=[times,bolditalic,40], align=right],n=1..11,frames=35, paraminfo=false):
E:=animate(textplot,[[-0.3,-0.25, "Day!"[1..round(n)]],color="Blue", font=[times,bolditalic,40], align=right],n=1..4,frames=41, paraminfo=false):
T:=display([B, display(op([1,-1,1],B),C), display(op([1,-1,1],B),op([1,-1,1],C),E)], insequence=true):
K:=display(A, T, axes=none):
K;


The last frame of this animation:

display(op([1,-1],K), size=[600,600], axes=none);  # The last frame

                          

 

ValentinelDay.mw
 

Edit. The code was edited - the number of frames has been increased.

Suppose we have some simple animations. Our goal - to build a more complex animation, combining the original animations in different ways.
We show how to do it on the example of the three animations. The technique is general and can be applied to any number of animations.

Here are the three simple animations:

restart;
with(plots):
A:=animate(plot, [sin(x), x=-Pi..a, color=red, thickness=3], a=-Pi..Pi):
B:=animate(plot, [x^2-1, x=-2..a, thickness=3, color=green], a=-2..2): 
C:=animate(plot, [[4*cos(t),4*sin(t), t=0..a], color=blue, thickness=3], a=0..2*Pi):

 

In Example 1 all three animation executed simultaneously:

display([A, B, C], view=[-4..4,-4..4]);

                                

 

In Example 2, the same animation performed sequentially. Note that the previous animation disappears completely when the next one begins to execute:

display([A, B, C], insequence);

                                 

 

Below we show how to save the last frame of every previous animation into subsequent animations:

display([A, display(op([1,-1,1],A),B), display(op([1,-1,1],A),op([1,-1,1],B),C)], insequence);

                                 

 

Using this technique, we can anyhow combine the original animations. For example, in the following example at firstly animations   and  B  are executed simultaneously, afterwards C is executed:

display([display(A, B), display(op([1,-1,1],A),op([1,-1,1],B),C)], insequence);

                                     

 

The last example in 3D I have taken from here:

restart;
with(plots):
A:=animate(plot3d,[[2*cos(phi),2*sin(phi),z], z =0..a, phi=0..2*Pi, style=surface, color=red], a=0..5):
B:=animate(plot3d,[[(2+6/5*(z-5))*cos(phi), (2+6/5*(z-5))*sin(phi),z], z=5..a, phi=0..2*Pi, style=surface, color=blue], a=5..10):
C:=animate(plot3d,[[8*cos(phi),8*sin(phi),z], z =10..a, phi=0..2*Pi, style=surface, color=green], a=10..20):
display([A, display(op([1,-1,1],A),B), display(op([1,-1,1],A),op([1,-1,1],B),C)], insequence, scaling=constrained, axes=normal);

                        


 

AA.mw

   

 

The code for the animation:

L:=[[-0.12,2],[-0.14,0],[0.14,0],[0.12,2]]:
L1:=[[0.05,2],[4,1],[2,4],[3.5,3.5],[1,7],[2,6.5],[0,10]]:
A:=plot(L, color=brown, thickness=10):
B:=plot([op(L1),op(map(t->[-t[1],t[2]],ListTools:-Reverse(L1)))], color="Green", thickness=10):
C:=plottools:-polygon([op(L1),op(map(t->[-t[1],t[2]],ListTools:-Reverse(L1)))], color=green):
Tree:=plots:-display([A, B, C], scaling=constrained, axes=none):
T:=[[-3.2,-2, Happy, color=blue, font=[times,bold,30]], [0,-2,New, color=blue, font=[times,bold,30]], [2.5,-2,Year, color=blue, font=[times,bold,30]], [-5,-3.5, "&", color=yellow, font=[times,bold,30]],[-2.5,-3.5, Merry, color=red, font=[times,bold,30]], [2.3,-3.5, Christmas!, color=red, font=[times,bold,30]], [0,-5, "2017", color=cyan, font=[times,bold,36]]$5]:
F:=k->plottools:-homothety(Tree, k, [0,5]):
A:=plots:-animate(plots:-display, ['F'(k)], k=0..1, frames=60, paraminfo=false):
B:=plots:-animate(plots:-textplot,[T[1..round(i)]], i=0..nops(T), frames=60, paraminfo=false):
plots:-display(A, B, size=[500,550], scaling=constrained);


Christmas_Tree.mw

 Edit.

 

2 3 4 5 6 7 8 Last Page 4 of 12