This is part of live presentation series called Mathematical Games in which we explore a variety of games and puzzles using Wolfram Language. In this episode, we explore some covering sets.
demonstrations.wolfram.com
demonstrations.wolfram.com
Many Demonstrations cover covering.
In the news:
In the news:
Can you cover a tetrahedron so it is only stable on one face?
by: Izidor Hafner
A face of a polyhedron is stable if and only if the orthogonal projection of the center of mass of the polyhedron onto the plane of the face lies inside the face or on an edge. In other words, when the polyhedron is placed on that face, the center of mass is over the face. This tetrahedron has two unstable faces. If you place it on one of the unstable faces, it will topple to the other unstable face and then topple to one of the stable faces.
Out[]=
In the News: The Kobon Triangle problem.
In the News: The Kobon Triangle problem.
In Wheels, Life, and Other Mathematical Amusements, Gardner discussed the Kobon Triangle problem for getting the maximum coverage of triangles with a given number of lines.
Covering problems in Gardner’s books - Circles
Covering problems in Gardner’s books - Circles
Covering a circle with 5 circles
Out[]=
Covering with 3α-2α-2=0
Covering with -2α-2=0
3
α
The algebraic number field for -2α-2=0 provides the best solution for 12 disks covering a unit disk.
3
α
Out[]=
Melissen 12 Disk Covering (in -2-2α+ 3 α |
That value also provides a solution for the 12 point Heilbronn problem maximizing the area of the smallest triangle in a unit square.
Out[]=
Heilbronn Square 12 (in -2-2α+ 3 α |
triangles have area 0.03259885869 |
Not many polynomials have roots that cover their coefficients. The algebraic number field of -2α-2=0 allows for a rare cubic with equivalent roots and coefficients.
3
α
r=(-Root[-2-2#1+&,1]);poly=RootReduce[x^3+(/2-1)+rx+(2-r-)]
3
#1
2
r
2
x
2
r
In[]:=
Solve+x++==0
3
x
2
x
Out[]=
x,x,x
This is the same root associated with .
π
19
ColumnAccountingForm[N[Root[-2-2#1+&,1]^24-24,30]],AccountingForm[N[E^(PiSqrt[19]),30]],96^3+744
3
#1
885479.777991852361442453825758 |
885479.777680154319497537893482 |
885480 |
Covering problems in Gardner’s books - Ternary System
Covering problems in Gardner’s books - Ternary System
A number represented in binary is a sum of the powers of 2 (1, 2, 4, 8, 16,...) multiplied by 0 or 1. For example, 60 in binary notation is , using six "bits".
111100=1×32+1×16+1×8+1×4+0×2+0×1
Balanced ternary notation multiplies each power of 3 (1, 3, 9, 27,...) by -1, 0, or 1. In balanced ternary, 60 is , with 1 indicating -1; 60 requires five "trits". With weights 1, 3, 9, 27, and 81, the notation can be used to balance any unit amount from 1 to 121 by putting the weights on either side of the balance pan.
11110=81-27+9-3+0
Out[]=
Covering problems in Gardner’s books -- Consecutive Squares
Covering problems in Gardner’s books -- Consecutive Squares
Ponting Squares
Ponting Squares
Can squares with sides equal to consecutive values 1 to tile the plane? An arbitrarily large patch can be covered by a method found by Adam Ponting[1].
Start with an gray and white checkerboard, where is odd and the corners are gray. Fill in the gray squares from left to right, bottom to top, with the numbers from 1 to . Fill in the white squares top to bottom, left to right, with the numbers from to . At each vertex, a unit segment is drawn, vertical if the gray squares around that vertex are sloping down and horizontal if they are sloping up. This matrix has the property that digit pairs on each side of a segment have the same sum, which allows each number to be converted to a square of side . The segments indicate the squares are flush on that side.
n
Start with an
n×n
n
(+1)/2
2
n
(+3)/2
2
n
2
n
k
k
Out[]=
Covering problems in Gardner’s books -- Chess Coverings
Covering problems in Gardner’s books -- Chess Coverings
One of Gardner’s favorite problems: Place 5 white queens and 3 black queens on a 5×5 chessboard so they don’t attack each other.
https://oeis.org/A051567 2*floor(2n/3) queens on a nxn board each attacking 1 other.
https://oeis.org/A051567 2*floor(2n/3) queens on a nxn board each attacking 1 other.
{0, 5, 0, 2, 149, 49, 1, 12897, 2238}
The solution for the 9x9 board is unique.
Covering problems in Gardner’s books -- Sparse Rulers
Covering problems in Gardner’s books -- Sparse Rulers
Consider a sparse ruler of length 13. Clearly, five marks wouldn’t be enough since there are at most (5; 2)=10 differences between possible marks. On the other hand, six marks is enough, but because that gives (6; 2)=15 differences, there must be two repeats. {0, 1, 6, 9, 11, 13}
In[]:=
SplitBy[SortBy[Subsets[{0,1,6,9,11,13},{2}],#[[2]]-#[[1]]&],#[[2]]-#[[1]]&]
Out[]=
{{{0,1}},{{9,11},{11,13}},{{6,9}},{{9,13}},{{1,6},{6,11}},{{0,6}},{{6,13}},{{1,9}},{{0,9}},{{1,11}},{{0,11}},{{1,13}},{{0,13}}}
Here’s the unique Leech Yardstick:
Here’s unique 1m ruler.
The Pegg 1-meter ruler has a 100 partition, which measures 214cm.
In solving the problem, I first noticed that all rulers needed marks, where 0 or 1 was the excess E. Then I noticed a pattern when stacking rulers by maximal marks.
rnd(
3n+9/4
)+01
NJA Sloane called the pattern “Dark Satanic Mills on a Cloudy Day”.
As seen above, the length 50 sparse ruler on the left covers all lengths up to 50.
Cyclic Sum Sets
Cyclic Sum Sets
Like sparse rulers, but covers in a circle.
For all prime powers , there are possible Singer difference sets with +1 terms and modulus , where and is the Euler function. For the example , , , and . The two sets are and . For a given Singer difference set with modulus , the others are , where is relatively prime to . In our example, .This Demonstration lets you pick from the prime powers and two other values, 6 and 10. The modulus is shown at the center of the annulus. For each pick, you may index through the cyclic sum sets. For examples based on 6 and 10, with 7 and 11 terms, a perfect covering is impossible. There are duplicated sums in these two examples, with coverings to the maximal values of 39 and 95. For all other non-prime powers, starting with terms, the maximal coverings are unknown.
m
q
s
m
q
M=++1
2
m
q
m
q
s=ϕ(M)/(6m)
ϕ
ϕ
A
q=3
m=1
M=13
s=2
A
B
S
M
kS(modM)
k
M
B=2A(mod13)
2,3,4,5,7,8,9,11,13,16,17,19,23,25,27,29,31,32
M
ϕ(M)/(6m)
12+1=13
Out[]=
134 , 215 , 316 , 578 , 739 , 9110 -- Singer Difference Sets
13
4
21
5
31
6
57
8
73
9
91
10
On a circular wheel is used, a perfect set of measuring marks is called a difference set, a Ganymede circle, or an n-switch. All the distances between selected red points are different. The distances are indicated by arcs inside the circle.
As a difference set, all possible differences are given by the set:
In[]:=
Sort[Flatten[Mod[{#[[2]]-#[[1]],#[[1]]-#[[2]]},31,1]&/@Subsets[{0,1,3,8,12,18},{2}]]]
Out[]=
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30}
Out[]=
Perfect Partitions
Perfect Partitions
We can look for perfect cyclic partitions for any N value. Here are some solutions.
{{{1}},{{1,1}},{{1,2}},{{1,1,2}},{{1,1,3},{1,2,2}},{{1,2,3}},{{1,2,4}},{{1,1,2,4},{1,1,3,3},{1,2,1,4},{1,2,2,3}},{{1,1,2,5},{1,1,3,4},{1,2,1,5},{1,2,2,4},{1,2,3,3}},{{1,1,3,5},{1,2,2,5},{1,2,3,4},{1,3,2,4}},{{1,1,3,6},{1,2,2,6},{1,2,4,4},{1,2,5,3},{1,3,2,5}},{{1,2,4,5},{1,3,2,6}}{{1,2,6,4},{1,3,2,7}},{{1,1,1,4,7},{1,1,2,3,7},{1,1,2,5,5},{1,1,3,2,7}},{{1,1,1,4,8},{1,1,2,3,8},{1,1,2,5,6},{1,1,2,6,5}},{{1,1,3,3,8},{1,1,3,5,6},{1,1,4,3,7},{1,2,1,5,7}},{{1,1,2,8,5},{1,1,3,3,9},{1,1,3,6,6},{1,1,4,3,8}},{{1,1,3,6,7},{1,1,4,3,9},{1,2,3,4,8},{1,2,5,4,6}},{{1,1,4,3,10},{1,2,2,8,6},{1,2,4,5,7},{1,2,6,6,4}},{{1,1,1,3,4,10},{1,1,1,3,7,7},{1,1,1,4,3,10}},{{1,3,10,2,5}},{{1,1,1,4,4,11},{1,1,1,4,7,8},{1,1,1,5,4,10}},{{1,1,1,4,4,12},{1,1,1,4,8,8},{1,1,1,5,4,11}},{{1,1,1,4,8,9},{1,1,1,5,4,12},{1,1,2,8,7,5}},{{1,1,1,5,4,13},{1,1,2,5,6,10},{1,1,2,8,8,5}},{{1,1,3,4,6,11},{1,1,3,7,6,8},{1,1,4,4,3,13}},{{1,1,3,8,9,5},{1,1,4,3,7,11},{1,1,4,4,3,14}},{{1,3,11,5,2,6}},{{1,1,1,1,5,5,15},{1,1,1,1,5,10,10},{1,1,1,1,6,5,14}},{{1,1,1,1,5,10,11},{1,1,1,1,6,5,15},{1,1,1,2,6,7,12}},{{1,2,5,4,6,13},{1,2,7,4,12,5},{1,3,2,7,8,10}}}
Here are some trickier partitions to find.
{(*93*){1,5,4,13,3,8,7,12,2,2,36},(*95*){1,2,6,11,13,14,8,15,16,5,4},(*101*){1,14,10,20,7,6,3,2,17,4,8,9},(*101*){1,15,5,3,25,2,7,4,6,12,14,7},(*102*){1,3,12,3,21,2,8,9,5,6,7,25},(*103*){1,2,14,12,2,19,6,5,4,18,13,7},(*104*){1,2,12,2,25,4,9,10,7,11,16,5},(*104*){1,8,10,5,7,21,4,2,11,3,26,6},(*107*){1,8,10,5,7,21,4,2,11,3,26,9},(*108*){1,2,12,6,25,4,9,10,7,11,16,5}}
The lengths of these partitions is as follows:
{{1},{2,2},{3,3,3,3},{4,4,4,4,4,4},{5,5,5,5,5,5,6,5},{6,6,6,6,6,6,6,7,7,6},{7,7,7,7,7,7,8,7,8,8,8,8},{8,8,8,8,8,8,8,8,9,9,9,9,9,8},{9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,9},{10,10,10,10,10,10,11,11,11,11,11,11,11,11,11,11,11,10},{11,11,12,11,12,12,12,12,12,12,12,12,12,x,x,12,12,x,x,x}}
Here’s the excess pattern as it is known so far:
{{0},{0,0},{0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0,1,0},{0,0,0,0,0,0,0,1,1,0},{0,0,0,0,0,0,1,0,1,1,1,1},{0,0,0,0,0,0,0,0,1,1,1,1,1,0},{0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0},{0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0},{0,0,1,0,1,1,1,1,1,1,1,1,1,2,2,1,1,2,2,2}}
Difference Sets in Configurations
Difference Sets in Configurations
The {0,1,4,14,16}_21 difference set in circles and lines. All pairs of points 0-20 are connected by a circle or line.
The {0,1,3,9}_13 difference set as a configuration of parabolas
The {0,1,3,9}_13 difference set as a configuration of parabolas
The Springer Difference Set -- Spot-It
The Springer Difference Set -- Spot-It
The game of Spot-it uses a Springer difference set. Any two cards of the 57 card set share a number:
In[]:=
Table[Style[Grid[Partition[Mod[RandomSample[{0,1,6,15,22,26,45,55}+RandomInteger[{0,56}]],57],4],Frame->All],30],{2}]
Out[]=
,
36 | 4 | 33 | 41 |
35 | 50 | 0 | 23 |
55 | 32 | 11 | 36 |
16 | 25 | 10 | 8 |
Any two cards of the 73 card set share a number:
In[]:=
Table[Style[Grid[Partition[Mod[RandomSample[{0,1,12,20,26,30,33,35,57}+RandomInteger[{0,72}]],73],3],Frame->All],30],{2}]
Out[]=
,
15 | 9 | 63 |
1 | 62 | 19 |
24 | 46 | 22 |
31 | 16 | 26 |
53 | 22 | 70 |
29 | 8 | 69 |
Any two cards of the 133 card set share a number:
In[]:=
Table[Style[Grid[Partition[Mod[RandomSample[{0,1,3,17,21,58,65,73,100,105,111,124}+RandomInteger[{0,132}]],133],4],Frame->All],30],{2}]
Out[]=
,
126 | 44 | 53 | 56 |
20 | 118 | 54 | 74 |
31 | 70 | 25 | 111 |
100 | 62 | 94 | 123 |
122 | 89 | 10 | 125 |
47 | 113 | 54 | 6 |
MG8: Polygon Dissections
MG8: Polygon Dissections
MG16: Space-filling Curves
MG16: Space-filling Curves
How can we cover space with a curve?
The Marcel J. E. Golay 1949 paper. “The Best Single Page in Coding” - Berlekamp
The Marcel J. E. Golay 1949 paper. “The Best Single Page in Coding” - Berlekamp
Generating the Binary Golay Code
Generating the Binary Golay Code
There is a natural way to generate the binary Golay code. Just use the inverse of the icosahedron! It’s that easy!
In[]:=
ico={{1,0,0,0,0,0,1,1,1,1,1,1},{0,1,0,1,0,1,0,0,1,1,1,1},{0,0,1,0,1,1,0,1,0,1,1,1},{0,1,0,1,1,0,1,1,0,0,1,1},{0,0,1,1,1,0,1,0,1,1,0,1},{0,1,1,0,0,1,1,1,1,0,0,1},{1,0,0,1,1,1,1,0,0,1,1,0},{1,0,1,1,0,1,0,1,1,1,0,0},{1,1,0,0,1,1,0,1,1,0,1,0},{1,1,1,0,1,0,1,1,0,1,0,0},{1,1,1,1,0,0,1,0,1,0,1,0},{1,1,1,1,1,1,0,0,0,0,0,1}};Row[{Graph3D[UndirectedEdge@@@Union[Sort/@Position[1-ico,1]],ImageSize->Small],Graph3D[UndirectedEdge@@@Select[Union[Sort/@Position[ico,1]],Length[Union[#]]==2&],ImageSize->Small]}]
Out[]=
Just join with the identity matrix:
In[]:=
golayico=Join[IdentityMatrix[12],ico,2];ArrayPlot[golayico,PixelConstrained->25]
Out[]=
In[]:=
fullcodeico=Mod[Total/@Subsets[golayico,{0,12}],2];
In[]:=
Sort[Tally[Total/@fullcodeico]]
Out[]=
{{0,1},{8,759},{12,2576},{16,759},{24,1}}
MG19: Turing Machines
MG19: Turing Machines
Covering all programs.
What do order-n simple programs do?
MG26: Puzzles on a Square Grid
MG26: Puzzles on a Square Grid
Mondrian Art Problem
Mondrian Art Problem
Divide a square into non-congruent rectangles. If all the sides are integers, what is the smallest possible difference in area between the largest and smallest rectangles? This is known as the Mondrian art problem. This Demonstration shows optimal solutions up to size 65 and best known solutions up to 900.
Up to the square of side 100, check the "analysis" box to see the possible improvements. If all of those possibilities can be checked in a packing program without a new solution turning up, the given solution is optimal.
Can the defect be 0? If the rectangles do not have integer sides, there are many solutions, known as Blanche dissections. Whether there is an integer Blanche dissection is an unsolved question. The defect for square might be bounded above by +3. The quality of a solution is the favorable distance from this upper bound[6,9].
n
n
log(n)
In the variant, a rectangle can be repeated if it has a different orientation. It is is a tiling where no rectangle has a direct translation to another rectangle. The upper bound seems to be . Solutions up to size 45 are optimal.
n
log(n)
Out[]=
Thomas Kirkman Schoolgirl Problem
Thomas Kirkman Schoolgirl Problem
Fifteen young ladies in a school walk out three abreast for seven days in succession:it is required to arrange them daily,so that no two shall walk twice abreast.
The below grid was used by Cayley to solve the Kirkman Schoolgirl’s problem:
A set of 28 double-8 dominoes without blanks or doubles. This is now called a Room square.
abc d35 e17 f28 g46 gives the first day.
abc d35 e17 f28 g46 gives the first day.
Out[]=
a | b | c | d | e | f | g | |
abc | |||||||
ade | |||||||
afg | |||||||
bdf | |||||||
bge | |||||||
cdg | |||||||
cef |
Smallest Projective Space
Smallest Projective Space
In[]:=
pg23={{1,4,5},{8,9,1},{2,10,8},{14,12,2},{5,11,14},{1,3,2},{2,7,5},{5,13,8},{8,6,14},{14,15,1},{2,6,4},{14,7,9},{5,15,10},{1,13,12},{8,3,11},{6,11,13},{7,4,3},{15,9,6},{13,10,7},{3,12,15},{15,8,7},{13,2,15},{3,14,13},{6,5,3},{7,1,6},{9,3,10},{10,6,12},{12,7,11},{11,15,4},{4,13,9},{9,2,11},{10,14,4},{12,5,9},{11,1,10},{4,8,12}};
The 35 triples of the smallest projective space all have an XOR sum of zero
In[]:=
BitXor@@#&/@pg23
Out[]=
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
15 points, each on 7 planes.
15 planes, each on 7 points. {1,2,3,4,5,6,7}, {2,4,6,9,11,13,15}, {2,4,6,8,10,12,14}
Also, 35 lines each with BitXor sum 0.
15 planes, each on 7 points. {1,2,3,4,5,6,7}, {2,4,6,9,11,13,15}, {2,4,6,8,10,12,14}
Also, 35 lines each with BitXor sum 0.
Find the fifteen projective Fano planes. One of them is 1 to 7.
Out[]=
Social Golfer Problem (Cayley, Kirkman, Steiner)
Social Golfer Problem (Cayley, Kirkman, Steiner)
A group consists of 32 golfers who want to play in groups of four for several days. Can they play for ten days, with no pair of golfers in the same group twice?
In 1850, Reverend Thomas Kirkman sent a related query to the readers of a popular math magazine, Lady’s and Gentleman’s Diary: Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily, so that no two will walk twice abreast. Arthur Cayley and Jakob Steiner solved the problem. For groups of three, solutions are called either a resolvable Steiner triple system (RSTS) or a Kirkman triple system (KTS).
Out[]=
Steiner Trees
Steiner Trees
Soap films can cover a road network. These lead to Steiner trees.
by: Ferenc Beleznay
We would like to find an optimal way of connecting a given finite set of points in the plane, in the sense that the total length of the line segments joining the points is minimal. This optimization problem is referred to as the Steiner tree problem. This Demonstration supports a manual search for such a network of line segments. It can be proved that an optimal network is achieved by adding some points (called Steiner points) to the original set of so-called regular points and finding the minimal spanning tree of the resulting complete graph, where the weights of the edges are the Euclidean distances between the endpoints.
Out[]=
S(2,3,9) : Lo Shu Magic Square
S(2,3,9) : Lo Shu Magic Square
Steiner systems cover a range. S(2,3,9) uses values up to 9 in sets of 3 so that all sets of 2 are covered. Many more coverings at the Covering Repository.
Any pair of numbers shows up in a row or column in exactly one of the grids.
In[]:=
Row[Riffle[Style[Text@Grid[Partition[#,3],Frame->All],30]&/@{Range[9],{4,9,2,3,5,7,8,1,6}}," "]]
Out[]=
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
4 | 9 | 2 |
3 | 5 | 7 |
8 | 1 | 6 |
Shown as triangles:
In[]:=
tri=Partition[#,3]&/@{Range[9],{4,9,2,3,5,7,8,1,6}};
Out[]=
S(2,4,16) : The 9 4 Puzzle
S(2,4,16) : The 9 4 Puzzle
Fill in the second grid so that any pair of numbers shows up in a row, column or main diagonal in exactly one of the grids.
In[]:=
Row[Riffle[Style[Text@Grid[Partition[#,4],Frame->All],30]&/@{Range[16],PadRight[{9,4},16," "]}," "]]
Out[]=
1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 |
9 | 4 | ||
To fill out the first row, there are 3 numbers to choose from. The 6 is on a diagonal.
For balance, 6 will need to be off the diagonals in the second grid.
For balance, 6 will need to be off the diagonals in the second grid.
Out[]=
1 | 2 | 3 | 4 |
5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 |
9 | 4 | ||
Only memorize the 9 and 4.
Only memorize the 9 and 4.
Or we can arrange them all graphically (blue+magenta, yellow+green, orange):
Out[]=
| ||||||||||||||||
|
S(2,5,25) : Magic Hexagon
S(2,5,25) : Magic Hexagon
Fill in the second grid so that any pair of numbers shows up in a row, column or wrapped \ diagonal in exactly one of the grids.
In[]:=
Row[Riffle[Style[Text@Grid[Partition[#,5],Frame->All],30]&/@{Range[25],{1,20,9,23,12,8,22,11,5,19,15,4,18,7,21,17,6,25,14,3,24,13,2,16,10}}," "]]
Out[]=
1 | 2 | 3 | 4 | 5 |
6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 |
1 | 20 | 9 | 23 | 12 |
8 | 22 | 11 | 5 | 19 |
15 | 4 | 18 | 7 | 21 |
17 | 6 | 25 | 14 | 3 |
24 | 13 | 2 | 16 | 10 |
This is easier to see in a hexagonal grid:
Out[]=
This better presented with a clipped hexagon
S(2,7,49) :
S(2,7,49) :
For 7×7 grids, the grids are toroidal. In each grid the digits seen by 1 are shown.
A moment of Venn
A moment of Venn
The 32 regions of Venn-5 cover all possible true-false options for five sets.
In[]:=
vennpoints=-Join[Reverse/@CirclePoints[5],1.45Reverse/@CirclePoints[10],2.6CirclePoints[10],-4CirclePoints[5]];venn5={{28,25,14,5,1,7,21,20,9,10,18,29,28},{27,23,6,1,2,9,19,18,11,12,16,28,27},{26,21,8,2,3,11,17,16,13,14,24,27,26},{30,19,10,3,4,13,25,24,15,6,22,26,30},{29,17,12,4,5,15,23,22,7,8,20,30,29}};colors={Orange,Yellow,Green,Red,Blue};Graphics[Table[{colors[[n]],Thick,Line[vennpoints[[venn5[[n]]]]]},{n,1,5}]]
Out[]=
Done another way:
In[]:=
pp=RootReduce[2CirclePoints[5]/(EuclideanDistance@@CirclePoints[5][[{1,2}]])];sp=Join[Table[2.12CirclePoints[10][[Mod[n-2,10,1]]]+pp[[2]],{n,1,9}],Table[1.05CirclePoints[10][[Mod[n-6,10,1]]]+pp[[4]],{n,1,7}]];colors={Orange,Magenta,Green,Red,Cyan};
In[]:=
Graphics[{Table[{AbsoluteThickness[15],Black,BSplineCurve[sp.RotationMatrix[2kPi/5],SplineClosedTrue],AbsoluteThickness[13],colors[[k+1]],BSplineCurve[sp.RotationMatrix[2kPi/5],SplineClosedTrue]},{k,0,4}]},ImageSize600]
Out[]=
Graceful Graphs
Graceful Graphs
A graceful graph has numbered vertices and N edges such that the vertex differences are 1 to N.
In[]:=
ResourceFunction["GracefulGraphFromPermutation"][{1,2,9,5,4,12,7,6,3,11,10,8}]
Out[]=
Note that the Lehmer code for the same permutation uses {0,1,2,6}.
In[]:=
ResourceFunction["LehmerCodeFromPermutation"][{1,2,9,5,4,12,7,6,3,11,10,8}]
Out[]=
{0,0,6,2,1,6,2,1,0,2,1,0}
Here are the smallest graceful graphs with valence 5, 6, 7 and 8. These were found by using Sparse Rulers, mentioned earlier. The minimal possible vertices for a graceful graph with edges is . How can we find the corresponding permutations?
n
rnd(
3n+9/4
)
For valence 9, the graph complement looks better.
The de Bruijn Torus
The de Bruijn Torus
A de Bruijn sequence cyclically covers all combinations.
In[]:=
DeBruijnSequence[{0,1},4]
Out[]=
{0,0,0,0,1,0,0,1,1,0,1,0,1,1,1,1}
In the de Bruijn sequence , all items of order two from the alphabet of size four are cyclically represented. Those items are , , , and so on. In the de Bruijn sequence , all order-four items from the size-two alphabet are cyclically represented. In this case, the items are , , and so on.In general, the order- de Bruijn sequence for a size- alphabet has length . There are different sequences.For a de Bruijn torus, all -matrices from a size- alphabet have toroidal representation in an array. In this Demonstration, de Bruijn tori for ternary , quaternary , binary and binary are shown. Choose an index number with a slider; the de Bruijn torus is rotated to place the corresponding matrix in the upper-left corner of the array.
0010203112132233
{0,1,2,3}
00
01
10
02
0000100110101111
{0,1}
0000
0001
0010
n
k
B(k,n)
n
k
n-1
k
(k!)
n
k
B(k,n)
(m,n)
k
2×2
2×2
3×2
3×3
Out[]=
Covering a 24-cell with Hypercubes
Covering a 24-cell with Hypercubes
We can cover a 24-cell with 3 hypercubes.
Out[]=
Similarly, we can cover graph with three copies of hypercubes with diagonals, otherwise known as the Clebsch graph. This proves Ramsey(3,3,3)>16. In other words, we can color the graph in 3 colors with no triangles. One game introduced by Gardner is 2-coloring connections in a hexagon, with the first to make a triangle losing.
K
16
Out[]=
Engel 38 Spacefiller
Engel 38 Spacefiller
What’s the most complex way to cover space with a convex polyhedron? The Engel polyhedron has 38 sides.
Out[]=
Here’s a picture of just the polyhedron:
In[]:=
Graphics3D[{Red,Polyhedron[vv,pol]},Boxed->False,SphericalRegion->True]
Out[]=
Describe a polyhedron with minimal values.
Describe a polyhedron with minimal values.
The vertices of an icosahedron can be covered with one coordinate:
In[]:=
Out[]=
{{-1,-ϕ,0},{-1,ϕ,0},{0,-1,-ϕ},{0,-1,ϕ},{0,1,-ϕ},{0,1,ϕ},{1,-ϕ,0},{1,ϕ,0},{-ϕ,0,-1},{-ϕ,0,1},{ϕ,0,-1},{ϕ,0,1}}
All the Platonic and Archimedean solids are easy to represent:
ϕ=(1+;ξ=;tetrahedron=Select[{1,1,1}],EvenQ[Count[Sign[#],-1]]&Sqrt[8];cube=[{1,1,1}/2];octahedron=[{0,0,1}]Sqrt[2];cuboctahedron=[{0,1,1}]Sqrt[2];icosahedron=[{0,1,ϕ},"Cyclic"]2;rhombicuboctahedron=[{1,1,1+Sqrt[2]},"Even"]2;truncatedcube=[{Sqrt[2]-1,1,1}](Sqrt[2]-1)2;truncatedoctahedron=[{0,1,2}]Sqrt[2];truncatedtetrahedron=Select[{1,1,3}],EvenQ[Count[Sign[#],-1]]&Sqrt[8];truncatedcuboctahedron=[{1,1+Sqrt[2],1+2Sqrt[2]}]2;dodecahedron=Join@@[#,"Cyclic"]&/@{{1,1,1},{0,ϕ,1/ϕ}}(2/ϕ);icosidodecahedron=Join@@[#,"Even"]&/@{0,0,ϕ},{1,ϕ,}2;snubcube=JoinSelect[{1,1/t,t},"Even"],EvenQ[Count[Sign[#],1]]&,Select[{1,1/t,t},"Odd"],OddQ[Count[Sign[#],1]]&Sqrt[2+4t-2t^2];rhombicosidodecahedron=Join@@[#,"Even"]&/@{{1,1,},{,ϕ,2ϕ},{2+ϕ,0,}}2;truncateddodecahedron=Join@@[#,"Even"]&/@{{0,1/ϕ,2+ϕ},{1/ϕ,ϕ,2ϕ},{ϕ,2,ϕ+1}}(2ϕ-2);truncatedicosahedron=Join@@[#,"Even"]&/@{{0,1,3ϕ},{1,2+ϕ,2ϕ},{ϕ,2,2ϕ+1}}2;truncatedicosidodecahedron=Join@@[#,"Even"]&/@{1/ϕ,1/ϕ,3+ϕ},{2/ϕ,ϕ,1+2ϕ},1ϕ,,3ϕ-1,{2ϕ-1,2,2+ϕ},{ϕ,3,2ϕ}(2ϕ-2);snubdodecahedron=JoinSelectJoin@@[#,"Even"]&/@,OddQ[Count[Sign[#],-1]]&,SelectJoin@@[#,"Even"]&/@,EvenQ[Count[Sign[#],-1]]&2;poly={tetrahedron,cube,octahedron,icosahedron,dodecahedron,cuboctahedron,icosidodecahedron,rhombicuboctahedron,rhombicosidodecahedron,truncatedcube,truncatedoctahedron,truncatedtetrahedron,truncatedcuboctahedron,truncateddodecahedron,truncatedicosahedron,truncatedicosidodecahedron,snubcube,snubdodecahedron};
1
2
5
);t=2
ϕ
3
ϕ
2
ϕ
2
ϕ
2
ϕ
In[]:=
Grid[Partition[ConvexHullMesh[N[#],ImageSize->Tiny]&/@poly,6]]
Out[]=
We can cover the vertices of a polyhedron with a Hamiltonian tour.
by: Ed Pegg Jr
This Demonstration shows Hamiltonian tours on various polyhedra.
Out[]=
No Three In A Line
No Three In A Line
Can we cover every row and column of a grid with 2 markers so that there are never 3 markers in a straight line?
104 points on a 52×52 square. No 3 points are in a line.
Are larger solutions possible? No-one knows!
Are larger solutions possible? No-one knows!
Orthoschemes and other Spacefilling Tetrahedra
Orthoschemes and other Spacefilling Tetrahedra
A cube can replicate itself with 8 copies.
A few tetrahedra, known as orthoschemes, can be divided into eight similar copies of themselves.
Are there any such polyhedra?
In[]:=
ortho1=IntegerDigits[#,10,3]&/@#&/@{{020,111,121,022},{022,111,112,222},{022,111,121,222},{022,113,112,222},{022,113,123,024},{022,113,123,222},{111,202,212,113},{111,222,212,113}};
In[]:=
ortho2=IntegerDigits[#,10,3]&/@#&/@{{002,022,111,113},{022,042,131,133},{022,222,111,113},{022,222,111,131},{022,222,113,133},{022,222,131,133},{111,131,220,222},{113,133,222,224}};
In[]:=
Graphics3D[{Opacity[.6],Tetrahedron/@ortho1},Boxed->False,SphericalRegion->True]
Out[]=
In[]:=
Graphics3D[{Opacity[.6],Tetrahedron/@ortho2},Boxed->False,SphericalRegion->True]
Out[]=
Covering a Rolling Octahedron
Covering a Rolling Octahedron
We can cover all possible edge-roll orientations of an octahedron with a graph.
This gives the Nauru graph, or the Rolling Octahedron graph.
This is the same graph as the positions of a 2×2×2 Rubik’s cube with half-twists only.
We can similarly get a rolling of the icosahedron to cover all orientations. Doing the cube is a nice puzzle. I still haven’t found a nice solution for the dodecahedron.
Out[]=
Magic Sums
Magic Sums
There are 32 tuples from -8 to 8 summing to zero.
In[]:=
Select[Subsets[Range[-8,8],{3}],Total[#]==0&]
Out[]=
{{-8,0,8},{-8,1,7},{-8,2,6},{-8,3,5},{-7,-1,8},{-7,0,7},{-7,1,6},{-7,2,5},{-7,3,4},{-6,-2,8},{-6,-1,7},{-6,0,6},{-6,1,5},{-6,2,4},{-5,-3,8},{-5,-2,7},{-5,-1,6},{-5,0,5},{-5,1,4},{-5,2,3},{-4,-3,7},{-4,-2,6},{-4,-1,5},{-4,0,4},{-4,1,3},{-3,-2,5},{-3,-1,4},{-3,0,3},{-3,1,2},{-2,-1,3},{-2,0,2},{-1,0,1}}
For any triple of values that sum to zero, those three points are on a straight line.
Out[]=
Pick three numbers from -7 to 7 that sum to 0, mod 15. Are they on a straight line here?
We can add another point at infinity for the six faint horizontal green lines.
We can add another point at infinity for the six faint horizontal green lines.
Of the maximizing solutions for the 3-in-a-row problem, solutions for =7, 11, 16, and 19 points are sporadic, with more lines than lower bound (p-3)p+1. The above card trick is the fifth sporadic orchard solution, with 37 lines for 16 points (one at infinity). Terrence Tao missed it in his proof on the problem.
p
1
6
Out[]=
|
| ||||
|
|
Power Wheel Graphs
Power Wheel Graphs
How can similar triangles cover a vertex?
Some triangles have sides . In terms of a value , they have power sides . If all sides are multiplied by , one gets the similar triangle . This is called a powered triangle (not to be confused with a power triangle, used for AC circuits). For the given problem, powered triangles can simplify the solution process.
When powered triangles fit perfectly around a vertex, they make a wheel graph. Sometimes these wheels can lead to solutions when more triangles are added. For example, wheel 5 based on--10 with powers and additions gives a solution when is also added. If the original figure is a triangle, it cannot be similar to the component triangles.
(,,)
a
x
b
x
c
x
x
(a,b,c)
x
(a+1,b+1,c+1)
When powered triangles fit perfectly around a vertex, they make a wheel graph. Sometimes these wheels can lead to solutions when more triangles are added. For example, wheel 5 based on
8
x
2
x
(0,2,5)
(0,1,2,3,4)
(5,6)
Out[]=
Life is Omniperiodic
Life is Omniperiodic
In the cellular automaton called the Game of Life, a configuration of cells that returns to a prior state after steps is called a period- oscillator. Prior to the year 2023, it was unknown if period 19 or period 41 oscillators existed. Due to recent discoveries by Mitchell Riley and Nico Brown [1], oscillators of all periods are now known.
n
n
Out[]=
WFR GraphCoordinationSequence
WFR GraphCoordinationSequence
What graphs cover a particular property?
The coordination sequence is the number of vertices at distance 0, 1, 2, ... from a vertex.
In[]:=
ResourceFunction["GraphCoordinationSequence"]
Out[]=
{{1,3,6,8,2}}
Many graphs have the coordination sequence {1,3,6,4} for all vertices.
Out[]=
|
|
|
|
|
|
|
|
| ||||||||||||||||||
|
|
|
|
|
|
|
|
| ||||||||||||||||||
|
|
|
|
|
|
|
|
| ||||||||||||||||||
|
|
|
|
|
|
|
|
| ||||||||||||||||||
|
|
|
|
|
|
|
|
| ||||||||||||||||||
|
|
|
|
|
|
|
|
| ||||||||||||||||||
|
|
|
|
|
|
|
|
| ||||||||||||||||||
|
|
|
|
|
|
|
|
| ||||||||||||||||||
|
|
|
|
|
|
|
|
| ||||||||||||||||||
|
|
|
|
|
|
|
|
|
How many cylinders can cover/touch each other?
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Mathematical Games: Covering Sets
by Ed Pegg
Wolfram Community, STAFF PICKS, July 24, 2025
https://community.wolfram.com/groups/-/m/t/3518190
by Ed Pegg
Wolfram Community, STAFF PICKS, July 24, 2025
https://community.wolfram.com/groups/-/m/t/3518190