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.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s