Distancing uniquely

The latest Maths Puzzle from Matt Parker concerns itself with distancing, not socially but uniquely. Can you put three markers in a 3 by 3 square such that no two marker-to-marker distances are the same? You can:

Here A and B are 1 unit apart, B and C are √5 units apart, and A and C are 2√2 units apart. Not counting reflections and rotations, there are 5 distinct ways to put three markers in a size 3 square at unique distances:

Parker asks for a solution for six markers in a 6 by 6 square. I very quickly convinced myself that if there’s an intelligent, elegant way to get such a solution by pencil and paper, I wasn’t going to find it. Instead I wrote a Python script to find all solutions for any size square. Any size to a point, anyway.

How many ways are there to put n markers in an n by n square? If you number the positions 1 through n^2 then selecting n positions to receive markers amounts to choosing n out of n^2; the number of ways of doing so is \binom{n^2}{n} = n^2!/(n!(n^2-n)!). For 3 markers in a 3 by 3 square there are 84 ways. For 6 markers in a 6 by 6 square there are 1,947,792 ways. My Python script gets very slow very fast.

The way it works is this: There’s a subroutine that takes a string pattern like “*.*……” which is the concatenation of “*.*”, “…”, and “…” corresponding to:

The subroutine does nothing if it finds non-unique distances within the pattern. If the distances are unique and the number of markers is equal to the largest number previously seen with unique distances it adds the pattern to a list of solutions; if the number of markers exceeds the largest number previously seen, it erases the list of solutions and starts a new list with this pattern. Then it calls itself recursively to investigate patterns made by taking the original one and adding a marker at each of the rightmost empty positions. (In this case it checks “*.**…..”, “*.*.*….”, “*.*..*…”, “*.*…*..”, “*.*….*.”, and “*.*…..*”)

Actually it does the above only after looking at the eight possible rotations and reflections of the pattern and seeing whether it’s the lexicographically smallest of the eight.

In a 2 by 2 square you can put 2 markers, 2 different ways. (Adjacent to one another orthogonally or diagonally. Of course there is only one distance either way, so it’s unique.) In a 3 by 3 square you can put 3 markers 5 ways, as seen above. For 4 by 4: 4 markers, 23 ways. For 5 by 5: 5 markers, 35 ways.

So it looks as though the number of ways to put n markers in an n by n square just keeps increasing. Until you try it with 6. You can put 6 markers in a 6 by 6 square… only 2 ways. 7 markers in a 7 by 7 square — only 1 way. When you get to 8 markers in an 8 by 8 square, it can’t be done. At best you can put 7 markers, but there are 3350 different ways!

Having done that for squares, I modified the script to do other dimensions: Rows of n positions or cubes of n^3 positions. Rows are easy — the number of combinations grows slowly. Cubes grow very fast. Worse yet, checking all 48 possible rotations and reflections in three dimensions gets complicated, and once I finally got that code working, I discovered that even though checking for rotations and reflections cut way down on the number of positions it needed to examine, it was slower than examining all positions, because the reflection and rotation checking took so much time! Then I realized it’d make more sense to check for duplicate distances first, then check for rotations and reflections before doing the recursive calls, and that did speed things up somewhat, but not enough to make a lot of difference. There are probably smarter ways to do it in Python, and probably even smarter ways in C, but I’ll leave those to someone else to work out.

For rows I looked at sizes up to an arbitrary limit of 20. For squares and cubes I stopped when I got to a size that took more than about three hours. Successive size squares took about ten times as long, and successive size cubes about 200 times as long! The results:

dimensions ->123
size vmaxsolutionsmaxsolutionsmaxsolutions
2212231
32235420
431423636
53353574223
63762
74171
84573350
94138547
10430952
11455
1252
13511
14534
15578
165160
175292
1864
19612
20640

For instance, in a row of 5 positions, there are 3 ways to put 3 markers at unique distances. In a 5 by 5 square, there are, as said above, 35 ways to put 5 markers. In a 5 by 5 by 5 cube, there are 4223 ways to put 7 markers, and so forth.

The two solutions for 6 markers in 6 by 6 are:

Greeks and Romans and cards

Take the aces and face cards from a deck; you can arrange those sixteen cards in a square. But can you arrange them in a square in such a way that every rank and every suit appears in every row, every column, and both diagonals? You can. (Go try it, it’s not that hard.) How many ways? (That’s harder!)

A simpler problem is to ignore the suits and just have every row, column, and diagonal contain all four ranks. You can do that easily enough by trial and error, but how many ways can you do it?

Let’s suppose you make the top row A K Q J and see what solutions that leads to. Every other row, column, and diagonal has to be some permutation of A K Q J. In particular, the first column must be one of the permutations that begins with A. There are six such permutations:

A K Q J
A K J Q
A Q K J
A Q J K
A J K Q
A J Q K

But it can’t be A K Q J or A Q K J, because that would put two Js on one of the diagonals. So for the first row and column there are four possibilities:

A K Q J   A K Q J   A K Q J   A K Q J
K         Q         J         J
J         J         K         Q
Q         K         Q         K

Now, what goes in the third row, third column for the first of these? It shares a diagonal with an A, a row with a J, and a column with a Q, so it has to be a K:

A K Q J
K
J   K
Q     ?

Now what do you put in the fourth row, fourth column? Not an A or a K, because it shares a diagonal with them; not a Q, because it shares a row with that, and not a J, because it shares a column with that. There’s nothing you can put there. So the first column can’t be A K J Q.

In similar fashion you can eliminate A J Q K. The second row, second column must be Q, and then once again the fourth row, fourth column can’t be filled.

Try the second possibility:

A K Q J
Q ? 
J   ?
K     ?

The second row, second column has to be a J; the third row, third column must be a K; and the fourth row, fourth column is a Q.

A K Q J
Q J
J   K
K     Q

Then the remaining positions are similarly forced: A in row 2, column 3; then K in row 2, column 4; then A in row 3, column 4, and so on:

A K Q J
Q J A K
J Q K A
K A J Q

Likewise the third possibility allows only one completion:

A K Q J
J Q K A
K A J Q
Q J A K

So that’s it, those are the only two ways to do it with A K Q J in the first row. Any other solution then will have to be what you get if you take one of the A-K-Q-J solutions and permute the ranks. There are 24 such permutations, so there are 48 solutions.

This is an example of a Latin square. In fact the requirement that the diagonals contain all four suits is extra. A Latin square needs only to have all four in each row and column. Or all five or whatever — you can do Latin squares of any size.

Now if you pay attention to both rank and suit, and require each row and each column to contain all four of each, that’s a Graeco-Latin square. Again, that says nothing about the diagonals, but you can extend the requirement to them and still get solutions for squares of size 4.

The ranks have to form a Latin square and so do the suits. Replace A, K, Q, J with H, C, D, S (hearts, clubs, diamonds, spades) in the above squares and those are your possibilities for the suits. There are just two that have H, C, D, S in the top row:

H C D S   H C D S
D S H C   S D C H
S D C H   C H S D
C H S D   D S H C

But you can’t use the first possibility for both the ranks and the suits. Otherwise all the As will be Hs, all the Ks will be Cs, and so on. Likewise you can’t use the second possibility for both. But you can use the first for one and the second for the other, either way around:

AH KC QD JS   AH KC QD JS
QS JD AC KH   JD QS KH AC
JC QH KS AD   KS AD JC QH
KD AS JH QC   QC JG AS KD

And again, any other solutions have to be obtainable from these two by permuting the suits and permuting the ranks. There are 24 × 24 = 576 such permutations, so in total there are 1152 solutions.

Pegs jumping

Matt Parker’s newest Maths Puzzle asks you to provide the shortest solution to a triangular peg jumping puzzle. Start with ten pegs in ten holes arranged in a triangle:

Remove one peg. Now start jumping pegs, checkers style, but in any of six directions. For instance if peg 1 is removed then you can jump peg 4 over peg 2 into position 1, or peg 6 over peg 3 into position 1. The jumped peg is removed. That’s a move, but if you can jump two or more pegs in succession with the same peg (removing them all) that counts as a single move too. Non jumping moves are not allowed. Keep going until you’re left with only one peg, or there are no legal jumps.

There are ten pegs but really only three pegs to consider removing: A corner peg like 1, an edge peg like 2, or the center peg, 5. In each case what’s the best strategy for clearing the board? Can you clear the board, and in how few moves? For bonus points, can you find ways of winning with the last peg left in a given position?

Continue reading “Pegs jumping”

Everyone face down

Here’s another puzzle from Matt Parker and you kind of have to go there and watch the video, I can’t really summarize it here in only a paragraph.

And my solution:

Start with a really simple version of the game: Two cards, not all face down, and we have to get them all face down. If I use o to mean a face up card and x for face down, then we have three initial possibilities:

ox
xo
oo

Having no information about the setup there’s no particular reason to choose one card over the other, so we can just arbitrarily flip the first card:

xx Winner!
oo
xo

At this point you either win, or you know the second card is face up. So flip that.

(won)
ox
xx Winner!

Now either you win, or you know the first card is now face up, so flip that.

(won)
xx Winner!
(won)

So with two cards initially, not all face down, you need up to three flips.

Now three cards, and I’ll show them like this:

xo x
ox x
oo x

xx o

xo o
ox o
oo o

Let’s suppose for the moment the last card is face down, the first three possibilities. Now we have to get the remaining two cards face down, and we know that takes up to three flips: first card, second card, first card.

But the last card could be face up. If so then we need to flip that card, and if the other two cards are face down — the fourth possibility — then we’re done. Otherwise we again need to get the remaining cards face down, requiring three flips.

Since we don’t know whether the last card is face up or not, we have to try all three of these possibilities. So flip first, second, first; then third; then first, second, first. We need up to seven flips.

Moving on to four cards, by the same reasoning, we need up to seven flips to either win or know that the fourth card is face up, one to flip the fourth card and see if that wins it, and if not, up to seven more flips, for a total of fifteen:

first, second, first; then third; then first, second, first
fourth
first, second, first; then third; then first, second, first

And clearly 31 for five cards, 63 for six cards, and so on: 2^n-1 flips for n card.

But all this might look familiar. Remember the Towers of Hanoi? The optimum strategy for moving four disks is to move them in this order:

first, second, first; then third; then first, second, first
fourth
first, second, first; then third; then first, second, first

That’s right… this game is just the Towers of Hanoi in disguise.

Scrabble 46

Here’s a puzzle from Matt Parker:

How many ways, from the 100 standard scrabble tiles, can you choose seven which total 46 points?’ Clarification: for this we’re asking you how many distinct scrabble hands (groups of 7 letters) there are that total exactly 46. So order does not matter and identical letters are indistinguishable.

The distribution of scrabble tiles and points is below. (Eg the letter A is worth 1 point, and there are 9 letter A tiles)

0 points – blank (x2)
1 point – A (x9), E (x12), I (x9), O (x8), U (x4), L (x4), N (x6), S (x4), T (x6), R (x6)
2 points -D (x4), G (x3)
3 points -B (x2), C (x2), M (x2), P (x2)
4 points -F (x2), H (x2), V (x2), W (x2), Y (x2)
5 points -K (x1)
8 points – J (x1), X (x1)
10 points -Q (x1), Z (x1)

Notice that if you have seven tiles adding to 46 then the average tile value is 46/7 which is 6 point something. So you must have at least one of the “big four” tiles: Q, Z, J, and X.

In fact you have to have all four. If you have only three (or fewer) then your highest three tiles can be worth no more than 28 points, so you need 18 points from your other four tiles. But the highest total you can get with four non big four tiles is 5+4+4+4 = 17.

So you need the big four, giving 36 points, and then you need three more tiles totaling 10 points. These can be:

  • 5 + 4 + 1 points — There is 1 way to get 5 points, 5 ways to get 4 points, and 10 ways to get 1 point, so the number of possibilities is 1 times 5 times 10 = 50.
  • 5 + 3 + 2 points — 1 way to get 5 points, 4 ways to get 3 points, 2 ways to get 2 points, number of possibilities is 1 times 4 times 2 = 8.
  • 4 + 4 + 2 points — 5 ways to get the first 4 points, but that leaves only 4 ways to get the next 4, and that gives you each pair of 4-point letters twice, and then there are 2 ways to get 2 points, so in total the number of possibilities is (5 times 4)/2 times 2 = 20.
  • 4 + 3 + 3 points — 5 times (4 times 3)/2 = 30 possibilities.

And that’s all. When I first thought about this puzzle I came up with the above and then realized I’d forgotten about the blanks, but then figured out the blanks can’t be used. If you have the big four plus a blank you need to get 10 points with two of the remaining tiles, and that can’t be done.

So the answer is 50 + 8 + 20 + 30 = 108.

Here they are:

Q Z J X K F A
Q Z J X K F E
Q Z J X K F I
Q Z J X K F L
Q Z J X K F N
Q Z J X K F O
Q Z J X K F R
Q Z J X K F S
Q Z J X K F T
Q Z J X K F U
Q Z J X K H A
Q Z J X K H E
Q Z J X K H I
Q Z J X K H L
Q Z J X K H N
Q Z J X K H O
Q Z J X K H R
Q Z J X K H S
Q Z J X K H T
Q Z J X K H U
Q Z J X K V A
Q Z J X K V E
Q Z J X K V I
Q Z J X K V L
Q Z J X K V N
Q Z J X K V O
Q Z J X K V R
Q Z J X K V S
Q Z J X K V T
Q Z J X K V U
Q Z J X K W A
Q Z J X K W E
Q Z J X K W I
Q Z J X K W L
Q Z J X K W N
Q Z J X K W O
Q Z J X K W R
Q Z J X K W S
Q Z J X K W T
Q Z J X K W U
Q Z J X K Y A
Q Z J X K Y E
Q Z J X K Y I
Q Z J X K Y L
Q Z J X K Y N
Q Z J X K Y O
Q Z J X K Y R
Q Z J X K Y S
Q Z J X K Y T
Q Z J X K Y U
Q Z J X K B D
Q Z J X K B G
Q Z J X K C D
Q Z J X K C G
Q Z J X K M D
Q Z J X K M G
Q Z J X K P D
Q Z J X K P G
Q Z J X F H D
Q Z J X F H G
Q Z J X F V D
Q Z J X F V G
Q Z J X F W D
Q Z J X F W G
Q Z J X F Y D
Q Z J X F Y G
Q Z J X H V D
Q Z J X H V G
Q Z J X H W D
Q Z J X H W G
Q Z J X H Y D
Q Z J X H Y G
Q Z J X V W D
Q Z J X V W G
Q Z J X V Y D
Q Z J X V Y G
Q Z J X W Y D
Q Z J X W Y G
Q Z J X F B C
Q Z J X F B M
Q Z J X F B P
Q Z J X F C M
Q Z J X F C P
Q Z J X F M P
Q Z J X H B C
Q Z J X H B M
Q Z J X H B P
Q Z J X H C M
Q Z J X H C P
Q Z J X H M P
Q Z J X V B C
Q Z J X V B M
Q Z J X V B P
Q Z J X V C M
Q Z J X V C P
Q Z J X V M P
Q Z J X W B C
Q Z J X W B M
Q Z J X W B P
Q Z J X W C M
Q Z J X W C P
Q Z J X W M P
Q Z J X Y B C
Q Z J X Y B M
Q Z J X Y B P
Q Z J X Y C M
Q Z J X Y C P
Q Z J X Y M P

Pythagorean circles

Here’s yet another Catriona Shearer problem:

But let’s start with a related picture, one with only two circles:

Again, the circles have unit radius. What are the dimensions of the rectangle?

The key to figuring this out is that if you have two lines through a point both tangent to a circle, then the line segments from the intersection point to the tangent points are congruent. We know the distance from the top right corner of the rectangle to the top tangent point on the yellow circle is 3. We don’t know the distance from the bottom right corner of the rectangle to the left tangent point on the yellow circle; call it x. Then the length of the diagonal is 3+x. By Pythagoras,

(3+x)^2 = 4^2+(1+x)^2

whose solution is x=2. So the height of the rectangle is 3, its width is 4, and its diagonal is 5: the diagonal and two sides make a 3:4:5 triangle, where 3:4:5 is a Pythagorean triple.

You can do the 3-circle problem the same way; here the length of the diagonal is 5+x, the equation is

(5+x)^2 = 6^2+(1+x)^2

whose solution is x=3/2. The rectangle then is 2.5 by 6 with diagonal 6.5. Those three numbers are in the proportion 5:12:13, another Pythagorean triple!

Coincidence? No. Of course if x is rational then the lengths of the sides and diagonal are in the proportion of a Pythagorean triple. But in general, with n circles, does x have to be rational? You might expect not. However, the solution for n circles is given by

(2n-1+x)^2 = (2n)^2+(1+x)^2

whose solution is

x = \frac{n}{n-1}

So the rectangle height:width:diagonal is

1+\frac{n}{n-1} : 2n : 2n-1+\frac{n}{n-1}

or

\frac{2n-1}{n-1} : \frac{2n(n-1)}{n-1} : \frac{2n(n-1)+1}{n-1}

which is the integer proportion 2n-1 : 2n(n-1) : 2n(n-1)+1, scaled by n-1. That’s a Pythagorean triple, and in particular it’s a triple in which the hypotenuse is one greater than the longer side. For four circles, for example, the triple is 7:24:25 and the rectangle’s dimensions are 7/3 by 8.

Semicircles, semi mysterious

This puzzle by Catriona Shearer has been driving me nuts today:

I stared at a while, didn’t come up with anything good, and finally gave up and started looking at the solutions people were posting. They fell into three categories: Answers with no real attempt to show reasoning; algebraic solutions that were kind of opaque and didn’t really give any insight; and geometric solutions that depended on assertions I couldn’t see a justification for.

I still haven’t seen a solution that makes me particularly happy.

The geometric solutions in particular mostly looked like they assumed the left small semicircle’s base makes a 45° with the large semicircle’s base (or something equivalent). Which it does, but how do you know it does? In particular, it appeared people were assuming the square diagonal and the perpendicular bisector shown below are the same; in this diagram they’re not, because the large “semicircle” is really a semiellipse, but how do you know they do coincide when it’s a semicircle?

The clearest solution posted which I felt didn’t make any unjustified assumptions was Bilal Aydin’s. Here’s my version of it.

Let the radii of the small and large semicircles be r and R. In the following diagram D is the center of the large semicircle, B is the center of the small one on the left, and E is the center of the small one on the right. C is the point where the base of the large semicircle is tangent to the angled semicircle, and radius BC is perpendicular to that base. Since the base of the angled semicircle is a chord of the large one, its perpendicular bisector passes through B and D.

Then BE=2r and BC = r so CE = \sqrt{3}r. Let DE=x=R-r. Now (BD)^2 = r^2+(\sqrt{3}r-x)^2. AB=r, so AD^2 = r^2+r^2+(\sqrt{3}r-x)^2. But AD = R. So

r^2+r^2+(\sqrt{3}r-x)^2 = (r+x)^2

2r^2+3r^2-2\sqrt{3}rx+x^2 = r^2+2rx+x^2

4r^2= 2rx(1+\sqrt{3})

x = 2r/(1+\sqrt{3}) = r(\sqrt{3}-1)

And then R = x+r = \sqrt{3}r. So the large semicircle is three times the area of each small one; the shaded area is 2/3 of the whole.

That works, but it’s very mysterious. Stuff cancels on both sides for no obvious reason. And if you try to figure out CD = \sqrt{3}r-x you find it’s just r, which means triangle BCD is isosceles and the angled semicircle’s base is 45° from the large semicircle’s base. Those seem like things that should be easy to prove geometrically, and yet… how?