Kombinationsproblem

[NatGum]

En sån där koddosa för dörrar där man skall trycka fyra siffror för att dörren skall öppna sig räknar de fyra sist tryckta siffrorna som inmatad kod. Exempel rätt kod är 1234 och du trycker 71234 så öppnar sig dörren. Det finns 10000 möjliga kombinationer på ett sådant kodlås. Men det behövs långt ifrån 4x10000 knapptryckninger för att vara säker på att knäcka koden.

Jag kan inte komma på något sätt att ta reda på det minsta antalet knapptryckningar som krävs för att vara säker på att koden är knäckt.

 

25 kominationer man kan skapa med siffrorna 0,1,2,3,4 kombinerade i par. Den koden kan man vara säker på att knäcka med 26 knapptryckningar.01234432102422031330411400

Kan det vara så enkelt att det bara krävs 10001 knapptryckningar för att knäcka en sådan 4 siffrig kod?

Är lösningen antalet kombinationer+1 ?

 

/NatGum

 

[Vanjis]

Hej!

 

Klurigt problem! Jag skulle gissa på att det minsta antalet knapptryckningar blir 10003, dvs antal komb + kodens längd - 1. Men det gäller bara under förutsättning att det går att skapa en nummerserie, som du gjorde i exemplet, där inga kombinationen uppkommer fler än en gång. Rent spontant känns det svårt att åstadkomma med koder på fler än två siffror, men jag är inte säker. Ska klura lite till på det.

 

Mvh

/Vanja

 

[inlägget ändrat 2005-06-16 13:11:45 av Vanjis]

[Martin Karlsson]

000010002000300040005000600070008000900011001200130014001500

160017001800190010102010301040105010601070108010901002100310

041005100610071008100910022002300240025002600270028002900202

030204020502060207020802090200320042005200620072008200920033

003400350036003700380039003030403050306030703080309030043005

300630073008300930044004500460047004800490040405040604070408

040904005400640074008400940055005600570058005900505060507050

805090500650075008500950066006700680069006060706080609060076

008600960077007800790070708070907008700970088008900808090800

980099009090111011201130114011501160117011801190121012201230

124012501260127012801290131013201330134013501360137013801390

141014201430144014501460147014801490151015201530154015501560

157015801590161016201630164016501660167016801690171017201730

174017501760177017801790181018201830184018501860187018801890

191019201930194019501960197019801990102110221023102410251026

102710281029102120213021402150216021702180219021031103210411

042105110521061106210711072108110821091109210331034103510361

037103810391031203130314031503160317031803190310431053106310

731083109310441045104610471048104910412041304140415041604170

418041904105410641074108410941055105610571058105910512051305

140515051605170518051905106510751085109510661067106810691061

206130614061506160617061806190610761086109610771078107910712

071307140715071607170718071907108710971088108910812081308140

815081608170818081908109810991091209130914091509160917091809

190911112111311141115111611171118111911221123112411251126112

711281129113211331134113511361137113811391142114311441145114

611471148114911521153115411551156115711581159116211631164116

511661167116811691172117311741175117611771178117911821183118

411851186118711881189119211931194119511961197119811991121213

121412151216121712181219121222022212320232124202421252025212

620262127202721282028212920292122302231224022412250225122602

261227022712280228122902291220322042205220622072208220922033

203420352036203720382039203230324032503260327032803290320432

053206320732083209320442045204620472048204920423042404250426

042704280429042054206420742084209420552056205720582059205230

524052505260527052805290520652075208520952066206720682069206

230624062506260627062806290620762086209620772078207920723072

407250726072707280729072087209720882089208230824082508260827

082808290820982099209230924092509260927092809290921322133213

421352136213721382139214221432144214521462147214821492152215

321542155215621572158215921622163216421652166216721682169217

221732174217521762177217821792182218321842185218621872188218

921922193219421952196219721982199212330233123402341235023512

360236123702371238023812390239123131323141314231513152316131

623171317231813182319131923124302431253025312630263127302731

283028312930293124402441245024512460246124702471248024812490

249124132414142415141524161416241714172418141824191419241254

025412640264127402741284028412940294125502551256025612570257

125802581259025912513251425151525161516251715172518151825191

519251265026512750275128502851295029512660266126702671268026

812690269126132614261526161626171617261816182619161926127602

761286028612960296127702771278027812790279127132714271527162

717172718171827191719271287028712970297128802881289028912813

281428152816281728181828191819281298029812990299129132914291

529162917291829191929133303331334033413350335133603361337033

713380338133903391343034313440344134503451346034613470347134

803481349034913530353135403541355035513560356135703571358035

813590359136303631364036413650365136603661367036713680368136

903691373037313740374137503751376037613770377137803781379037

913830383138403841385038513860386138703871388038813890389139

303931394039413950395139603961397039713980398139903991304330

443045304630473048304930434043504360437043804390430533054306

330643073307430833084309330943055305630573058305930534053505

360537053805390530653075308530953066306730683069306340635063

606370638063906307630863096307730783079307340735073607370738

073907308730973088308930834083508360837083808390830983099309

340935093609370938093909314331443145314631473148314931533154

315531563157315831593163316431653166316731683169317331743175

317631773178317931833184318531863187318831893193319431953196

319731983199314341435143614371438143914322223223322422243232

333234223432423243324422443252225232532253325422543262226232

632263326422643272227232732273327422743282228232832283328422

843292229232932293329422943235223532362236323722373238223832

392239323342335233623372338233923333433353336333733383339333

442344334522452345324533462246234632463347224723473247334822

482348324833492249234932493341534163417341834193414440444145

404541464046414740474148404841494049414450445144604461447044

714480448144904491440544064407440844094405540564057405840594

054505460547054805490540654075408540954066406740684069406450

646064706480649064076408640964077407840794074507460747074807

490740874097408840894084508460847084808490840984099409450946

094709480949094154415541564157415841594164416541664167416841

694174417541764177417841794184418541864187418841894194419541

964197419841994145504551456045614570457145804581459045914515

351545163516451735174518351845193519451465046514750475148504

851495049514660466146704671468046814690469146153615461636164

617361746183618461936194614760476148604861496049614770477147

804781479047914715371547163716471737174718371847193719471487

048714970497148804881489048914815381548163816481738174818381

848193819481498049814990499149153915491639164917391749183918

491939194915550555155605561557055715580558155905591565056515

660566156705671568056815690569157505751576057615770577157805

781579057915850585158605861587058715880588158905891595059515

960596159705971598059815990599150655066506750685069506560657

065806590650755076508550865095509650775078507950756075707580

759075087509750885089508560857085808590850985099509560957095

809590951655166516751685169517551765177517851795185518651875

188518951955196519751985199516561657165816591652255226523542

355236423652424252434243524442445245424552464246525253425352

544254525532554255525622563256425652624262526342635264426452

653265426552662266326642665272427252734273527442745275227532

754275527622763276427652824282528342835284428452852285328542

855286228632864286529242925293429352944294529522953295429552

962296329642965237423752384238523942395235623572257235822582

359225923534343535362436253634363537243725373437353824382538

343835392439253934393533543355336433653374337533843385339433

953356335732573358325833593259335443444354534453546244625463

446354724472547344735482448254834483549244925493449354345435

543644365437443754384438543944395434643474247434842484349424

943455345624563457245734582458345924593453645374538453945346

534752475348524853495249534662366246633663467226723672467326

733673468226823682468326833683469226923692469326933693462626

362646272627362746282628362846292629362946237623862396237722

772378227823792279237263727273728272837292729372287229722882

289228282928229822992292923872388238923972398239923277327832

793273826382739263927328732973288328932838283928329832993293

829392933763377337833793386338733883389339633973398339933476

247634772477347824783479247934726472747284729472486248724962

497248824892482648274828482948249824992492649274928492949255

625572558255925662567256825692574257525762577257825792584258

525862587258825892594259525962597259825992526742675268426852

694269526562657265826592653555356435653655366436653755376437

653855386438653955396439653574357535843585359435953556355735

583559355444454455454555464446454654465547444745475447554844

484548544855494449454954495545644565457445754584458545944595

455645574558455945555655575558555955566356644664566546655673

567436744674567536754675568356843684468456853685468556935694

369446945695369546955617561856195616660666167606761686068616

960696166706671668066816690669166076608660966077607860796076

707680769076087609760886089608670868086908609860996096709680

969096176617761786179618661876188618961966197619861996167706

771678067816790679167175717671857186719571967168706871697069

716880688168906891681758176818581868195819681698069816990699

169175917691859186919591969177707771778077817790779178707871

788078817890789179707971798079817990799170877088708970878087

908709770987099709780979097187718871897197719871997187818791

872666266726762677268626872756275727662767277427752776277727

842785278627872856285728662867287428752876287728842885288628

872956295729662967297429752976297729842985298629872696269726

682669266363646365636663736374637563766383638463856386639363

946395639663486349634873488348934836473648373738374737483838

473848393739383947394834973498349934936493749384939394935763

577357835793586358735883589359635973598359935279427952758275

927537743775387438753974397537843785379437953757365737583658

375936593754764476547744775486448654874487549644965497449754

784478547944795474646474748464847494649474576457745864587459

645974578457945738573957366736763677368636873696369736683669

366465646664756476648564866495649664676468646964657465846594

655765586559655775578557955747574857495746674677468746974668

466946656566657565766585658665956596656765686569656675668566

956666766686669666775677637764776577667826783678467856786378

647865786679267936794679567962796379647965796673767386739673

777378737972797376827683769276937638763976388438853886389428

943895289538962896385828583859285938539843985399429943995299

539582958395929593954884488548944895498449854994499545884589

458475848485849484958459845994594759485949495946882688368846

892689368946982698369846992699369946299629682868296928692963

986399637782778377927793773877397738873897289738683869386487

648864976498648964867476748684768486947694865875587658855886

597559765985598658955896585757585859575958568756885697569856

895683968378827883798279837892789378197818880888189808981889

088918809880998098909819881998189908991891979198919990999192

799272997297828782979287929739873997379937938783879396939783

979388828883889288938982898389928993829882998298929839883998

398939847774778478747884797479848774878488748884897489849674

968497749784987498849964997499847794775767577758675877596759

775787579757685769576687669766886689668586859685778578857985

779577676777686768776967697767876797677867796777787779777886

788758876887789478957896789758976897785878597858885898586958

669866995599569965996694969479947598759975959579957698769976

959695879487958894889589948995859885998597949795977986798779

967997786868786968697868886898687968787888789878797879886988

799869987969697968896899688889788988899789988949894999299939

99495989599959698969996979798979997989899989999.

 

Det är den bästa serien jag kan komma på. Jag satt uppe i två dygn och skrev den i wordpad.

Nu är det bara att börja cracka din portkod som du har tappat bort, grabben. 10427 tryckningar blir det som mest.

 

Men sen är ju frågan vilken algoritm man faktiskt använder för att generera den optimala serien.

[inlägget ändrat 2005-06-17 09:12:04 av Martin Karlsson]

[NatGum]

Då är det nog dax att vila ditt stackars pekfinger nu.

Jag knäckte min kod på 4 knapptryckningar :-) 9510

 

Nä det är troligtvis inte optimalt men det är nära. Du ligger bara ca 4% över det som troligtvis är minsta möjliga 10003. Du har löst det väldigt systemmatiskt. Skrev du något program?

 

/NatGum

 

[Martin Karlsson]

Japp, skrev ett litet "brutal force" program i morse. Vackert är det inte.

 

http://hem.bredband.net/b218521/code.exe

 

Fick egentligen ner den till 10006. Jag är riktigt kass på matte, det finns säkert nåt fundamentalt man missar.

 

Nu börjar det bli lite ramblings och off-topic från mig här... Men det är ju svinenkelt att ändra algoritmen så att den lägger på siffror både på början och slutet, då kommer den hitta den perfekta kombinationen. men det orkar jag inte programmera.

 

Det hjälper ju liksom inte så mycket...

[inlägget ändrat 2005-06-17 11:58:26 av Martin Karlsson]