Consider an answering machine with remote inquiry facility, where you can call the answering machine and enter a 4 digit passcode into your telephone keypad, so you can listen to the messages from anywhere you like. Many of these machines will let you in if you enter the correct consecutive sequence of digits, regardless of what preceded that sequence.

Example: Passcode is 1234.

if you feed the machine 1234, you're in.
if you feed the machine 01234, you're in.
if you feed the machine 0121234, you're in.
if you feed the machine 94129838701234, you're in.

To brute-force hack the machine, you could try all numbers from 0000 to 9999, sending 40000 sounds across the wire. But since you are a smart hacker, you see that there's room for optimization. What is the shortest series of digits you have to send to the answering machine in order to break the code in any case?

(In reply to de Bruijn sequence by Kenny)

Apparently the forum software didn't like the long string:

0000100020003000400050006000700080009001
1001200130014001500160017001800190021002
2002300240025002600270028002900310032003
3003400350036003700380039004100420043004
4004500460047004800490051005200530054005
5005600570058005900610062006300640065006
6006700680069007100720073007400750076007
7007800790081008200830084008500860087008
8008900910092009300940095009600970098009
9010102010301040105010601070108010901110
1120113011401150116011701180119012101220
1230124012501260127012801290131013201330
1340135013601370138013901410142014301440
1450146014701480149015101520153015401550
1560157015801590161016201630164016501660
1670168016901710172017301740175017601770
1780179018101820183018401850186018701880
1890191019201930194019501960197019801990
2020302040205020602070208020902110212021
3021402150216021702180219022102220223022
4022502260227022802290231023202330234023
5023602370238023902410242024302440245024
6024702480249025102520253025402550256025
7025802590261026202630264026502660267026
8026902710272027302740275027602770278027
9028102820283028402850286028702880289029
1029202930294029502960297029802990303040
3050306030703080309031103120313031403150
3160317031803190321032203230324032503260
3270328032903310332033303340335033603370
3380339034103420343034403450346034703480
3490351035203530354035503560357035803590
3610362036303640365036603670368036903710
3720373037403750376037703780379038103820
3830384038503860387038803890391039203930
3940395039603970398039904040504060407040
8040904110412041304140415041604170418041
9042104220423042404250426042704280429043
1043204330434043504360437043804390441044
2044304440445044604470448044904510452045
3045404550456045704580459046104620463046
4046504660467046804690471047204730474047
5047604770478047904810482048304840485048
6048704880489049104920493049404950496049
7049804990505060507050805090511051205130
5140515051605170518051905210522052305240
5250526052705280529053105320533053405350
5360537053805390541054205430544054505460
5470548054905510552055305540555055605570
5580559056105620563056405650566056705680
5690571057205730574057505760577057805790
5810582058305840585058605870588058905910
5920593059405950596059705980599060607060
8060906110612061306140615061606170618061
9062106220623062406250626062706280629063
1063206330634063506360637063806390641064
2064306440645064606470648064906510652065
3065406550656065706580659066106620663066
4066506660667066806690671067206730674067
5067606770678067906810682068306840685068
6068706880689069106920693069406950696069
7069806990707080709071107120713071407150
7160717071807190721072207230724072507260
7270728072907310732073307340735073607370
7380739074107420743074407450746074707480
7490751075207530754075507560757075807590
7610762076307640765076607670768076907710
7720773077407750776077707780779078107820
7830784078507860787078807890791079207930
7940795079607970798079908080908110812081
3081408150816081708180819082108220823082
4082508260827082808290831083208330834083
5083608370838083908410842084308440845084
6084708480849085108520853085408550856085
7085808590861086208630864086508660867086
8086908710872087308740875087608770878087
9088108820883088408850886088708880889089
1089208930894089508960897089808990909110
9120913091409150916091709180919092109220
9230924092509260927092809290931093209330
9340935093609370938093909410942094309440
9450946094709480949095109520953095409550
9560957095809590961096209630964096509660
9670968096909710972097309740975097609770
9780979098109820983098409850986098709880
9890991099209930994099509960997099809991
1112111311141115111611171118111911221123
1124112511261127112811291132113311341135
1136113711381139114211431144114511461147
1148114911521153115411551156115711581159
1162116311641165116611671168116911721173
1174117511761177117811791182118311841185
1186118711881189119211931194119511961197
1198119912121312141215121612171218121912
2212231224122512261227122812291232123312
3412351236123712381239124212431244124512
4612471248124912521253125412551256125712
5812591262126312641265126612671268126912
7212731274127512761277127812791282128312
8412851286128712881289129212931294129512
9612971298129913131413151316131713181319
1322132313241325132613271328132913321333
1334133513361337133813391342134313441345
1346134713481349135213531354135513561357
1358135913621363136413651366136713681369
1372137313741375137613771378137913821383
1384138513861387138813891392139313941395
1396139713981399141415141614171418141914
2214231424142514261427142814291432143314
3414351436143714381439144214431444144514
4614471448144914521453145414551456145714
5814591462146314641465146614671468146914
7214731474147514761477147814791482148314
8414851486148714881489149214931494149514
9614971498149915151615171518151915221523
1524152515261527152815291532153315341535
1536153715381539154215431544154515461547
1548154915521553155415551556155715581559
1562156315641565156615671568156915721573
1574157515761577157815791582158315841585
1586158715881589159215931594159515961597
1598159916161716181619162216231624162516
2616271628162916321633163416351636163716
3816391642164316441645164616471648164916
5216531654165516561657165816591662166316
6416651666166716681669167216731674167516
7616771678167916821683168416851686168716
8816891692169316941695169616971698169917
1718171917221723172417251726172717281729
1732173317341735173617371738173917421743
1744174517461747174817491752175317541755
1756175717581759176217631764176517661767
1768176917721773177417751776177717781779
1782178317841785178617871788178917921793
1794179517961797179817991818191822182318
2418251826182718281829183218331834183518
3618371838183918421843184418451846184718
4818491852185318541855185618571858185918
6218631864186518661867186818691872187318
7418751876187718781879188218831884188518
8618871888188918921893189418951896189718
9818991919221923192419251926192719281929
1932193319341935193619371938193919421943
1944194519461947194819491952195319541955
1956195719581959196219631964196519661967
1968196919721973197419751976197719781979
1982198319841985198619871988198919921993
1994199519961997199819992222322242225222
6222722282229223322342235223622372238223
9224322442245224622472248224922532254225
5225622572258225922632264226522662267226
8226922732274227522762277227822792283228
4228522862287228822892293229422952296229
7229822992323242325232623272328232923332
3342335233623372338233923432344234523462
3472348234923532354235523562357235823592
3632364236523662367236823692373237423752
3762377237823792383238423852386238723882
3892393239423952396239723982399242425242
6242724282429243324342435243624372438243
9244324442445244624472448244924532454245
5245624572458245924632464246524662467246
8246924732474247524762477247824792483248
4248524862487248824892493249424952496249
7249824992525262527252825292533253425352
5362537253825392543254425452546254725482
5492553255425552556255725582559256325642
5652566256725682569257325742575257625772
5782579258325842585258625872588258925932
5942595259625972598259926262726282629263
3263426352636263726382639264326442645264
6264726482649265326542655265626572658265
9266326642665266626672668266926732674267
5267626772678267926832684268526862687268
8268926932694269526962697269826992727282
7292733273427352736273727382739274327442
7452746274727482749275327542755275627572
7582759276327642765276627672768276927732
7742775277627772778277927832784278527862
7872788278927932794279527962797279827992
8282928332834283528362837283828392843284
4284528462847284828492853285428552856285
7285828592863286428652866286728682869287
3287428752876287728782879288328842885288
6288728882889289328942895289628972898289
9292933293429352936293729382939294329442
9452946294729482949295329542955295629572
9582959296329642965296629672968296929732
9742975297629772978297929832984298529862
9872988298929932994299529962997299829993
3334333533363337333833393344334533463347
3348334933543355335633573358335933643365
3366336733683369337433753376337733783379
3384338533863387338833893394339533963397
3398339934343534363437343834393444344534
4634473448344934543455345634573458345934
6434653466346734683469347434753476347734
7834793484348534863487348834893494349534
9634973498349935353635373538353935443545
3546354735483549355435553556355735583559
3564356535663567356835693574357535763577
3578357935843585358635873588358935943595
3596359735983599363637363836393644364536
4636473648364936543655365636573658365936
6436653666366736683669367436753676367736
7836793684368536863687368836893694369536
9636973698369937373837393744374537463747
3748374937543755375637573758375937643765
3766376737683769377437753776377737783779
3784378537863787378837893794379537963797
3798379938383938443845384638473848384938
5438553856385738583859386438653866386738
6838693874387538763877387838793884388538
8638873888388938943895389638973898389939
3944394539463947394839493954395539563957
3958395939643965396639673968396939743975
3976397739783979398439853986398739883989
3994399539963997399839994444544464447444
8444944554456445744584459446544664467446
8446944754476447744784479448544864487448
8448944954496449744984499454546454745484
5494555455645574558455945654566456745684
5694575457645774578457945854586458745884
5894595459645974598459946464746484649465
5465646574658465946654666466746684669467
5467646774678467946854686468746884689469
5469646974698469947474847494755475647574
7584759476547664767476847694775477647774
7784779478547864787478847894795479647974
7984799484849485548564857485848594865486
6486748684869487548764877487848794885488
6488748884889489548964897489848994949554
9564957495849594965496649674968496949754
9764977497849794985498649874988498949954
9964997499849995555655575558555955665567
5568556955765577557855795586558755885589
5596559755985599565657565856595666566756
6856695676567756785679568656875688568956
9656975698569957575857595766576757685769
5776577757785779578657875788578957965797
5798579958585958665867586858695876587758
7858795886588758885889589658975898589959
5966596759685969597659775978597959865987
5988598959965997599859996666766686669667
7667866796687668866896697669866996767686
7696777677867796787678867896797679867996
8686968776878687968876888688968976898689
9696977697869796987698869896997699869997
7778777977887789779877997878797888788978
9878997979887989799879998888988998989999

Posted by Kenny on 2006-02-25 00:06:49