Distancing uniquely

3 June 202030 May 2020 by Rich Holmes, posted in Uncategorized

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 ->	1		2		3
size v	max	solutions	max	solutions	max	solutions
2	2	1	2	2	3	1
3	2	2	3	5	4	20
4	3	1	4	23	6	36
5	3	3	5	35	7	4223
6	3	7	6	2
7	4	1	7	1
8	4	5	7	3350
9	4	13	8	547
10	4	30	9	52
11	4	55
12	5	2
13	5	11
14	5	34
15	5	78
16	5	160
17	5	292
18	6	4
19	6	12
20	6	40

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:

Pegs jumping

6 May 20201 May 2020 by Rich Holmes, posted in Games

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 →

Riddlers for 4 May 2018

7 May 20186 May 2018 by Rich Holmes, posted in Numbers, Riddler

Spoilers for last week’s fivethirtyeight.com Riddler Express and Classic:

Express

From Charlie Drinnan, find the letters’ numbers:

If A, B, C, D and E are all unique digits, what values would work with the following equation?

ABC,CDE × 4 = EDC,CBA

No problem. $A$ must be even, and $4A < 10$ , so $A=2$ . Then $4AB < 100$ so $B < 5$ , and $BA\mod 4 = 0$ so $B = 1$ and $E = 8$ , or $B = 3$ and $E = 9$ . But $4E \mod 10 = A = 2$ so $E = 8$ .

Now $4D+3 \mod 10 = B = 1$ so $4D \mod 10 = 8$ . $D\ne 2$ so $D = 7$ .

Finally $4C+3 \mod 10 = C$ or $3C\mod 10 = 7$ , so $C = 9$ .

$219,978 \times 4= 879,912$ .

Classic

This is fairly mechanical although I tripped up several times on the way.

Let $n_i$ be the number of coconuts found by the $i$ th pirate, and $n_8$ be the number of coconuts found in the morning. $n_8$ is divisible by 7 so write $n_8 = 7m_8$ .

But $n_8$ is what was left when the seventh pirate discarded one coconut out of $n_7$ and hid one seventh of the rest, so $n_7 = (7/6)n_8+1 = (7/6)(7m_8)+1$ . For that to be an integer $m_8$ must be a multiple of 6, so write $m_8 = 6m_7$ . Then $n_7 = 7^2m_7+1$ .

Now $n_6 = (7/6)n_7+1 = (7/6)(7^2m_7+1)+1$ . For integer value, $7^2m_7\mod 6 = m_7\mod 6 = 5$ , so write $m_7 = 6m_6+5$ . Then $n_6 = (7/6)(7^2(6m_6+5)+1)+1 = 7^3m_6+288$ .

You see how this goes.

$n_5 = (7/6)n_6+1 = (7/6)(7^3m_6+288)+1$ . For integer value, $m_6\mod 6 = 0$ , so write $m_6 = 6m_5$ . Then $n_5 = (7/6)(7^3(6m_5)+288))+1 = 7^4m_5+337$ .

$n_4 = (7/6)n_5+1 = (7/6)(7^4m_5+337)+1$ . For integer value, $m_5\mod 6 = 5$ , so write $m_5 = 6m_4+5$ . Then $n_4 = (7/6)(7^4(6m_4+5)+337)+1 = 7^5m_4+14400$ .

$n_3 = (7/6)n_4+1 = (7/6)(7^5m_4+14400)+1$ . For integer value, $m_4\mod 6 = 0$ , so write $m_4 = 6m_3$ . Then $n_3 = (7/6)(7^5(6m_3)+14400)+1 = 7^6m_3+16801$ .

$n_2 = (7/6)n_3+1 = (7/6)(7^6m_3+16801)+1$ . For integer value, $m_6\mod 6 = 5$ , so write $m_3 = 6m_2+5$ . Then $n_2 = (7/6)(7^6(6m_2+5)+16801)+1 = 7^7m_2+705888$ .

$n_1 = (7/6)n_2+1 = (7/6)(7^7m_2+705888)+1$ . For integer value, $m_2\mod 6 = 0$ , so write $m_2 = 6m_1$ . Then $n_1 = (7/6)(7^7(6m_1)+705888)+1 = 7^8m_1+823537$ . The smallest value corresponds to $m_1 = 0$ so $n_1^{min} = 823537$ .

These pirates were either very sleepy, or incredibly quick at counting coconuts.

Riddler Classic for 23 March 2018 (part 2)

7 April 20188 April 2018 by Rich Holmes, posted in Numbers, Riddler

We’ve seen a generalization of the problem to multiplicative factors other than 2 and bases other than 10. A third generalization would be to shift more than one digit.

Take a positive integer $j$ in base $b$ and move its last $m$ digits to the front. What is the smallest $j$ such that when you do this, the result $k$ is exactly $p$ times $j$ (where $p$ is in the range $[2,b-1 ]$ )?

Let $j= b^m \times y+x$ , where $b^{m-1}\le x< b^m$ . So the digits of $x$ are the final $m$ digits of $j$ and the initial $m$ digits of $k$ , and the digits of $y$ are the remaining digits of both. Let $n$ be the number of digits in $y$ . Then we require

$p(b^my+x)= b^nx+y$ .

Solving, $(pb^m-1)y=(b^n-p)x$ or

$y= \frac{b^n -p}{pb^m-1}x .$

Now let $g=\gcd(pb^m-1,x)$ and let $w=x/g$ , $v=(pb^m-1)/g$ . Then

$y= \frac{b^n-p}{v}w$

and since $v$ and $w$ are relatively prime, we must have

$b^n=p\mod v$ .

So we must calculate $pb^m-1$ and then, for each possible value of $x$ , obtain $v$ and look for the least $n$ that satisfies the above relation. (The minimal value of $x$ is in fact not $b^{m-1}$ but $pb^{m-1}$ , since there can be no carry to an additional digit when $j$ is multiplied by $p$ .) Then we can compute $y$ , and verify that it does indeed have $n$ digits. The smallest such $y$ and associated $x$ solve the problem.

If $(pb^m-1)$ is prime, then $v = (pb^m-1)$ for all possible $x$ and the smallest $k$ results when $x=pb^{m-1}$ . But if $(pb^m-1)$ has a common factor with some $x$ , then $v$ is some factor of $(pb^m-1)$ . Generally $n$ , the number of digits in $y$ , is on the order of $v$ , so when $(pb^m-1)$ is prime the solution tends to be many orders of magnitude larger than when it is not.

For instance, consider $p=3$ and $b=10$ . For $m=2$ , $(pb^m-1)=299=13\times 23$ . In that case some values of $x$ have a common factor with $(pb^m-1)$ . E.g., $x=46$ gives

$y= \frac{10^n-3}{13}w$

where

$10^n=3\mod 13$ .

The solution is $n=4$ , leading to

$j=153846$ , $k=3j=461538$ .

But for $m=1$ , $(pb^m-1)=29$ is prime. The number of digits in $y$ then turns out to be 27, and

$j=1034482758620689655172413793$ .

And for $m=3$ , $(pb^m-1)=2999$ is prime too. We end up with the 1499 digit solution

$j = 100033344448149383127709236412137379126375458486162054018006\\ 0020006668889629876625541847282427475825275091697232410803601200\\ 4001333777925975325108369456485495165055018339446482160720240080\\ 0266755585195065021673891297099033011003667889296432144048016005\\ 3351117039013004334778259419806602200733577859286428809603201067\\ 0223407802600866955651883961320440146715571857285761920640213404\\ 4681560520173391130376792264088029343114371457152384128042680893\\ 6312104034678226075358452817605868622874291430476825608536178726\\ 2420806935645215071690563521173724574858286095365121707235745248\\ 4161387129043014338112704234744914971657219073024341447149049683\\ 2277425808602867622540846948982994331443814604868289429809936645\\ 5485161720573524508169389796598866288762920973657885961987329109\\ 7032344114704901633877959319773257752584194731577192397465821940\\ 6468822940980326775591863954651550516838946315438479493164388129\\ 3764588196065355118372790930310103367789263087695898632877625875\\ 2917639213071023674558186062020673557852617539179726575525175058\\ 3527842614204734911637212404134711570523507835945315105035011670\\ 5568522840946982327442480826942314104701567189063021007002334111\\ 3704568189396465488496165388462820940313437812604201400466822274\\ 0913637879293097699233077692564188062687562520840280093364454818\\ 2727575858619539846615538512837612537512504168056018672890963654\\ 5515171723907969323107702567522507502500833611203734578192730910\\ 3034344781593864621540513504501500500166722240746915638546182060\\ 6868956318772924308102700900300$ .

If you’d asked me to guess, before I worked any of this out, the order of magnitude of the smallest positive integer which is exactly tripled when you move the last three digits to the front, I’m pretty sure I would have seriously underestimated it.

Riddler Classic for 23 March 2018

26 March 20185 April 2018 by Rich Holmes, posted in Numbers, Riddler

Spoiler for last week’s fivethirtyeight.com Riddler Classic:

From Joseph Converse, a puzzle of digital manipulation:

Imagine taking a number and moving its last digit to the front. For example, 1,234 would become 4,123. What is the smallest positive integer such that when you do this, the result is exactly double the original number? (For bonus points, solve this one without a computer.)

One way

Write the number (call it $m$ ) as $10y+x$ , where $x<10$ ; for instance, for 1,234, $y=123$ and $x=4$ . Let $n$ be the number of digits in $y$ ; then the number resulting from moving the last digit to the front is $10^nx+y$ . We want $2(10y+x)=10^nx+y$ .

Solving, we get $y = (10^n-2)x/19$ . Now, 19 is prime and $x<10$ so isn’t a multiple of 19, and therefore $(10^n-2)$ must be, that is, $10^n\mod 19 = 2$ .

Going ahead and doing the long division ― that is, dividing 100, 1000, 10000… by 19 until a remainder of 2 is found ― we get $n=17$ ; $(10^{17}-2)/19 = 5263157894736842$ . That has 16 digits, so $x=1$ won’t work; $x=2$ will give us a 17-digit $y=10526315789473684$ , though. So the smallest number that works is $m = 105263157894736842 = 210526315789473684/2$ .

Another way

We require $2m$ to have the same number of digits as $m$ , and that means the first digit of $2m$ can’t be 1. So let’s try making it 2. Then that’s also the last digit of $m$ .

Now, the last digit of $2m$ is 4, which is also the second to last digit of $m$ . And then the second to last digit of $2m$ is 8, which must be the third to last digit of $m$ . Then the third to last digit of $2m$ is 6, with a carry. That means the fourth to last digit of $m$ is 6 and the fourth to last digit of $2m$ is 3, with a carry.

And so on, until we reach a place where the digit of $m$ is 1 and $2m$ is 2 without a carry. Stop there. Follow that procedure and you get $n = 105263157894736842$ as before.

Except we don’t know that this is the smallest answer. We need to do the same with last digit of $m$ running from 3 to 9. In fact (and as you’d expect having seen the other method) this is the smallest.

I’m rather surprised the second way didn’t occur to me sooner; it seems a good deal more obvious in retrospect. Then again, had I done it first I think I might’ve looked at the size of the result and been unconfident I hadn’t overlooked something that might give a smaller answer. The first method confirms it and makes it more clear, I think, that this really is the minimum. It also provides the insight that the answer is not just a mysterious sequence of digits but is connected with the decimal representation of 1/19.

Triple?

Instead of moving the digit to get multiplication by 2, what about by 3? Or by $k$ generally? Adapting either method, one finds moving the last digit of 1034482758620689655172413793 to the front gives triple that number. For quadrupling we get a much smaller answer: 102564 = 410256/4. For quintupling we encounter for the first time the necessity of checking all possible last digits, not just the minimum one: Using 5 for the last digit we find 102040816326530612244897959183673469387755, but with 7 we get 142857! This is related to the fact that if you try the first method, you need $y = (10^n-5)x/49$ , and 49 is not prime, so when $x=7$ we need $10^n \mod 7 = 5$ rather than $10^n \mod 49 = 5$ .

Here’s a table for $k$ = 1 through 9. I am glad the Riddler puzzle didn’t ask for 6 (by hand)… I did these with a spreadsheet.

1	1
2	105263157894736842
3	1034482758620689655172413793
4	102564
5	142857
6	1016949152542372881355932203389830508474576271186440677966
7	1014492753623188405797
8	1012658227848
9	10112359550561797752808988764044943820224719

All your base

Another generalization of the original puzzle is to do it in base $b$ instead of base 10. There’s no solution in binary, as you can figure out by trying to adapt either method above, or just by noting that doubling a number in binary means appending a 0 to the right end, so you can’t double a number and get a number with the same number of binary digits (bits). In base 3, starting with final digit 2 for $m$ , the final digit for $2m$ is 1 with a carry of 1; 1 for the next digit of $m$ gives 0 for the next digit of $2m$ with a carry; 0 for $m$ gives 1 for $2m$ ; 1 for $m$ gives 2 for $2m$ and we’re done: $1012_3 = 2101_3/2$ . In decimal, that’s 32 and 64. (In higher bases we need to check last digits from 2 to $b-1$ .) Alternatively, we want $y = (3^n-2)x/5$ and so require $3^n \mod 5 = 2$ . $n = 3$ works and then $y = 5x$ . So with $x = 2$ , $y = 10 = 101_3$ and $m = 1012_3$ .

In all bases from 3 through 10:

3	1012
4	102
5	13
6	1031345242
7	103524563142
8	25
9	10467842
10	105263157894736842

Edit to add:

And if this Python script is bug free, then

$\mathrm{10179b72334c73ad1496e2dbd2c4365203047e46699e76b293dd5c8b5986ca406090d8cd44}\\ \mathrm{ded7537cbba27b41da580c131c2ab89cebea70a88550783c5b119263956824ae8e5e1621aa_{15}}$

is the smallest base 15 number which is multiplied by (decimal) 10 when the last digit is moved to the front. At 148 digits, it’s the longest such number for all bases up to 16 and all factors up to (base-1).

Share this:

Like this:

Share this:

Like this:

Express

Classic

Share this:

Like this:

Share this:

Like this:

One way

Another way

Triple?

All your base

Share this:

Like this: