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 A guess by Jer)

My first guess is

For 2 digits codes a 101 digit string works:

0010203040506070809112131415161718192234252627282933435363738394454647484955657585966768697787988990"

You're right that for 2 digits the answer is 101 but you posted 100 digits (you forgot 32!)

I did 3 digits and found the answer to be 1002...

0001002003004005006007008009011012013014015016017018019021022023024025026027028029031032033034035036 0370380390410420430440450460470480490510520530540550560570580590610620630640650660670680690710720730 7407507607707807908108208308408508608708808909109209309409509609709809911121131141151161171181191221 2312412512612712812913213313413513613713813914214314414514614714814915215315415515615715815916216316 4165166167168169172173174175176177178179182183184185186187188189192193194195196197198199222322422522 6227228229233234235236237238239243244245246247248249253254255256257258259263264265266267268269273274 2752762772782792832842852862872882892932942952962972982993334335336337338339344345346347348349354355 3563573583593643653663673683693743753763773783793843853863873883893943953963973983994445446447448449 4554564574584594654664674684694754764774784794854864874884894954964974984995556557558559566567568569 5765775785795865875885895965975985996667668669677678679687688689697698699777877978878979879988898999 00

So my guess for 4 digits is 10003 because with 1 digit it's 10, obviously. 2 is 101 and 3 is 1002. So following the pattern 4 would be 10003

Edited on May 24, 2004, 6:39 pm

Posted by Danny on 2004-05-24 18:29:09