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.

Advertisements

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

and

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:

00
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

001020304050607080911213141516171819223242526272829334353637
38394454647484955657585966768697787988990

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”:

314100001001100200021003000310040004101011101200121013001310
140014110201021103010311040104111120112111301131114011412020
212030203120402041212130213121402141303031304030413131403142
002200320042012201320142102210321042112211321142202220322042
212221322142300230123022303230423102311231223132314300330043
013301431033104311331143202320332043212321332143302330333043
312331333144002400340044012401340144102410341044112411341144
202420342044212421342144302430343044312431343145000500150025
003500450105011501250135014510051015102510351045110511151125
113511452005201520252035204521052115212521352145300530153025
303530453105311531253135314600060016002600360046010601160126
013601461006101610261036104611061116112611361146200620162026
203620462106211621262136214630063016302630363046310631163126
313631470007001700270037004701070117012701370147100710171027
103710471107111711271137114720072017202720372047210721172127
213721473007301730273037304731073117312731373148000800180028
003800480108011801280138014810081018102810381048110811181128
113811482008201820282038204821082118212821382148300830183028
303830483108311831283138314900090019002900390049010901190129
013901491009101910291039104911091119112911391149200920192029
203920492109211921292139214930093019302930393049310931193129
313931502050215030503151205121513051315220522152305231532053
215330533154005401541054115420542154305431550055015510551155
205521553055315600560156105611562056215630563157005701571057
115720572157305731580058015810581158205821583058315900590159
105911592059215930593160206021603060316120612161306131622062
216230623163206321633063316400640164106411642064216430643165
006501651065116520652165306531660066016610661166206621663066
316700670167106711672067216730673168006801681068116820682168
306831690069016910691169206921693069317020702170307031712071
217130713172207221723072317320732173307331740074017410741174
207421743074317500750175107511752075217530753176007601761076
117620762176307631770077017710771177207721773077317800780178
107811782078217830783179007901791079117920792179307931802080
218030803181208121813081318220822182308231832083218330833184
008401841084118420842184308431850085018510851185208521853085
318600860186108611862086218630863187008701871087118720872187
308731880088018810881188208821883088318900890189108911892089
218930893190209021903090319120912191309131922092219230923193
209321933093319400940194109411942094219430943195009501951095
119520952195309531960096019610961196209621963096319700970197
109711972097219730973198009801981098119820982198309831990099
019910991199209921993099322223223322402241224222432250225122
522253226022612262226322702271227222732280228122822283229022
912292229323233323402341234223432350235123522353236023612362
236323702371237223732380238123822383239023912392239324032413
242324332440244124422443245024512452245324602461246224632470
247124722473248024812482248324902491249224932503251325232533
254025412542254325502551255225532560256125622563257025712572
257325802581258225832590259125922593260326132623263326402641
264226432650265126522653266026612662266326702671267226732680
268126822683269026912692269327032713272327332740274127422743
275027512752275327602761276227632770277127722773278027812782
278327902791279227932803281328232833284028412842284328502851
285228532860286128622863287028712872287328802881288228832890
289128922893290329132923293329402941294229432950295129522953
296029612962296329702971297229732980298129822983299029912992
299333340334133423343335033513352335333603361336233633370337
133723373338033813382338333903391339233933440344134423443345
034513452345334603461346234633470347134723473348034813482348
334903491349234933540354135423543355035513552355335603561356
235633570357135723573358035813582358335903591359235933640364
136423643365036513652365336603661366236633670367136723673368
036813682368336903691369236933740374137423743375037513752375
337603761376237633770377137723773378037813782378337903791379
237933840384138423843385038513852385338603861386238633870387
138723873388038813882388338903891389238933940394139423943395
039513952395339603961396239633970397139723973398039813982398
339903991399239934040414042404340504051405240534060406140624
063407040714072407340804081408240834090409140924093414142414
341504151415241534160416141624163417041714172417341804181418
241834190419141924193424243425042514252425342604261426242634
270427142724273428042814282428342904291429242934343504351435
243534360436143624363437043714372437343804381438243834390439
143924393444044414442444344504451445244534460446144624463447
044714472447344804481448244834490449144924493454045414542454
345504551455245534560456145624563457045714572457345804581458
245834590459145924593464046414642464346504651465246534660466
146624663467046714672467346804681468246834690469146924693474
047414742474347504751475247534760476147624763477047714772477
347804781478247834790479147924793484048414842484348504851485
248534860486148624863487048714872487348804881488248834890489
148924893494049414942494349504951495249534960496149624963497
049714972497349804981498249834990499149924993505051505250535
060506150625063507050715072507350805081508250835090509150925
093515152515351605161516251635170517151725173518051815182518
351905191519251935252535260526152625263527052715272527352805
281528252835290529152925293535360536153625363537053715372537
353805381538253835390539153925393544054415442544354505451545
254535460546154625463547054715472547354805481548254835490549
154925493554055415542554355505551555255535560556155625563557
055715572557355805581558255835590559155925593564056415642564
356505651565256535660566156625663567056715672567356805681568
256835690569156925693574057415742574357505751575257535760576
157625763577057715772577357805781578257835790579157925793584
058415842584358505851585258535860586158625863587058715872587
358805881588258835890589158925893594059415942594359505951595
259535960596159625963597059715972597359805981598259835990599
159925993606061606260636070607160726073608060816082608360906
091609260936161626163617061716172617361806181618261836190619
161926193626263627062716272627362806281628262836290629162926
293636370637163726373638063816382638363906391639263936440644
164426443645064516452645364606461646264636470647164726473648
064816482648364906491649264936540654165426543655065516552655
365606561656265636570657165726573658065816582658365906591659
265936640664166426643665066516652665366606661666266636670667
166726673668066816682668366906691669266936740674167426743675
067516752675367606761676267636770677167726773678067816782678
367906791679267936840684168426843685068516852685368606861686
268636870687168726873688068816882688368906891689268936940694
169426943695069516952695369606961696269636970697169726973698
069816982698369906991699269937070717072707370807081708270837
090709170927093717172717371807181718271837190719171927193727
273728072817282728372907291729272937373807381738273837390739
173927393744074417442744374507451745274537460746174627463747
074717472747374807481748274837490749174927493754075417542754
375507551755275537560756175627563757075717572757375807581758
275837590759175927593764076417642764376507651765276537660766
176627663767076717672767376807681768276837690769176927693774
077417742774377507751775277537760776177627763777077717772777
377807781778277837790779177927793784078417842784378507851785
278537860786178627863787078717872787378807881788278837890789
178927893794079417942794379507951795279537960796179627963797
079717972797379807981798279837990799179927993808081808280838
090809180928093818182818381908191819281938282838290829182928
293838390839183928393844084418442844384508451845284538460846
184628463847084718472847384808481848284838490849184928493854
085418542854385508551855285538560856185628563857085718572857
385808581858285838590859185928593864086418642864386508651865
286538660866186628663867086718672867386808681868286838690869
186928693874087418742874387508751875287538760876187628763877
087718772877387808781878287838790879187928793884088418842884
388508851885288538860886188628863887088718872887388808881888
288838890889188928893894089418942894389508951895289538960896
189628963897089718972897389808981898289838990899189928993909
091909290939191929193929293939440944194429443945094519452945
394609461946294639470947194729473948094819482948394909491949
294939540954195429543955095519552955395609561956295639570957
195729573958095819582958395909591959295939640964196429643965
096519652965396609661966296639670967196729673968096819682968
396909691969296939740974197429743975097519752975397609761976
297639770977197729773978097819782978397909791979297939840984
198429843985098519852985398609861986298639870987198729873988
098819882988398909891989298939940994199429943995099519952995
399609961996299639970997199729973998099819982998399909991999
299944445444644474448444944554456445744584459446544664467446
844694475447644774478447944854486448744884489449544964497449
844994545464547454845494555455645574558455945654566456745684
569457545764577457845794585458645874588458945954596459745984
599464647464846494655465646574658465946654666466746684669467
546764677467846794685468646874688468946954696469746984699474
748474947554756475747584759476547664767476847694775477647774
778477947854786478747884789479547964797479847994848494855485
648574858485948654866486748684869487548764877487848794885488
648874888488948954896489748984899494955495649574958495949654
966496749684969497549764977497849794985498649874988498949954
996499749984999555565557555855595566556755685569557655775578
557955865587558855895596559755985599565657565856595666566756
685669567656775678567956865687568856895696569756985699575758
575957665767576857695776577757785779578657875788578957965797
579857995858595866586758685869587658775878587958865887588858
895896589758985899595966596759685969597659775978597959865987
598859895996599759985999666676668666966776678667966876688668
966976698669967676867696777677867796787678867896797679867996
868696877687868796887688868896897689868996969776978697969876
988698969976998699977778777977887789779877997878797888788978
9878997979887989799879998888988998989999314

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

 

Power trip (part 2)

That proof that e^a>a^e for any positive a\ne e relies on \ln(e)=1, so doesn’t generalize to anything nearly as simple relating a^b to b^a. But let’s see what we can do.

Here’s an inequality which, if you’re like me, looks pretty mysterious:

\displaystyle b>\frac{b-a}{\ln(b/a)}>a for a and b>a positive real numbers.

I mean, the difference between a and b doesn’t “know” anything about a or b, right? And neither does their ratio. But the difference over the log of the ratio is always between a and b? Weird!

(Okay, maybe you’re not so easily impressed, since if you know b-a and b/a you can get a and b. Fine. I think it’s mysterious anyway.)

Well, let’s consider a function f(x) with derivative df(x)/dx = f'(x) monotonically decreasing (we could do increasing too, similarly). Let a and b>a be in the range where f(x) and f'(x) exist and f'(x)>0. Then

\displaystyle \int_a^b f'(x)dx = f(b)-f(a)

But that integral is the area under the curve from a to b and so

\displaystyle f'(a)(b-a)>f(b)-f(a)>f'(b)(b-a).

Then (b-a)>[f(b)-f(a)]/f'(a) and [f(b)-f(a)]/f'(b)> (b-a) or

\displaystyle \frac{f(b)-f(a)}{f'(b)}> (b-a)>\frac{f(b)-f(a)}{f'(a)}.

But that makes sense given the definition of the derivative and the monotonic property of f'(x); with a little thought you could’ve written this down directly. As obvious as it is, it takes a decidedly less obvious form if you specify f(x) = \ln(x), f'(x) = 1/x, which gives

\displaystyle b\ln(b/a)>(b-a)>a\ln(b/a)

or the formerly mysterious

\displaystyle b>\frac{b-a}{\ln(b/a)}>a QED.

I called the original post “Power trip” and this one “Power trip (part 2)”, and there haven’t been any powers here. Sorry. Here:

\displaystyle a\ln(b/a) < b-a < b\ln(b/a)

so

\displaystyle (b/a)^a < e^{b-a} < (b/a)^b.

That form is… neither obvious nor interesting, though. Unless a=e in which case the left part is

\displaystyle (b^e)/(e^e) < (e^b)/(e^e)

or

\displaystyle b^e<e^b

which is where we came in.

Power trip

Here’s a mathematical paper of which I can smugly say I understood every word.

Ha ha. No, seriously, I like it. A visual proof that e^\pi>\pi^e.

But as Math with Bad Drawings pointed out someone else pointed out, the proof doesn’t depend on \pi but can be generalized to any number > e, and as Math with Bad Drawings pointed out, a similar proof works for any positive number < e. That is, for all a > 0 and a\ne e, e^a>a^e.

Proof here if you don’t want to click through to MwBD:

 

If a > e,

\displaystyle \frac{1}{e}(a-e) = \frac{a}{e}-1 > \int_e^a \frac{1}{x}dx = \ln(a)-\ln(e) = \ln(a)-1

so

\displaystyle \frac{a}{e} > \ln(a)

or

\displaystyle a > \ln(a^e)

or

\displaystyle e^a > a^e

and similarly, if b < e,

\displaystyle \frac{1}{e}(e-b) = 1-\frac{b}{e} < \int_b^e \frac{1}{x}dx = \ln(e)-\ln(b) = 1-\ln(b)

so

\displaystyle \frac{b}{e} > \ln(b)

or

\displaystyle b > \ln(b^e)

or

\displaystyle e^b > b^e

QED

 

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.