Riddler Classic for 27 July 2018 (part 2)

Here’s a way to think about those time symmetric solutions.

Color the squares like this:There’s a 2 by 3 block in each corner, each containing one square of each of the colors red, orange, yellow, green, blue, purple. Now starting from the top left go East, South, West, Northeast, South:You’ve visited one square of each color. Obviously if you started in a different corner and followed a similar path (rotated 90°, 180°, or 270°) you’d visit a different square of each color. Do that from all four corners and you visit 24 of the 25 squares, all but the center one. Of course that’s four paths, not one. But!

The path ends on a purple square. Notice, though, from a purple square you have a legal move to another purple square. From there you can follow the same path (rotated) backwards, ending up on a red square. Now you’ve visited twelve squares.

But now from that red square you can go to the center square, and from there to the red square diagonally opposite.

From there you can follow the path a third time (forward, rotated) to reach a third purple square; from there you can move to the fourth purple square; and from there you can follow the path a fourth time (backwards, rotated) to reach the final red square. And that gives you a time symmetric path visiting all 25 squares. Not only is it time symmetric, but it’s doubly so: the first 12 steps also are time symmetric with a rotation (as are, necessarily, the last 12).

Specifically it gives you the first two time symmetric solutions of the four I mentioned — one if you go Northwest from the first purple square to the second, the other if you go Northeast.

The other two time symmetric solutions are a little more complicated, because they begin with a path that starts on a yellow square and ends on purple:From there you could go to another purple square and then follow a backwards, rotated path that would land you on a yellow square— but then what? You could go to another yellow square, do another forward path and another reversed path, and you’d have a doubly time symmetric solution… but for 24 squares, not 25. But instead, after the jump to the second purple square, you can follow a different path, one that hits the same squares but in a different order, ending on red:And now you can go to the center square, then to the opposite red square, and then follow a path that time reverses the first steps to finish.

What these solutions rely upon is that there’s a color (purple) from which you can move to another square of the same color, and a central square from and to which you can move to another color (red). With a 6 by 6 square, using the same idea with 3 by 3 blocks in each corner, there is no center square to use as a stepping stone. So to get a similar solution you’d need two colors from which you can move to squares of the same colors. Start on (say) red, hit all the colors ending on (say) purple, jump to another purple, reverse the path to get to red, jump to another red, and then reverse everything to finish. But if you check you’ll find there’s only one color from which you can move to another square of the same color. So doubly time symmetric solutions of this sort don’t exist.

In principle there could still be a singly time symmetric solution, where you use 18 colors to color two 3 by 6 blocks. Then follow a path that hits every color once, ending with (say) purple from which you can go to the other purple, then follow the reversed path to finish. But it seems there’s no such path.

Riddler Classic for 27 July 2018

Spoiler for the July 27 fivethirtyeight.com Riddler Classic:

From Renaud Dubedout, a puzzle perfect for doodling during a boring class or meeting, not that I would ever endorse that sort of thing:

Start with an empty 5-by-5 grid of squares, and choose any square you want as your starting square. The rules for moving through the grid from there are strict:

  1. You may move exactly three cells horizontally or vertically, or you may move exactly two cells diagonally.
  2. You are not allowed to visit any cell you already visited.
  3. You are not allowed to step outside the grid.

You win if you are able to visit all 25 cells.

Is it possible to win? If so, how? If not, what are the largest and smallest numbers of squares you can legally visit?

I was out of the country, so I didn’t get a look at this puzzle until its solution had been published. I found a 24-cell solution and about 80% convinced myself 25 cells was impossible, then looked and found out, no, it’s not. In fact there are 12,400 solutions.

Which I proceeded to verify with a Python script. Actually it’s 12,400 if you count reflections and rotations as distinct. If you don’t, though, then I think there are “only” 1806.

Or something like half that, if you don’t count as distinct a solution and its time reversal. That is, a solution starting at square a and ending at square b can be trivially transformed into a solution starting at square b and ending at square a. That means for every solution there’s another solution that’s basically the same… unless of course it’s a solution that is time symmetric, that is, it is its own time reversal.

Consider for instance this solution:

1 17 20 2 14
11 23 5 10 22
19 8 13 18 7
4 16 21 3 15
12 24 6 9 25

Starting from the top left square, it goes East, South, West, Northeast, South… and ends up going (from 20) …South, Northeast, West, South, East. The last twelve directions are the same as the first twelve, in reverse order. If you replace each step number n with 26-n and rotate the square 180°, you get the original solution back again.

There seem to be four such solutions (not counting rotations and reflections). One other also starts in the corner:

1 9 20 2 12
15 23 5 16 22
7 18 13 8 19
4 10 21 3 11
14 24 6 17 25

which has 1 through 6 and 20 through 25 in the same place as above but 7 through 19 rotated 180°. Then there are:

23 15 7 22 14
9 1 18 10 2
6 21 13 5 20
24 16 8 25 17
12 4 19 11 3


23 11 19 22 12
17 1 8 16 2
6 21 13 5 20
24 10 18 25 9
14 4 7 15 3

which are related in the same way.

How about time antisymmetric solutions? For instance, starting with East, South, West, Northeast, South… and ending with …North, Southwest, East, North, West? Nope, none.

Oliver also asks:

If you solved this game and want another game for your next boring event (and who doesn’t?): Can you still win if the grid is 6-by-6?

Exponential growth being what it is, my Python script was a lot slower on this one (in fact it crashed until I realized I could modify it to use a lot less storage) but it eventually came up with 8,250,272 solutions including rotations and reflections; 1,287,875 not including them. It found no time symmetric or time antisymmetric solutions.

Riddler Classic for 29 June 2018

Spoiler for the June 29 fivethirtyeight.com Riddler Classic:

From Jan-Willem Tel, a puzzle of efficient breaking and entering:

You have a gate that requires a passcode to open. There are 10 buttons: the digits 0 to 9. You have forgotten the passcode, but you remember it has four digits. You have no choice but to try them all.

Since there are 10^4 = 10,000 four-digit passcodes, you might think this would take you 40,000 button presses to guarantee an opened gate. However, this gate’s keypad never resets: The gate opens as soon as the last four buttons you’ve pressed are the correct code, so you can be more efficient. For example, you can try two different codes by pressing just five buttons: The combination “12345” tries both “1234” and “2345.” Of course, pressed for time, you want to press as few buttons as possible while still trying different codes and eventually opening the gate.

So the question is: What’s the smallest number of buttons you need to press to make sure you open the gate — i.e., that you’ve tried every possible four-digit combination?

Extra credit: How do things change if you didn’t remember the passcode’s length?

I thought about this at the time, but didn’t come up with anything worth writing about. Having now seen the solutions I went back to it.

The site’s a little terse about the proof that the answer’s 10003. Let’s see if I can clarify it. Suppose you’re building up a string of digits to enter, you have say 3141 digits so far and you’re about to add the 3142nd. Call the last 4 digits of the string you already have a, b, c, and d:

zyxwv… (3133 digits) …abcd

and you’re going to add a new digit, call it e. What you want, if possible, is for the last four digits of the result, bcde,  to be unique, not having occurred already. That is, you’d like each four digit combination to occur once and only once. That means you want each three digit combination to occur ten times, followed by a unique one of the ten digits. (Mostly. I’ll get to that.)

So when you go to add the 3142nd digit, will there be one available that will do that? Well, if bcd has already occurred ten times before this, with each of the ten digits following it, then no. But in that case the bcd occurring at the end is the 11th instance of bcd. Meaning the abcd at the end must be the second (or later) occurrence of that string. Meaning that if adding a digit is impossible without creating a duplicate, then a duplicate already exists. If there are no duplicates already, then you can add a digit without creating a duplicate. The only exception to this argument is if the string both starts and ends with bcd; then the terminating bcd can be the eleventh one without abcd being a duplicate, and then you can’t add a digit.

That means you can always add a digit without creating a duplicate four digit code, until you have a string that contains every code, and that string has to end with the same three digits you start with. Each digit from the fourth on ends a new unique code, of which there are 10,000, so the string you end up with will be 10,003 digits long.

Or 10^n+(n-1), for n-digit codes.

I wrote a Python script to generate these strings. It starts with a string of length n (all zeros for instance), then repeatedly tries to add a digit to that which will make a new code: first 0, then 1, then 2, and so on, until it succeeds, after which it goes back and tries to add another digit. For n = 2:

001   # 01 is new
0010  #10 is new
00102  #02 is new
001020  #20 is new

0010203040506070809  #09 is new
00102030405060708090  #90 is new

But here we’re stuck, because we’ve used 0 11 times already and we can’t add a new digit without creating a duplicate. The script’s not that smart, it just tries 0 through 9 and finds none of them work. So now it gets rid of the last digit in the string (the 0) and tries the next one:

00102030405060708091  #91 is new
001020304050607080911  #11 is new
0010203040506070809112  #12 is new

and so on. Obviously if it gets stuck with a string ending in 9 there isn’t a next digit to try instead, so it has to backtrack further. But eventually it finds the 101 digit solution


and it works the same way for larger values of n. If you’re skeptical the solution has to end with the same n-1 digits it starts with, here’s the 10,003 digit solution it finds for n=4, if it starts with the somewhat arbitrary four digit string “3141”:


Yep, it ends with 314. Go ahead, look for the last four digits of your Social Security number, they’re there.


Riddler Express for 22 June 2018

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

From Dave Moran, this is the final boarding call for flight RDLR 100:

Michelle decided to get some extra exercise at the airport by walking toward her departure gate at her normal pace, but on a lengthy moving walkway … going the wrong way. Gotta get those steps in.

After going 100 meters (that is, getting 100 meters closer to her departure gate), Michelle dropped her boarding pass onto the walkway. But she didn’t notice at first and continued walking toward her gate. After walking another 90 seconds, she finally realized that she had dropped her boarding pass. She then immediately turned around and jogged in the direction of the walkway’s movement. Michelle’s jogging pace is exactly twice as fast as her walking pace. She caught up with her boarding pass 10 meters from the start of the moving walkway.

How fast does the walkway move?

You could set this up as a complicated algebra problem, or you can be lazy enough to be clever.

Think about this from the boarding pass’s point of view. As far as it’s concerned it’s sitting still while Michelle walks at her normal walking speed away from it for 90 seconds, and then jogs back to it at twice that speed. She’s covering the same distance both times, so it takes her 45 seconds to return to where she dropped the pass after she turns around; that is, the pass is lying on the walkway for 135 seconds.

Now, from the airport’s point of view, the pass is moving at the speed of the walkway and it covers 90 meters in those 135 seconds. So that speed is 90 / 135 = 2/3 meters per second.


Riddler Classic for 8 June 2018

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

From Ben Gundry via Eric Emmet, find and replace with a twist:

Riddler Nation has been enlisted by the Pentagon to perform crucial (and arithmetical) intelligence gathering. Our mission: decode two equations. In each of them, every different letter stands for a different digit. But there is a minor problem in both equations.

In the first equation, letters accidentally were smudged on their clandestine journey to a safe room within Riddler Headquarters and are now unreadable. (These are represented with dashes below.) But we know that all 10 digits, 0 through 9, appear in the equation.

What digits belong to what letters, and what are the dashes?

In the second equation, our mathematical spies have said that one of the letters in the equation is wrong. But they can’t remember which one. Which is it?

First puzzle:

The smudged letter business seems to be an obvious red herring; all 10 digits are used, but 6 letters appear and 4 dashes, so each dash is a different letter and might as well be replaced by four different letters, say: EXMREEK + EHKREKK = AKBHCXDE. Right away we know A = 1.

2E > 9 and 2K\mod 10 = E, so E = 6\textrm{ or } 8. But 2E\mod 10 is K = X-1 or X = K-1. So E = 6 with K = 3 and X = 2. D = 9.

Now 2+H\ge 9, so H = 7 or H = 8.

1+2R\mod 10 = C. The only possibility still available is R = 7 and C = 5 with H = 8. The two digits left are 0 and 4 and those are indeed what B and M work out to respectively. The sum is 6247663+6837633=13085296.

Second puzzle:

We’ll assume everything’s okay until we hit a contradiction. By exactly the same logic as before E = 1, Y= 6, D = 3. In column 7, D+Y=9 so T=9\textrm{ or }0. Since in column 5 2B\mod{10} cannot be 1, there must be a carry into that column, meaning T=9.

But in column 9, K+D\mod{10}=T so K=6 which is not available.

If one of the letters column 5 is wrong then there could be no carry into that column, in which case we could have T = 0, and then K=7. But from column 4 we’d still need B = 6\textrm{ or }7 neither of which is possible. So the problem lies elsewhere.

Maybe a letter in column 9 is wrong. Then R=0, and B=5. H=7. If there’s a carry into column 8 then M+7=P, which doesn’t work, so there’s no carry and M+6=P means M=2, P=8. We’re left with K=4 which gives the incorrect sum 695513243+673596633=1369109896; if the first two numbers are right the sum should be 1369109876. Or if the first number is right and the sum is right the second number should be 673596653. Or if the second number is right and the sum is right the first number should be 695513263. We can’t determine which letter is incorrect.

This doesn’t rule out other possibilities, such as that one of the letters in column 7 or column 10 is wrong.

Riddlers for 4 May 2018

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


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?


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.


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

Let n_i be the number of coconuts found by the ith 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)

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


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


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

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.


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).