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