Can you crack the combination lock?

[yourmum3121]

111211311221231213213313222323­332. Not sure it's the shortest but they're all in there.

[naradia95]

For 3-digit number using 1-3, I got: 1 1 1 2 1 1 3 2 2 2 3 2 1 2 2 1 3 3 1 3 1 2 3 3 3 2 3 1 1 That holds: 111 112 113 121 122 123 131 132 133 211 212 213 221 222 223 231 232 233 311 312 313 321 322 323 331 332 333

[LegendofStalfos]

4 digit

111122223333444455556666777788­889999000011121113111411151116­111711181119111011221123112411­251126112711281129113011311321­133113411351136113711381139114­011421143114411451146114711481­149115011521153115411551156115­711581159116011621163116411651­167116811691170117211731174117­511761177 ... I give up

[Pianoguy32]

does the lower half of his body move this much ?

[brianawesome100]

111222333112113221223332331321­321313212121313213132313232132­-3 digits

321432143241324132413241342413­413413241341321434213421341314­-4 digits

343215324152341534154325324153­215432453154325423135423534151­324153241532454315245423512345­321513442352143253241432514321­51-5 digits

[subsystems]

I solved the sequence for all 1 digit combinations using 0 thru 9! Yaaaaay!!

[Gytax0]

What?! I recognize this face! Hello from a Numberphile's viewer. Definitely subscribing.

[singingbanana]

@Gytax0 Hello!

[CNN911Fakes]

So the lock is a "bad" lock because, once you have punched correct numbers in sequence, punching incorrect ones doesn't make you start all over. Unfortunately, you must use the same approach on all future openings. The advantage of the normal "brute force" approach is that you get the correct combination when you are successful and you can use it over and over again.

Cool.

[ThBearsFriend]

Remarkably, there are, at time of writing, 189 comments - and not a single one has mentioned the fact that you have used the word "combination" when you should have used the word "permutation"!!!

[hussein688]

@ThBearsFriend because people dont get hung up on the notation when everyone including you understand what problem is asking for.

[eddyproca]

33322211121223113123213233133 for three digits

[allyamezola]

I don't know what just happened



[geeta172]

there are quite a few possible answers...ryt!?

[JRocKinPENANG]

so.... the 3 digit code is going to be 29 digits long....?? @@

[coolster01]

I dont get it :(

[iTmcb]

You didn't say "If you have been, thanks for watching." :(

[FanaticDamen]

DAMMIT BANANA! IM A PHYSCHOLOGIST! NOT A MATHEMATICIAN! Oh well ... lets see nao... Would a magnet and a screw driver work on opening said lock?

[tonix1993]

so every combination in the sequence must be unique?

[singingbanana]

@tonix1993 Yup If possible.

[FHomeBrew]

Oh man this sounds like such a big problem, and I'm SOO certain it has a very simple and elegant answer we mere laymen humans won't find all that easily. I think I'll just wait for the solution :p

Great problem! This problem also applies to combination locks on a lot of suitcases where you rotate the numbered rings. The solution would have to resemble grey code to be efficiently put to use.

[Berntisso]

3 digits: 11121131221231322233232133311

[Fishpizza1212]

Spent all day going through both the 3 digit sequence and the 4 digit sequence.

The shortest 3 digit sequence is 29 digits : 33111211312212313213322232333

The shortest 4 digit sequence is 259 digits : 444111121113111411221123112411­321123113411421143114412121312­141222122312241232123312341242­124312441313141322132313241332­133313341342134313441414221423­142414321433143414421443144422­223222422332234224323233323432­423243324423342344242434244322­4443333433443434444

[smsdiscrete]

Mr. Curran's 3rd Hour Discrete Math Solution:

11121232312221313223331133211

We found our solution by vertically aligning each permutation by overlapping the last two digits of one permutation with the first two digits of another. We also believe that we came up with a solution for how many digits any sequence would require. Let x = number of digits to choose from, let n = number of digits in the sequence, then x^n + (n-1) would give the number of digits required. Thus, 3^3 + (3-1) = 29.

[mihassan]

3 digit code: 1 1 1 2 1 1 3 1 2 2 1 2 3 1 3 2 1 3 3 2 2 2 3 2 3 3 3 1 1

4 digit code: 111121113111411221123112411321­133113411421143114412121312141­222122312241232123312341242124­312441313141322132313241332133­313341342134313441414221423142­414321433143414421443144422223­222422332234224322442323242333­233423432344242433243424432444­3333433443434444111

[DrMikero]

De Bruijn sequences! ;)

[bluecombats]

max length for 3 digit combination only containing 1,2 and 3 would be 81 (3^4) digits long so looking for something less than that.

111222333121132131131332212323­231(33 digits) got them all although some are repeated like 232 and 323. I think the general formula is n^k+(k-1) where n is the number of available digits and k is the number of digits for the lock. so for 3 digits and a 3 digit lock it will be 3^3+2=29 digits long. so for numbers 0-9 on a 4 digit lock it will be 10^4+3=10003

[JayJamesDee]

For 3 digits I'm thinking:

111221131121231322232133323312

[001BrainyBrady]

It would be good to find an algebraic expression for the next number in the sequence.

[roflmoqkz1]

i solved the 3 digit one its kinda like a maze here inis 29 digits

11122233311332212131323123211

[MyrMagic]

I got to 35 numbers for the 3-digit: 123121321112122113133112223233­22333

[Horinius]

I'd solve it by making a program going through all the combinations by shifting just a digit each time.

[MrRyanDuba]

Hopefully the bedroom intruder never finds the sequence.

[darkdudironaji]

What if the lock doesn't work like that?

[TehMathWiztard]

Alright so, I spent about 3 hours on the thought that the triple 1's, 2's and 3's were separated from each other. Found out that is impossible. I need sleep now x_x

[qwert4327able]

meant 10003 below

[qwert4327able]

I am going to conjecture that this lower bound is always achievable hence the general solution here is m^n+n-1 where n is the number of digits that can be entered chosen from m numbers. For his answer we had 4 numbers in a sequence and 10 choices giving 10^4+3=100003 as wanted. This is almost certainly the solution for every possible one and now just has to be proven that this is achievable which is gna be very hard.

[qwert4327able]

Here is a general lower bound for n digits and m numbers (that may not be achievable). With n digits and m different numbers there are m^n possible combinations and to type in this many of ANY n digit numbers requires m^n+n-1 entries hence this is a lower bound. For example with 3 digits 3 numbers then 29 is a lower bound and any combination found which equals this will be the lowest combo. Given that someone above claimed they have done it in 18 numbers they must be wrong.

[TehMathWiztard]

@qwert4327able I was just thinking that.

[PartiallyRibena]

π definitely pie!

[PartiallyRibena]

pie?

[Pizzscn]

well, now we all know how to hack people :D

[qwerasdfAngel]

I spendt 5 min to find the kode for a door to the girls "dome" when i was in highschool.. ;)

same type of lock... ^^

[saltymurder]

I love how enthusiastic you are!

[anticorncob6]

Finally, something that I can use the Sketch pad function on my iPad for.

[Th1s1sMyAcc0untNam3]

32333123131112113222332122133

Finally

[singingbanana]

@imTHEcardMAGICmaster That's a bit childish isn't it.

[GammahooX]

This is the solution for 4 digits from 1 to 4:

111121113111411221123112411321­133113411421143114412121312141­222122312241232123312341242124­312441313141322132313241332133­313341342134313441414221423142­414321433143414421443144422223­222422332234224322442323242333­233423432344242433243424432444­3333433443434444111

The one for 5 digits doesn't fit in the comment section anymore. :P

[wopaah]

Shortest possible for 3 digits (other solutions possible):

111 222 333 121 131 321 232 213 323 (11)

I entered the last 2 digits between brackets, because I see it as a cycle. If you start anywhere in this sequence (without the final two), make it to the end, start again from the beginning and then type the two first numbers again, you'll have all of them.

Why have I split it up in groups of three? Don't know yet, but I guess there'll be patterns in such a way.

Time for lunch...

[HappyMemoryXD]

The number of digits of the sequence should be the number of combinations + Number of digits - 1.

So 2 digits is 5

3 digits is 29

4 digits it 259

[PullarBearBear]

Just a question: Is it possible to have 2 or more possible solutions?

[thepianoaddict]

@PullarBearBear yes there is more than one solution.

[isj4]

@PullarBearBear Yes, for instance when you have found a valid sequence then the reverse of the sequence is also valid.

[HappyMemoryXD]

Is this for 3 digits?

11121131221231321332223233311

[gecko77z]

wow! this is awesome, this could be used for hacking!

[x246869]

Nothing an infinite number of monkeys can't handle.

[hi1hi2hi2]

This is my solution. Ill try and make a better one maybe?

111211311212213123132133323223­3122232

[hi1hi2hi2]

@hi1hi2hi2 Better one

21112312122331131321333232221

[Goldy1337]

3 digits - 111222333112233123

4 digits - 111122223333444411122233344411­2233441234

5 digits -11111222223333344444555551111­222233334444555511122233344455­5112233445512345

[singingbanana]

@Goldy1337 You've missed a few.

[Goldy1337]

@singingbanana I just guessed. I figured there would be a few missing combinations.

I hated sequences and combinations in high school; it was my worst topic.

[brianshrode72]

@singingbanana A FEW?!!?!? HE MISSED TONS!

[iamUSAn50]

@Goldy1337 lol fail

[yuitry1]

@Goldy1337 132 missed in 3 1224 missed in 4 and 12354 missed in 5

[vincentlcarter]

@yuitry1 check out the last 5 digits for 5

[muffemod]

Play the video then rapidly keep pressing the number 1 on your keyboard for a good laugh.

[forrest0no]

3 digits: 211223313 4 digits: 21443424112233132 5 digits: 1121341552535451442433223 Check me Im pretty sure Im right

[singingbanana]

@forrest0no You need to contain combinations like 111 as well. I can see you've missed 121 as well...

[forrest0no]

@singingbanana I set it up in pairs, not triples, sorry for not clarifying :) ill try in triples and quadruples.

[forrest0no]

@singingbanana in fact here is one with triples

2: 11121122212 3:1112113112212321322231233313­323

Im thinking that is right... Not sure...

[Pizzscn]

@singingbanana I think he got 121 right at the beginning

[muffemod]

@forrest0no Think you're missing some combos like 111 and 222 and 333 in the first one etc...

[rtwvidz]

I got these answers:

11122233311332213121232313211 (29 digits)

111144443444244414433443244314­423442244214413441244114343424­341433343324331432343224321431­343124311424241423342324231422­342224221421342124211414133413­241314123412241214113411241113­333233313322332133123311323231­322232213212321131312231213112­3111222212211212111 (259 digits)

In general, for a combination of length N from K possible digits, the sequence length is (K^N)+N-1.

So:

(3^3)+3-1 = 29

(4^4)+4-1 = 259

(10^4)+4-1 = 10003

[GammahooX]

@Zeldakitteh I'm getting a stack overflow, it's not just pure ram size. The problem might be with the deep recursion but I suspect it's actually the ArrayList which is probably not meant for such large lists. For more digits I'd write it in C++ without recursion and my own datatype. Properly optimised you could got to about 10 digits with 4GB of RAM.

[Qwubs]

I feel as if the strategy I would use is to list every combination and create a chain adding 1 number at a time and crossing off numbers as you go along. So the order would be starting with 1234, then doing a combo that includes 234X, then 34XY, then 4XYZ then XYZA and so on until you've crossed off every combo. Using this strategy on the 3 puzzle, I got an answer of:

311121131333122232213231233212

it solved itself (except I had 311 at the end which I easily stuck a 3 at the beginning).

[Everyvideo123]

@Qwubs Yeah I used a similar method, mine was:

11122233311332213121232313211

[IhaveWoodforSheep]

For three digit combination of three digits, I have

11223213322212313233312111311,

which was solved graphically (using a directed graph). Such a solution is prohibitive in the next cases (drawing 259 lines between 16 points...) so I'll be doing those differently. But now I have two data points (plus the other strings in the comments) to look at the properties of!

[GetMeThere1]

I could do it....but I just don't wanna.

[hypock1]

more like winningbannana :) love the show!

[magician2242]

it is not possible after you get over 4 digits

[jowfofofo]

I made one of those locks back in my electronics course...it uses a 4017 IC, normally used for divisions and counters.

[IhaveWoodforSheep]

Well, given m digits in an n digit combination, I can tell you that the shortest string will be m^n+(n-1). This is because you can drop (n-1) digits from every combination (of which there are m^n) save the last. As well, there are n digits in each of m^n combinations, so the number of digits is really n*m^n-(n-1)*(m^n-1), which is just m^n+(n-1).

But you already knew that. I'll have a solution to the problem later.

[lekoman]

@singingbanana seriously dude, you're the first person to make math this interesting I've ever come across. Math education should start from solving *interesting* problems, and work backwards to let people figure out technique... and that's exactly what you're doing. I love it!

[Contrabot]

Nooooo! it wasent your normal goodbye! "So if you have been..Thanks for watching!"

[wzrds3]

Finally found a solution for the 3 digit problem using just pen and paper (no brute force methods here). 11121222323331312311332213211

[excepto94]

(0+1+2+3+4+5+6+7+8+9)^4=410062­5

[KyosBlog]

@excepto94 what is this? the possible combinations are 4^9, if you just write them down after one another you get 4^10 digits, which is about a fourth of your solution even without any optimization, while the optimum length should be way shorter.

[excepto94]

@KyosBlog didn't think through it, thought of the handshaking problem and (don't know the English term for X^Y) to the number of well... numbers, but I didn't even thought I was right.

[IAintMadXBL]

My solution to opening the door? Sledgehammer.

[MorallyDepraved]

My solution: 23213132313311122233322112123

[messi78910]

how are you that smart

[V1per41]

29 is the shortest string for 3 digits.

My solution:

31112113122123132133222323331

4 digit solution will be 112 digits long I believe.

[redmatrix]

aww, you didn't say "If you have been, thanks for watching"

There is a misnomer in your description. You are asking us to solve a 2 digit sequence with 2 total digits, a 3 digit sequence with only 3 digits, and a 4 digit sequence with only 4 digits. But the lock doesn't use a 10 digit sequence. Why not ask us to figure out a 2 digit sequence with 3 digits, 3 with 5, 4 with 7. That would get us to practice for the real problem. Just my thoughts.

[singingbanana]

@redmatrix I could have done. You're right, there is a slight difference between the problems.

[rakib567]

0123456789 1234567890 2345678901 3456789012 4567890123 5678901234 6789012345 7890123456 8901234567 9012345678 ?????

[supergreatsuper]

@rakib567 Where is 0000?

[GammahooX]

11121131221231321332223233311 - 29 Digits (one of the shortest possible ones).

[Butt4cak3]

I wrote an algorithm that solved the problem with all 10 digits and a 4 digit code with a 10029 digit solution. Only 26 to go!

[singingbanana]

@Butt4cak3 Ooh, so why wasn't it the 10003 digit solution? Tell me about it.

[Butt4cak3]

@singingbanana It was the first time I tested it. With some optimization I could get the 10003 solution as well. I'm going to try it later. If you want to see it yourself, I can upload to a webserver and private message you the link ;D

[GammahooX]

@Butt4cak3 Hm, I wrote one in like 20 lines of java code that always finds the shortest solution for all digit ranges (0-9 in this case) and lengths (4 in this case). :P

[singingbanana]

@GammahooX Excellent stuff. By the way, I'll be giving you a pen and paper solution - although a little intense when you have to write out a 10003 digit solution using pen and paper, which I did.

[GammahooX]

@singingbanana Well it starts getting hard above 4 digits (with 0-9) on the PC aswell. My simple and relatively fast way to solve it can not solve the problem for 5 digits due to memory limitations. However it would be possible to implement it in a more memory efficient, more complex and maybe slower way in C++.

My code can be found here: pastebin[.]com/bGdNwrUB

[Zeldakitteh]

@GammahooX Is the memory limitation Java's 64 MB or the computers RAM (one or more GB usually)?

[MrCDRipped]

for 4 numbers its either 28 or 29 i think :/

[xKargatx]

My 3 - digit sequence:

31231321223311211133323222131

With 29 digits I think it's the shortest possible way.

Since you get a new 3-digit combination by adding 1 digit to a 3 digit combination and I need 27 different 3-digit combinations I took 3 random digits and added 26 more to have the 27 different possibilities. Making an answer with 29-digits the shortest possible answer.

I hope people can understand my explanation. if you don't you can just ask me and I'll try too explain it better.

[MaThWa92]

By the way @singingbanana do you know Project Euler? It's all about solving little math problems and it's pretty fun and addictive!

[singingbanana]

@MaThWa92 I know of it. I haven't taken part yet.

[V1per41]

@MaThWa92 That's exactly what I thought of when I saw this problem

[LewisAM37]

12221112123332232313311312 i'm missing 132, 231 and 321. but everything I try, breaks everything else.

[111RockNRoll111]

21312313311223233321113222121

[razerburst]

1337

[khzhak]

Take the sequence for every combination of four numbers, and repeat the pattern for solving for the 1234 combination, but then 2345, 3456, .... After that, 1235, skipping any four consecutive without a 5, and so on, then 1236, 1237, 1238, 1239, 1230, 1245,6,7,1256,7,8, and so on, until 6890.

[macaw2000]

Is this a hobbit?

[alfa00xx]

123456789111212312341234512346­165715818165486156747946251897­916574897465419846541897465489­899789812563213251861654651566­6485321654654841864116824ILUMI­NATI21651874487183123412345123­461657158181654861567479462518­979165748974654198465418974654­89899789812563213251

[MegaCakewalker]

@alfa00xx I see what you did there!

[wizzboy5000000000000]

@alfa00xx not a single 0

[o0ocrizo0o]

001101122122332334434455455665­667767788788998

?

[IrkIr]

21222321113233131231121333221

[bobdole1988]

12312132321222111313322333112 for 1-3, I'll to 4 later if it's still unsolved

[monsimand]

you can do it on 24 digits

[monsimand]

1*2*3*4

[orcyngiser]

If you feel like giving us a real treat why dont you solve this for a code of N length, with K possible digits :)

[singingbanana]

@orcyngiser I will show you how in the response!

[Jonsoncao]

@orcyngiser Use Eulerian path to solve this problem seeing possible digits as nodes and combinations as paths, you would get De Bruijn sequence(s) with B(N, K) = K^N digits, then because the property of the cyclic group, you need another (N-1) attached to the end, in this case it is 10^4+4-1 = 10003, I feel like cheating since I am a math grad student...until I took an arrow in the knee.

[orcyngiser]

@Jonsoncao y u no talk in english? :)

[ipadkeyboard13]

For 3: 11122131232223311333231321211.­ That's 29 digits. :P

[siriuscord]

@NeoLeo37 except it's a 3-digit combination, that uses the numbers 1, 2 and 3. it'd be right is it was a 2 digit combination though

[alewisgb]

I know how to get into the lock easily its the same type of lock that is on the door to the office where i work, in a charity shop! If you simply put a number in and turn and keep the dial turned click C (cancel) and then if you hear a click its a number(repeat 0-9), The lock you showed is very simple and actually works on a down or not idea, basically you can put the four numbers in ANY order and click the letter X, Y or Z

I know its not the mathematical solve that you wanted but its a solution

[MrCDRipped]

for the 4 digit one is it 24?

[singingbanana]

@MrCDRipped It's longer than that. Don't forget it has to contain things like 1111, 2222 etc as well.

[111RockNRoll111]

on the 123 lock, given that there are (I think) 27 possible combos, am I right in saying that the correct sequence would be (3 + 26) = 29 digits long?

[singingbanana]

@111RockNRoll111 I don't think I'm spoiling to much by saying it is 29 digits long. And there are many ways to solve it.

[kitkatchunky93]

@111RockNRoll111 Yes you are correct now actually work it out like the rest of us :P

[111RockNRoll111]

@kitkatchunky93 I dont think Ive got enough paper in the house after all these failed attempts!

I wonder if there is a formula....

[singingbanana]

@111RockNRoll111 Haha! Now you're thinking like a mathematician...

[sid2089]

There are multiple answers. The process of finding an answer is very simple.

First write all states that are possible - 10k in this case. Now draw an arrow from each state to the one that would be obtained by adding a digit to it. For example, from state 1234 draw arrows to 2340, 2341...2349. After this, find a path that covers all states exactly once. There are multiple such paths and each corresponds to an answer.

Length of the solution is number of states + length of combination - 1 = 1003

[inscept]

@sid2089 So you've turned this question into an excercise in graph theory. That's a great idea I would've never had. Is there an simple algorithm for finding the traversal of an oriented graph without visiting a vertex twice? Otherwise I might just use backtracking to find a solution.

[MrCDRipped]

IS THE door already open?

[Nightmare2u]

I believe for 1-3 it's: 11121131221231321332322233311

But I think I'll need more then my Post-it note to work out 1-4.

And with finals coming up I think I'll leave it up to some daring

puzzler with more time on their hands. Good Luck

[rerere284]

111222333221121313212311331323­2312

323,321,132,313,132 occur twice : /

type:

3-grams "11122233322112131321231133132­32312"

into wolfram alpha

to check it.

[siriuscord]

so far, I have 000010002000300040005000600070­008000900, but after that it gets a bit tricky. If i put another 0 down, I would repeat something no matter what I put after it. I believe it should be a 1, but then unsure as to where to go from there.

[treegraph]

I have discovered the sequence, together with a truly marvelous proof that it's the best solution, which this textfield is too small to contain.

[GammahooX]

@treegraph Haha, nice one. :D

[jinanwow]

C4, thats my number.

[ZeldaGirl35]

122213133223112333121321113232­12 that's my guess >_< ... 32 digits :D

[wzrds3]

The shortest sequence for the 3-digit 1-3 lock is 29 digits long and for the 4-digit 1-4 lock is 259 digits long. I don't think I'll be posting the latter sequence today.

[ZeldaGirl35]

@wzrds3 yeah I think for 3-digit 1-3 lock is 29 digits long ^_^ , I got 32 digits though :/

[Mrcheesefaceful]

WHAT?



[lzrdking5]

Such sequences are called De Bruijn sequences. I believe the minimum length of a sequence of "m" digits of length "n" is m^n, but i completely forgot how to determine the exact sequence. It's been a while since I read about this.

[kitkatchunky93]

11121131221231321332223233311 allows for all 27 possible combinations of the 3 digits

[ZeldaGirl35]

@kitkatchunky93 I think this is right :D , great job ^_^

[ZeldaGirl35]

For 3 digit sequence, there are 27 possible combinations right? :p

[singingbanana]

@ZeldaGirl35 There are 27 combinations, so 27x3=81 digits all together - but there is a sequence that is much shorter but still contains all possible 3-digit combinations.

[kitkatchunky93]

@singingbanana 11121131221231321332223233311 allows for all 27 possible combinations of the 3 digits

[mdogboy0]

this is for the 4 digit combination using digits 0 to 9

i got it i think. count up from 0000 to 9999. and just place each number next to the previous.

0000 0001 0002 0003 0004... 9995 9996 9997 9998 9999

i put spaces in just to help you see the numbers.this is just going through every combination... lol but it works i think. take a long time to do it this way.

i believe this works but... it is inefficient. numbers will be repeated doing it like this

[singingbanana]

@mdogboy0 Exactly, the shortest solution has 10003 digits, so you're way off at the moment.