Featured Post

 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



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.

# 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

local m, k, l, r, a, L1;
m:=nops(L[1]); k:=0;
for l in L do
for r in R do
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):


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

for m in M1 do
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;
M2:=convert(M2, list):


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

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; 
od: od:
n:=n+1; T[n]:=[m,convert(S,set)];
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;

# 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));
U; s:=[op(U)];
k:=k+1; P[k]:=[seq(v[i],i=s[1..-2])];
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)]:


We get 28 unique solutions to this problem.

Visualization of all these solutions:

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]);




The code was edited.



Featured Post

So I have recently finished up a project that took different sounds found in nature, and through the Spectrogram command, plotted the frequency of each sound over time with some really cool results!


The contrast between sounds produced by the weather such as tornadoes, thunder, and hail versus something as innocuous as a buzzing bee, a chorus of crickets, or a purring cat really shows the variance in the different sounds we hear in our day to day life, while also creating some very interesting imagery.

My personal favourite was the cricket chorus, producing a very ordered image with some really cool spikes through many different frequencies as the crickets chirped, as shown here:

Using this plot, we can do some interesting things, like count the number of chirps in 8 seconds, which turns out to be 18-18.5. Why Is this important? Well, there’s a law known as Dolbear’s Law(shown here: https://en.wikipedia.org/wiki/Dolbear%27s_law)  which uses the number of chirps in a minute for Fahrenheit, or 8 seconds for Celsius to calculate the temperature. Celsius is very simple, and just requires adding 5 to the number of chirps in 8 seconds, which gets us a temperature of 23C.

Tc= 5 + N8

For Fahrenheit, it’s a bit more complicated, as we need the chirps in a minute. This is around 132 chirps in our case. Putting that into the formula:

TF= 50 +((N60 – 40)/4)

Which gets us 73F, or 22.7C, so you can see that it works pretty well! Pretty cool, huh?


There was also some really cool images that were produced, like the thunder plot:

Which I personally really like due to the contrasting black and yellow spike that occurs. Overall this was a very fun project to do, getting to tweak the different colours and scales of each spectrogram, creating a story out of a sound. Hope you all enjoy it!

adjusting latex output

Maple 17 asked by digerdiga 180 Yesterday

Crank Nicolson

asked by basha 666 0 Yesterday