Sähkölukossa on numeronäppäimet 0,1,...,9. Lukko aukeaa yhdellä nelinumeroisella avainkoodilla heti kun oikeat numerot ovat näppäillyt järjestyksessä. Montako näppäinpäinallusta riittää kaikkien mahdollilsten avainkoodien läpikäyntiin?
sähkölukko, lisää kombinatoriikkaa
pedantikko
476
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 4
Vanhimmat
10 000
Vaiko 40 000?
Onko kyse De Brujinin jonosta?
https://en.wikipedia.org/wiki/De_Bruijn_sequence
Vastaus on 10003. De Brujinin verkossa on 10000 solmua (kaikki mahdolliset koodit "0000",...,"9999"), mutta koska numerot näppäillään lineaarisesti putkeen, täytyy vielä loppuun näppäillä 3 numeroa. (Jos näppäilty jono laitettaisiin lopusta kiinni alkuun, niin sitten riittäisi 10000.)
Eräs ratkaisu löytyy sivulta:
http://alvaray.org/brute-forcing-pincode-keypads-using-combinatorial-mathematics/
Kyllä, Brujinista on kyse.
Eri yhdistelmiä on 1o000 kpl, á 4 numeroa. Syöttämällä kukin yhdistelmä erikseen, saadaan kaikki läpikäytyä 40000 painalluksella. Tämä siis riittää varmasti. Mutta kaikki yhdistelmät eivät tarvitse neljää painallusta, alkuvaiheessa yksi riittää yuottamaan kokeilemattoman yhdistelmän. Esim. syöttämällä 000012 tulee kokeilluksi yhdistelmät 0000, 0001 ja 0012. Selvästikin painlluksia pitää olla vähintään 10003. Loppupuolella monet kymmenluvut, esim koodit 0120...0129 ovat jo syötetyt, jolloin x012 yhdistelmästä ei ehkä pääse yhdellä painalluksella kokeilemattomaan yhdistelmään.
De Brujinin jonon muodostamalla päästään kuitenkin tilanteeseen, jossa jokainen uusi painallus tuottaaa uuden koodin, joten 10003 riittää.
Tämä ratkesikin nopeammin, kuin arvelin etukäteen.