Can You Solve The Code Lock Riddle? A GENIUS Math Shortcut

A safe has a code lock that unlocks if you input the correct four digits, in any order. The lock has a keypad the the digits 0, 1, 2, ..., 9. For example, suppose the unlock code is 1000. The safe will open for any order you input the digits: 1000, 0100, 0010, 0001. How many different unlock codes are there? (Two unlock codes are different if they do not contain exactly the same digits.) Watch the video for two different methods to solve this puzzle.
My blog post for this video:
wp.me/p6aMk-5cG
Tim Morris emailed me a wonderful write-up connecting the two methods and the Chu-Vandermonde identity. Do check it out! It's beautifully formatted and very nicely explained. Here is the link to the pdf on Google Drive: drive.google.com/file/d/0B8VT...
TOUGH Interview Question - Ways To Give 11 Coins To 3 People
• How To Solve A TOUGH I...
If you like my videos, you can support me at Patreon: / mindyourdecisions
Connect on social media. I update each site when I have a new video or blog post, so you can follow me on whichever method is most convenient for you.
My Blog: mindyourdecisions.com/blog/
Twitter: / preshtalwalkar
Facebook: / 168446714965
Google+: plus.google.com/1083366085665...
Pinterest: / preshtalwalkar
Tumblr: / preshtalwalkar
Instagram: / preshtalwalkar
Patreon: / mindyourdecisions
Newsletter (sent about 2 times a year): eepurl.com/KvS0r
My Books
"The Joy of Game Theory" shows how you can use math to out-think your competition. (rated 3.9/5 stars on 29 reviews) www.amazon.com/gp/product/150...
"The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias" is a handbook that explains the many ways we are biased about decision-making and offers techniques to make smart decisions. (rated 5/5 stars on 2 reviews) www.amazon.com/gp/product/152...
"Math Puzzles Volume 1" features classic brain teasers and riddles with complete solutions for problems in counting, geometry, probability, and game theory. Volume 1 is rated 4.4/5 stars on 13 reviews. www.amazon.com/gp/product/151...
"Math Puzzles Volume 2" is a sequel book with more great problems. (rated 5/5 stars on 3 reviews) www.amazon.com/gp/product/151...
"Math Puzzles Volume 3" is the third in the series. (rated 3.8/5 stars on 4 reviews) www.amazon.com/gp/product/151...
"40 Paradoxes in Logic, Probability, and Game Theory" contains thought-provoking and counter-intuitive results. (rated 4.3/5 stars on 12 reviews) www.amazon.com/gp/product/151...
"The Best Mental Math Tricks" teaches how you can look like a math genius by solving problems in your head (rated 4.7/5 stars on 4 reviews) www.amazon.com/gp/product/150...
"Multiply Numbers By Drawing Lines" This book is a reference guide for my video that has over 1 million views on a geometric method to multiply numbers. (rated 5/5 stars on 3 reviews) www.amazon.com/gp/product/150...

[@MindYourDecisions]

So here's a challenge problem: why are the two methods equivalent? I made some progress but didn't figure out the entire proof before posting the video. Here's what I came up with, help me fill in the details and check if this is correct. If enough people want, I can make a "footnote" video that explains this. In method 1, counting the number of "patterns" does give the binomial coefficients 1, 3, 3, 1, just like Pascal's triangle. This is not a coincidence! Let's say we pick r unique digits. How many patterns are there? Well we need those numbers to fill 4 spots. So we have the sum of r variables equal to 4. But we need those to be positive variables, as we need at least one of each digit. If we force each digit to appear once, then we have 4 - r stars left. So we count the number of non-negative solutions to r variables summing to 4 - r. This ends up being C(3, r - 1) = 3 choose (r - 1). Thus, the number we count in method 1 equals: C(10, 1)C(3, 0) + C(10, 2)C(3, 1) + C(10, 3)C(3, 2) + C(10, 4)C(3, 3) This equals C(13, 9). If we have n digits, and the code involves k digits, then we have proven: C(n, 1)C(k - 1, 0) + C(n, 2)C(k - 1, 1) + ... + C(n, k)C(k - 1, k - 1) = C(n - k + 1, k - 1) I believe this is a form of Chu-Vandermonde's identity, but I was not exactly sure: en.wikipedia.org/wiki/Vandermonde%27s_identity

[@GaborRevesz_kittenhuffer]

MindYourDecisions, in general, let the number of keys be k and let the number of key presses be p. (In this problem k=10 and p=4). We can uniquely describe every code equivalence class by specifying how many times each key gets pressed. For fixed k and p, there is a 1-to-1 correspondence between the set of code equivalence classes and the set of strings each consisting of exactly k-1 '#'s and exactly p '+'s, wherein the number of '+'s immediately preceding the n-th '#' specify the number of times key n gets pressed; any '+'s at the end specify how many times key k gets pressed. The number of such strings -hence code equivalence classes - is p+k-1 choose p, i.e. C(p+k-1, p) = (p+k-1)·...·(k) / p! and in particular C(13,4) = 13·12·11·10 / 4! = 13·11·5 = 715.

[@raseclilac9752]

MindYourDecisions I figured out 1 way that I used to solve this problem.....so I have some special cases(E means Equal and D means Different and when I use D1D1 I mean its two differents from the equals but they are same number like EED1D1 could be 1122) so I have these possibilities: EEEE/EEED/EED1D2/EED1D1/DDDD....for the situations(in order) we get 10/90/360/45/210....sum it and u get 715.....ps:sorry for bad english

[@nimsraw]

MindYourDecisions For n != m and n != 0, i.e. for an inner element, the element (m n) of the Pascal's triangle can be obtained by adding up the two elements over it (in the previous row) . So (m n) is equal to (m-1 n-1)+(m-1 n). In the second solution you used the element (13 9) so according to said: (13 9) =(12 8)+(12 9) =(11 7)+(11 8)+(11 8)+(11 9) =(10 6)+(10 7)+(10 7)+(10 8)+(10 7)+(10 8)+(10 8)+(10 9) =(10 6)+3*(10 7)+3*(10 8)+(10 9) Since the triangle is symmetric, i.e. (p q) = (p p-q), that is equal to: (10 4)+3*(10 3)+3*(10 2)+(10 1) Which is the expression you obtained with the first method.

[@JohanniklasLp]

nimsraw You are right, i just wanted to write... not the same but something equivalent. But looking at the triangle i found one (simple?) equation for method 1: (10 1)×(3 0)+(10 2)×(3 1)+(10 3)×(3 2)+(10 4)×(3 3) = (13 9) = (13 4) = 715. To make it easier: For A = Numbers in the lock and B = Number of unique digets (10 most of the time i guess) take f(X)=(B X) × ((A-1) (X-1)). The solution is the sum of f(X) for X=1 to X=A. But this method only works if you have less or the same count if Digets in the combination (

[@nimsraw]

Johanniklas You're also right. I came up with the same thing that the factors multiplying each term are the values of the row p-th row in Pascal's triangle. The expression you mean is: f(p,d) = SUM(i=1 to p)[(d i)*(p-1 i-1)] Being p the positions (places) in a combinationfor the lock and d the number of digits to use. (Notice in the last term the i-1, you put it as a constant (B-1) and it's not.) In the other hand, to calculatel the cases with more positions than possible digits, think that a new position give us the option to introduce in it, and for every combination used before, each of the possible digits to form a new unique one. So for those cases the solution would be, if I didn't make any mistake: f(p,d) = (SUM(i=1 to p)[(d i)*(p-1 i-1)])*d^e Being e the number of extra positions wich is p-d. So, to sum up: f(p,d)= SUM(i=1 to p)[(d i)*(p-1 i-1)] for p

[@nathnlturner68]

A true combination lock! All real locks are permutation locks

[@MindYourDecisions]

That's great! I added this to the title.

[@nathnlturner68]

I love you MindYourDecisions!

[@kennkong61]

An actual combination lock, not a real one.

[@nathnlturner68]

kennkong61, an actual combination lock, and a real combination lock are the same!

[@davidmam]

not true. there are numeric door locks which are combination and some which are permutation

[@JeffersonWolski]

Another way to think of this is simply counting the number of ways to place 4 stones into 10 jars, which is equivalent to the original problem. When you think of it this way, its pretty clear that we need 9 bars to partition into the grouping for 10 jars. Then you just put in a star for each stone. Now, it's 9 bars plus 4 stars and 13 choose 4, just like the original problem.

[@ste1l1]

I used Python: from itertools import combinations_with_replacement as c print len(list(c(range(10), 4)))

[@angrytedtalks]

Blow the safe. Now I'm going to 9 bars.

[@TheChamp1971]

I figured it out correctly within a minute..... by using the first method. (I would have never discovered the second method on my own in a million years, Lol)

[@GordieGii]

Show-off. It took me half an hour (actually, I'm not sure how long, but that's my story and I'm sticking to it) to derive the combinatorics from tons of examples because I haven't used them in over 30 years.

[@iSammax]

I used dynamic programming here, because it's a pretty typical problem. [warning, C++ code ahead lol] int R(int position, int lastUsedDigit, vector& dp) { if (position == 4) return 1; int &result = dp[position][lastUsedDigit]; if (result != -1) return result; result = 0; for (int digitForCurrentPosition = lastUsedDigit; digitForCurrentPosition < 10; ++digitForCurrentPosition) result += R(position + 1, digitForCurrentPosition, dp); return result; } int main() { vector dp(4, vector(10, -1)); cout

[@kokoro2542]

Saw "puzzle", got excited, then saw it depended on being able to do complicated maths.

[@Navajonkee]

Not really complicated, it's just combination with repetition, a pretty simple formula that's taught in school. I was kinda disappointed that it wasn't really a "puzzle" as it was just a typical combinatorics problem.

[@RafaelMunizYT]

@@Navajonkee logic puzzles >> maths puzzles

[@GregCannon7]

Should be 10 multichoose 4, which equals 13 choose 4, which is 715? I guess combinatorics kinda spoils the fun here.

[@mienzillaz]

Yup

[@kevina5337]

It's just combinations with repetitions allowed, which statistics teachers think is super high level math for some reason? (N+k-1) choose k Lol

[@theophiluskoay5905]

but why is it 13C4 , i thought it was only 10 numbers ?

[@davidmam]

@@theophiluskoay5905 because you are putting the numbers and the boundaries between the numbers in order.

[@mike1024.]

@@theophiluskoay5905 the 10 numbers represent 10 categories oh, and you can distinguish between those 10 categories by placing 9 bars between them. You then place 4 objects within the categories, for a total of 13 objects being arranged. As explained in the video, we really only care where the stars are with relation to the bars.

[@acoral1035]

The second method is beautiful.

[@bailey125]

Or you could use the equation: [(r + n - 1)!] / [r!(n - 1)!]

[@alexhu7939]

baileyboy125 exactly! This is the definition of K-combination multisubset

[@boru3413]

You have taught me so many great lessons, Thanks Presh Talwalker, You're AMAZING

[@twwc960]

I used the formula of method two as it is a fairly well-known combinatorics problem. It is really the multiset counting problem: how many n-element multisets are there where the elements are chosen from a set of r elements. The stars and bars method is the common way of deriving the formula. It is also one of the "twelvefold way" problems: how many ways are there to distribute n indistinguishable balls into r distinguishable buckets where we can have multiple balls in a bucket and we can have some empty buckets?

[@thalesogoncalves1]

I solved it on two different ways as well. My first is not exactily but very similar to the first of yours. But my second way uses burnside's lemma. You have to model the problem as the permutation group S_4 acting on the set of all possible lock codes and count how many orbits are there. Naturally, the answer is again 715.

[@kenhaley4]

I did it a slightly different way: There are 5 possible patterns: aaaa, aaab, aabb, aabc, and abcd. where a, b, c and d represent unique digits in the solution. E.g. 1133 would be an aabb pattern. Here is a count the number of solutions in each pattern. aaaa - 10 (one for each digit) aaab - 90 (10 possible a's and 9 different b's for each one. aabb - 45 (10 possible a's and 9 different b's for each one, but every possibility gets counted twice, so we divide by 2. E.g. 2255 is the same as 5522). aabc - 360 (10 possible a's, and for each one there are 9 possible b's and 8 possible c's. Again we have to divide by 2 because aabc is the same as aacb. so 10 x 9 x 8 / 2 = 360) abcd - 210 (10 choose 4 = 210). Sum = 715. But I love the stars and bars method. Very elegant!

[@romywilliamson4981]

This is how I learnt to visualise the method 2: imagine that you are programming a robot to pick the combination of numbers. There are a series of baskets are arranged in a line. The first contains only 0's, the second contains only 1's, etc. To program the robot you type in a sequence of the commands (->) to move forward to the next basket or (*) to pick up a number from the current basket. Clearly there must be four (*) symbols as you need four numbers. You have to get from the first to the last basket, and there are 9 gaps between 10 baskets, so you need 9 (->) symbols. The number of unique combinations of numbers is the same as the number of unique 'programs'. The program has a total of 13 symbols, four of which must be (->). So it's 13C4=715.

[@BigDBrian]

This is logistically equivalent to the way I learned it: with the number of fastest ways to get from point A to point B on a grid. This ends up being n+k choose k if you have to move n spots horizontally and k spots vertically. When approaching a problem of combinations with repeats, you can label the vertical lines with each value (1 through 9 in this case), which makes for n=8 since there's 1 less times you need to move right than there are vertical lines. Then, how tall the grid has to be, is of course 4, so k=4. This gives a really nice visual touch to it, where any solution is basically just a certain set of stairs. This is equal to your robot analogy, since you can imagine the robot checking the first value, if it needs to then it will go up as far as it needs, then moving to the right, doing the same, etc, basically climbing those stairs.

[@Tammyaway]

I immediately used the formula given at the end, it is a well known formula for choosing N out of R with repetition and without regard for order.

[@mike1024.]

I believe this is one of the more routine problems that have shown up on your channel, at least from the perspective of an introductory combinatorics class. When order doesn't matter but repeats are allowed, you immediately go stars and bars. I think you could bypass your explanation with the x_i stuff by simply considering the number in numerical order as a unique representation of that particular code and then just saying it's a matter of placing the stars among the bars.

[@gilbertoguerra]

I used: (10+4-1)!/(4!x(10-1)!) = 715

[@JohnRandomness105]

I did perhaps the grungiest way possible -- definitely more grungy than either solution given. If the four digits are k, l, m, and n, there is a unique combination with k

[@davidmeijer1645]

Nice problem...and timely! Will present to class tomorrow morning

[@donaldasayers]

This is a classic multichoose problem. I always visualise it as the number of paths along an array 5 high and 10 along. Start in the bottom left, finish in top right. First column represents the 4 1s, with zero 1s being the bottom square, the second column the 2s and so on. A step up chooses one of that number a step right skips. Any combination of 4 steps up and 9 right works to get you to the top right corner. The total path length is 9+4 and you are simply choosing where to put the steps up hence the solution is 13 Choose 43=715.

[@darnellyiadom3596]

Did anyone else notice at 4:05 the 4th row of Pascal's triangle (1331) in the possible patterns?

[@cuchulainn6478]

I saw it to. And I noticed that when the length of the unlock code is 1, 2, or 3, the number of possible patters you would need to multiply by would be 1, 11, 121; which just so happen to be the first 3 lines of Pascal's triangle. I don't know if this pattern holds true for longer code lengths (too lazy to figure it out).

[@darnellyiadom3596]

Isn't maths just so beautiful

[@kristofersokk1580]

Pat Miller yes, it's directly related, we can read every possible solution to (n choose k) from the Pascal's triangle, either PBS Infinity or Numberphile has a video about that, can't remember exactly which video

[@sadhlife]

Pascal's triangle pops everytime you talk about stuff like permutations combinations, and ESPECIALLY in binomial theorem.

[@dujas2]

Think about this using stars and bars. When there's one unique digit or four, we know each bin gets one star or one bin gets them all. In the other 2 cases, put one star in each bin. Now use stars and bars to distribute the remainder. We either have 2 bins and 2 stars or 3 bins and 1 star. Either way is 3 choose 1.

[@threej4pope]

The "quick elegant" solution was way more complicated and confusing than the first.

[@emiyareikwut-ukwa4005]

If you know stars and bars, it's faster to compute

[@aboudawik7973]

Suppose the digits a, b, c and d where by ascending order. a has 10 possibilities b has 10-a possibilities for each a => possibilities of a&b = 10-0 + 10-1 +...10-9 = 55 c has 10-b possibilities and a has b+1 possibilities for each b=> possibilities of a&b&c = 1×(10-0) + 2×(10-1) + 3×(10-2) +...+ 10(10-9) = 550-330 = 220 d has 10-c possibilities and b has c+1 possibilities for each c and a has b+1 possibilities for each b => possibilities of a&b&c&d = 1×(10-0) + (1+2)(10-1) + (1+2+3)(10-2) +...+55(10-9) = 10 + 27 + 48 + 70 + 90 + 105 + 112 + 108 + 90 + 55 = 715

[@aliasmask]

I'm curious what the solution is if you consider when going through the permutations that the last part of the code combines with the first part of the next code. For example, if you start with 0000 and go to 9999 for your next code that you've also completed 0009,0099,0999. How can you optimize the code entry to get the least number of tries.

[@jesan733]

One could add a question: What's the minimum number of keystrokes you have to enter to try out these 715 combinations? E.g. if you use 5 keystrokes, you can test 2 combinations: 14364 will test both 1436 and 4364. Trivially, there's a lower bound of 718 keystrokes, first 3 and then each new keystroke would test a unique combination. But is it possible to sequence keystrokes in such an optimal way?

[@marcusheeboellhansen8563]

We learned these types of problems in school and I used this formula: (n-1+r)!/((n-1)!*r!). Where n=10 different numbers to choose from and r=4 numbers to type on the keypad

[@31-DZ]

if we have 2 degits, the code can still be written with just 1 degit aaaa or bbbb in the case of 3 it can be written with 1 or 2 degits aaaa, bbbb, aabb, and in the case of 4 digits it can be written with 1, 2 or 3 degits aaaa, bbbb, cccc..... etc

[@jarencascino7604]

FethiKara no

[@ottoschullian7018]

There is actually another very easy way of getting the solution: essentially the question is equivalent to how many series (w_1,...w_4) can you find with w_i in {0,1,...,9} with w_1

[@saxbend]

10C4 for 4 different digits. 10C2 for two different digits, multiplied by 3 for 1,3 2,2 and 3,1 occurence counts for each pair, 10C3 for exactly one repeated digit multiplied by 3 for the 3 possible digits that could be repeated in each group of 3, and finally 10C1 for four identical digits. 210 + 3x45 + 3×120 + 10 = 715

[@alexissandoval1539]

I like your videos friends. They help a lot of to the mind.

[@shubhamvishwakarma8309]

Wow very clever solution. I am amazed!!!

[@corvididaecorax2991]

Hmm. An interesting related question: assuming the lock doesn’t lock out, and only keeps track of the last four digits entered regardless of how many came before, how long of a sequence is required to test all the possible combinations? I don’t have an answer, but my first narrowing down would be that each number entered can at most be part of four potential four digit sequences. So at a very minimum the sequence would need to be 716 numbers long, due to the rounding. Definitely more than that just because of the ends not being part of four possible combinations.

[@opytmx]

Seems to be a combination problem with 4 out of 10 (w/repetitive digits): C (n,k) = (n-1+k)! / (k! * (n-1)!) C (10,4) = 13! / (4! * 9!) = 715 > Nice explanation in the 2nd part!

[@papousekerikfuckinglegend1067]

i tried to do it like this: 1) compute count of all combinations (10 ^ 3 = 1000) 2) discount count of numbers which makes all same like 1-1-1, 2-2-2 = 10 3) divide by possible combinations per one line (1-2-3 can be altered in 3 combinations) = 990 / 3 = 330 4) now add count from 2) = 330 + 10 = so i was thinking 340, but somewhere is mistake then. it works for 2 digits and 2 length, and 2 digits and 3 length.

[@kennkong61]

Exact wording is critical in word problems. There is one, and only one, different combination for *A* safe. There can be many different *possible* combinations, but only one actual combination for *A* safe. Or you could say there is a *MODEL* of safe, removing the explication that there is only one safe.

[@ZeBestBagguetCrGd]

we learned about dis combo and permutations in algae bra 2

[@DennisRanke]

I figured that for a two digit code the number of codes would be 1+2+3+4+5+6+7+8+9+10 = 10*(10+1)/2 (counting the codes that have their digits in ascending order, like 00, 01, 11, 02, 12, 22, etc...). I spent a lot of time trying to extend that to 4 digits and ended up with 10*(10*(10*(10 + 6) + 11) + 6)/24 = 715. So I got to the correct number, yay, but it was super convoluted.

[@Minecraftster148790]

I always thought that when trying out every solution instead of doing 0001,0002... you could do 00012 or something and then you would have tried out 2 codes (0001 and 0012) with only 5 characters. Is there a nice way to generate the optimal sequence to do this or find the total length?

[@shy-watcher]

I expected the question to be "how many button presses do you need to brute-force the combination"? For example entering s=01234567 the lock would open after "4" if the code is 4321. What is the minimal length of s that will open every lock?

[@Pining_for_the_fjords]

Method 1 was far easier for me to understand. But how do you calculate the x-choose-y values?

[@encounteringjack5699]

Thanks this video was very educational for me. I was about to ask a question but while typing in the question I figured out the answer to it. The question had to do with the difference between permutations and combinations but then i realized this is more of a combinations question which why both methods work. I was using a completely incorrect method way of going about this when I tried to solve it, because I used a way to solve for how many different permutations there are instead of how many combinations there are. I feel stupid now lol I probably would've gotten the right answer if I used the n!/k!(n-k)! (n choose k) instead of just the n!/(n-k)! That I was using, but that's ok so long as I don't make the same mistake the next time.

[@OneWeirdDude]

I used the second method, but with slightly modified cosmetics. I asked myself, how about two digits? Order doesn't matter, so sort them in ascending order. The first digit can be anything 0-9, while the second digit is the same or greater. So it's 10 + 9 + 8 + 7 + ... + 2 + 1 = 55. The three digit case is similar. If the first digit is 0, the case is the same as the two-digit case. If 1, it's still the two-digit case, but with no zeroes. Thus, add up the numbers 1-9. If the first digit is 2, there are eight possibilities for the next digit, so you add up 1-8, and so on. Thus, the answer is the sum of the first 10 triangular numbers, or sums of numbers 1 to n - i.e. the 10th tetrahedral number. The four-digit case is also similar; just add the tetrahedral numbers. The sum of the first 10 can be verified to be C(13, 9), the answer to the question.

[@YogeshPersonalChannel]

How does the second method account for different patterns of same combination of digits. For example for one star in x1 and three stars in x7. I get 1777. But how does it ensure other patterns like 7177 are counted even?

[@samarth.patel21]

Unlock codes are 4 because there are only 4 arrangement of 4 correct numbers that unlocks the safe, others don’t unlock the safe, meaning they are not unlock codes.

[@tetrix1993]

I learned this in my Discrete Math class!

[@EanSeki]

If order is irrelevant, than aaab is the exact same thing as abbb. it was said 0001 is the same as 1000. meaning there is two quantities of digits either aaab or aabb, 3 of one and 1 of the other, or 2 of one and 2 of the other. which the same could be said about abca, abcb, and abcc all being the same thing just rearranged. aabc, bbac, ccab, 2 of one, one of another, and one of another. giving (1 x 10 = 10) + (2 x 10 x 9 = 180) + (1 x 10 x 9 x 8 = 720 ) + ( 1 x 10 x 9 x 8 x 7 = 5,040) = 5,950

[@simonhollad5511]

aaab being 0001 means 1000 would be baaa, not abbb.

[@marcvanleeuwen5986]

Why do you (and people in general) use the word "unique" when you mean "distinct"? When you say a code has 3 unique digits, it actually has 4 (occurrences of) digits, but 3 distinct digits. Of those 3 digits only 2 are _unique_ in the code (the remaining one is used twice, so it is not unique).

[@youcan_change_handle_3june_]

what 4 digits . sorry for bad understanding of maths

[@marcvanleeuwen5986]

@@youcan_change_handle_3june_ If a code is say 2021, then there are three distinct digits: 2,0,1. Of those digits two are unique in the code: 0 and 1 (at positions 2 respectively 4). The digit 2 is not unique in the code, as it occurs twice (at positions 1 and 3).

[@thekinginyellow1744]

because they have a poor grasp of english

[@SamvitAgarwal]

Hey. Regrading the first method, why did we have to add up the combinations of 1,2,3 and 4? Why isn't it just 10 choose 4 or 210?

[@michaelbrobbel8753]

Because digits can be duplicated, 10 choose 4 = 210 with out adding the results for 1, 2, and 3 would only account for unique digits being used in the combinations

[@Scynthescizor]

The way this question is written makes it sound like the answer should be 1. The door opens only if the "correct" 4 digits are entered in any order, and there is an equivalency between every permutation of those 4 digits. It implies that there is only one correct unlock code.

[@KetsubanZero]

My count was a little bit different, first of all i've started with the no repeated digit combinations (10*9*8*7)/(4*3*2)=210 then the all the same digits 10 then all the 3 repeated digits 10*9 = 90 (since we have to exclude the 10 all the same digits) then te 2 repeated digits 10*9*9/2 = 405 (since we have to exclude all the 3 repeated digits and 4 repeated digit, then since the remaining two digit can be arranged in 2 ways while the two pairs are counted twice we need to divide by 2 because (0012 and 0021 are the same, while 0011 and 1100 are the same too) so: 210+10+90+405 = 715

[@digxx]

Here is a different way of counting: The number of ways to set the lock is 10^4=10000 = 10*9*8*7 + 10*9*8*binomial(4,2) + 10*9*binomial(4,2)/2 + 10*9*binomial(4,3) + 10. The right hand side is the decomposition in terms of relevant quantities. The first term is the number of ways to write a number with distinct digits abcd. The second is the number of ways to write a number were two digits are equal (e.g. aabc). Binomial(4,2) counts for the fact of ordering these 2-pairs. Then there are binomial(4,2)/2 2-pairs (e.g. aabb). Binomial(4,3) is the number of ways to write a given number of the lock with 3 equal digits and 1 distinct (e.g. aaab). Finally the last term refers to the case were all 4 digits are equal (aaaa). From this decomposition it is obvious that the number of distinct unlock codes is given by: 10*9*8*7/4! + 10*9*8/2! + 10*9/2! + 10*9 + 10 = 715. A permutation of a number of distinct digits is also a number with distinct digits for the same unlock code of which there are 4!. The binomial coefficient in the above formula counted for the number of ways to arrange the 2- or 3-pairs and can just be left out. The 2-pair case has two additional distinct digits (in the case of e.g. aabc b and c can be permuted while abac was contained in the binomial coefficient, and in the case aabb a and b can be permuted) of which the permutation group size is 2!.

[@pauleatshotdogs]

Hi, love your videos. Thanks! However, as someone who used to work opening safes, your video does not provide the simplest solution to this problem. All that is needed is a little bit of fingerprint dust (I know it's messy), but you'll find out your 4 numbers right away. Happy burgling!

[@uiuiuiseraph]

Its a combination with repitition so it should be n+k-1 over k. So 10 + 4 -1 over 4 which gives us 715.

[@Kino-Imsureq]

I was happy i guessed the answer correctly before the reveal

[@arthur3424]

If a*b+a*c+7 is a multiple of 18, prove that a+b+c is a multiple of 6.

[@cryptexify]

Reducing ab+ac+1 mod 2, we get a(b+c) = 1 (mod 2). So both a and b+c are odd. Same for mod 3, we get a(b+c) = 2 (mod 3), so one of them is 1 and the other is 2 mod 3. In either case, you're adding a to b+c. Since they're both odd, their sum is even. Since one of them is 1 and the other is 2 mod 3, then their sum is 0. So a+b+c is divisible by 2 and 3, and therefore divisible by 6.

[@arthur3424]

I managed to get a simpler solution (C is the symbol of congruent) a*b+a*c+7 C 0 mod 18 a*b+a*c+7 C 0 mod 6 a*b+a*c C 5 mod 6 a*(b+c) C 5 mod 6 With this last equation we can conclude that a is congruent 5 mod 6 and b+c is congruent 1 mod 6 (or vice versa) , then we have a+b+c C (5+1)mod6 a + b +c C 0 mod 6

[@dustinbachstein3729]

We actually learned this formula in school (though it wasn't necessary in the final exam) :D

[@anmolbehl8572]

nice trick bro 👍👍 will surely try this

[@MrKockabilly]

5:05 method 2 is NOT an alternative method that will get to the answer "more directly and with fewer computation". Method 1 is.

[@TheMichaelru]

It might interest some of you to know that the problem at the end was the difficult part of a question on a first year maths exam set by the University of Cambridge two years ago.

[@GordieGii]

My answer is 715 (10!/9!)/1! + 3(10!/8!)/2! + 3(10!/7!)/3! + (10!/6!)/4! = 10 + 135 + 360 + 210 = 715 I figured 0000 to 9999 is equivalent to 0 to 9 0001 to 8889 = 01 to 89 0011 to 8899 = 01 to 89 0111 to 8999 = 01 to 89 0012 to 7789 = 012 to 789 0112 to 7889 = 012 to 789 0122 to 7899 = 012 to 789 and finally 0123 to 6789 I vaguely remembered that combinations and permutations used a lot of factorials, but that was over 30 years ago, so I did a LOT of examples to come up with the total, and worked backwards to the factorial form above. (might not be the best form but that's what I came up with) I assume this will be similar to one of the methods I'm about to see, at least in concept, if not efficiency.

[@supercat765]

I used Neither of the ones shown. I came up with a way to simply count them. Have the digits be sorted from lowest to highest, that way each unique combination also has a unique order. the first digit, I'll call A, has 10 digits to choose from 0-9 the second digit B has 10-A choices, if A=0, B can be anything. if A=9, B can only be 9, as the digits can only match or above the previous digit the second digit C has 10-B choices the second digit D has 10-C choices Then through a slightly convoluted thought process that I was fairly certain was flawed in some way I ended up putting this into wolfram alpha sum (sum (sum a, a=1 to b), b=1 to c), c=1 to 10 getting the correct answer.

[@hm7509]

you must patent did you figure it out

[@KarolKarasiewicz]

I believe Your formula works only if number of options (in Your example - digits) is bigger than the length of the sequence. If not - I can't compute binomial coefficient (maybe it's possible?)

[@yurenchu]

Well, let's see... Suppose the value of each digit is either 0 or 1; so we're looking at n-length binary codes. For example, if n = 4, then the possible codes are 0000, 0001, 0011, 0111 and 1111, which are 5 different codes. And if n = 5, then the possible codes are 00000, 00001, 00011, 00111, 01111 and 11111, which are 6 different codes. It's not hard to see that for n-length binary codes, there are n+1 different codes. Now using the formula: with r = 2 (because binary) (n+r-1) choose (r-1) = = (n+2-1) choose (2-1) = (n+1) choose 1 = (n+1)! /( n! 1! ) = n+1 which corresponds to what we calculated before. I see no problem with the binomial coefficient. Why should there be a problem with the formula when n > r ?

[@gcewing]

Here's a bonus problem. Suppose the lock is designed so that it opens whenever the last four digits entered are a valid code. In that case, if you're trying to crack the safe, you can overlap your attempts to reduce the number of digits you have to enter. The question is: What is the shortest sequence of digits that covers all the possible codes?

[@UltimaDoombotMK1]

Trick question, it's pi

[@Trephining]

Grab three socks from the drawer, guaranteeing you get at least a pair of either white or black socks

[@melissa9898]

Is the question stated correctly? If the question is how many codes are there then the answer would be either 1 or 24 as the code is already in place. You can input the code in 24 different variants so if you can place them in any order no specific one is correct. If the question was how many POSSIBLE codes are there it could be 715 as it could be any code without a specific 24 codes to chose from.

[@leif1075]

An interesting challenge is is there a permutation stars and bars formula..

[@Lucaash]

Well, this is just the number of combinations with repetition. Isn't this a well-known formula similar to regular combinations, variations or permutations?

[@nawedshaikh4333]

Though very rare but I did figure it out because I knew this is a question of combinatorics

[@mauriziomarenco6259]

I brute-forced it by calculating how many possible combinations per series of 10 numbers. 10×10+9×11+8×12+7×13+6×14+5×15+4×16+3×17+2×18+1×19. Not the most elegant solution, but it was fun nonetheless!

[@DucciVinci]

Did I seriously just calculate this using Burnside's lemma and miss the stars-and-bars solution despite having done an entire presentation on stars-and-bars at school 10 years ago? *facepalm*

[@cryptexify]

Yeah, you're not alone. I immediately thought of Burnside's lemma (forgot what it was called, but I had the idea in mind). I had a challenge a few months ago that required I learn about it, so I guess it's because of that.

[@DucciVinci]

Exactly the other way around for me - I immediately knew that Burnside's lemma should be used, I just had to ask Wikipedia what it exactly stated^^ It also works and is basically just the first of the presented solutions - written in the language of a mathematician :)

[@TheMichaelru]

How did you use representation theory to solve this? What group are you considering? I assume it was S_4.

[@DucciVinci]

Yes. What we essentially want to know is the number of orbits the operation of S_4 on the set of 10,000 possible 4-digit codes. By Burnside's lemma, this equals the average number of codes that are fixed by an element of S_4. To calculate the average, we need to add the number of codes fixed for all elements of S_4. How many codes a permutation fixes depends on its number of "cycles", since the permutation only fixes the codes which has the same digits in each of the "cycles". The identity element in S_4 for instance has 4 independent cycles, so it fixes 10^4 codes. We now examine the group S_4: 1 element has 4 cycles => 10,000 6 elements have 3 cycles => 6,000 11 elements have 2 cycles => 1,100 6 elements have a single cycle => 60 The sum is 17,160. Since S_4 has 4!=24 elements and we want to calculate the average, we have to divide and indeed, 17,160 / 24 = 715.

[@cryptexify]

Did you combine two conjugacy classes? Because there's 5 ways to partition 4, not 4.

[@Tyranisaur]

The general solution misses out on an aspect that isn't covered by this problem. What if you can only use a digit a limited number of times? I solved the problem using a method that can deal with that constraint. I used dynamic programming. Imagine a sub problem here. You have to pick n digits from a digit set of the first m digits. The solution to the problem is the sum of the solutions for the sub problems with a digit set of the m-1 first digits, and all numbers of digits

[@cih2007]

Java solution, output: "Unique combinations: 715". public class Combo { public static int order(int combo) { List digits = getDigits(combo); Collections.sort(digits); int orderedCombo = digits.get(0) * 1000 + digits.get(1) * 100 + digits.get(2) * 10 + digits.get(3); return orderedCombo; } private static List getDigits(int combo) { ArrayList digits = new ArrayList(); digits.add(combo / 1000); digits.add(combo % 1000 / 100); digits.add(combo % 100 / 10); digits.add(combo % 10); return digits; } public static void main(String[] args) { ArrayList savedCombos = new ArrayList(); boolean found; for (int combo = 0; combo

[@MrRyanroberson1]

wait! when you did 13 chose 9, that's the formula for 13 chose 4. (though identical, not having the algebra there is skipping steps, which is always bad practice. and otherwise, you should have said to place 4 stars and have the 9 bars fill the remaining empty spots.) also for the generalization at the end, if you had x0 through x(r-1) as you did in the original equation, the formula would have worked out nicer. n+r chose r

[@singhbrothers1346]

Why in first method you didn’t choose the same no. Like 2 unique digits are chosen by 10c2 but remaining 2 same digits also needs to choosed by 9c1.....?

[@arnaudj-d1896]

Woow I found the answer but only with observation not really with algebra but it worked ! All the solution explained in this videos are not at my actual level.....

[@PhrontDoor]

I see YOUR three codes for #2, with AABB, ABBB, AABB, but what about ABAA, BBAB, or BBAA(possibly just a re-ordering of AABB) but it's still a unique pattern.. did I miss something? at time-code 2:40ish

[@copperfield42]

nice solution, I just use simple brute force to count it all...

[@bolu7358]

sorry i have always had an issue with combination and permutation, can anyone explain when to use them

[@okaro6595]

One could replace the r-1 with n. This makes it easier to remember - that is instead of C(13,9) one calculates C(13,4)

[@egilsandnes9637]

Okaro X Agreed. Also, I think it's kind of more intuitive to place the stars, rather than the stripes.

[@diosicon3846]

Can someone explain the ways to choose digits what is this column exactly

[@fiorinidaniele]

The problem may be easily solved if you recognize that you are asking for the number of combination with repetition. Combination because the order is not important for the group identification. Repetition because the symbol can be repeated. In the end the problem is asking for computing the number of combination with repetition with k=4 and n= 10. (n+k-1)!/(k!*(n-1)!).

[@user-ii5ch8nw6s]

Actually method 2 (using the number of non-negative integer solutions) is taught in Taiwan, so I can figure it out even I'm not a genius.

[@grandexandi]

This feels like something I SHOULD know how to calculate...

[@genius11433]

Can someone please help me with the algebra? The combination-with-replacement formula, which some people in the comments already knew could have been used here, is (n + r - 1)! / [r! (n - 1)!] However, Presh's answer is (n + r - 1) C (r - 1) . When I run that through the combination formula and do the algebra, I get (n + r - 1)! / [ *n* ! ( *r* - 1)!] . Did I somehow make an error in my math? Or is [r! (n - 1)!] somehow equal to [n! (r - 1)!] ??

[@KingFredII]

Instead of 9 bars you could also take 4 stars, so 13 over 4 instead of 13 over 9. The result is the same.

[@desmondc2706]

So the second method is actually partition formula？

[@chamcham123]

You should also have mentioned that 13 choose 4 (stars) is equal to 13 choose 9 (bars)

[@thomasaskew1985]

You'd better have some good insurance with a weak lock code like that. LMAO

[@kevina5337]

This is a "combinations with repetition" problem, which is the material that always gets skipped over in elementary statistics for some reason. The formula isn't even that hard, it's just (n+k-1) choose k lol

[@apxprdtr_mge]

I almost immediately figured out it was a combination with repetition. Going by the subtraction method didn't make sense to me since there was 10 000 possible passcodes that you could type in.

[@FerroMancer]

Wait - at 3:49, what about abbc?

[@sethapex9670]

combinatorics goes way over my head.

[@katzen3314]

I got 715 in a really bad way. With summations like sum(a=1 to 5)( sum(b=1 to a)( sum(c=1 to b)( sum(d=1 to c)( ... ) ) ) Which I basically just chose from thinking about the problem. But wolfram could only do up to 4 summations, but I googled the numbers 1,5,15,35,70 and found they were numbers in pascals triangle (pentatope numbers) and found the 10th number. Figured it had something to do with binomial but couldn't figure out exactly how.

[@GaborRevesz_kittenhuffer]

Let D be the number of digits on the pad (so that S = {0, 1, ..., D-1} is the set of digits) and let L=4 be the length of the codes. Each code equivalence class corresponds to specifying for each digit k in S the number ω(k) of times k occurs in the code. So the set of code equivalence classes is in 1-to-1 correspondence to the set T of D-tuples (ω(0), ..., ω(D-1)) such that Σ[k in S] ω(k) = L with 0 ≤ ω(k) ≤ L for each k in S. In turn, T is in 1-to-1 correspondence to the set of strings composed of L "*"s and D-1 "|"s, with (ω(0), ..., ω(k), ..., ω(D-1)) corresponding to the concatenation of "*" ω(0) times, "|", ..., "|", "*" ω(k) times, "|", ..., "|", "*" ω(D-1) times. Therefore the number of code equivalence classes is C(L+D-1, L) = C(4+10-1, 4) = 13·12·11·10/4! = 13·11·5 = 715.

[@kokainum]

925 Ofc I had to make mistake. I was using method 1 but I guess I made error at calculations. Oh right. 3*4 is obviously not 6. ;) I guess it matters. :) I liked method 2. I actually knew it, shame I didn't think about it. Good reminder.

[@juanjosefernandez1590]

I did it with the pascal triangle You start in the one of the top, then you move 4 numbers down to the left, then 9 numbers down to the right and you’ll get 715

[@VedantArora]

Can you tell why it worked?

[@rickromney2150]

Without looking at the solution, here's my take: There are only 5 possibilities: a) all numbers are unique b) two numbers are the same and the other two numbers are unique c) there are two pairs of same numbers d) three numbers are the same, the other is different e) all four numbers are the same The order doesn't matter so for each digit, we just multiply the number of remaining options for the scenarios. Computing the number of ways for each possibility: a) 10 x 9 x 8 x 7 (unique digit * unique digit * unique digit *unique digit ) = 5,040 b) 10 x 9 x 8 (pair * unique digit * unique digit) = 720 c) 10 x 9 (pair * pair) = 90 d) 10 x 9 (trio * unique digit) = 90 e) 10 Adding all possibilities, we get 5,950 Now, let's see. May be my solution wasn't the short cut. Edit at 4:32 - whoops, i need to make some divisions to account for duplicates in the scenarios because of different orders: a) 10 x 9 x 8 x 7 (unique digit * unique digit * unique digit *unique digit ) = 5,040 / 4! = 210 b) 10 x 9 x 8 (pair * unique digit * unique digit) = 720 / 2! = 360 c) 10 x 9 (pair * pair) = 90 / 2 = 45 d) 10 x 9 (trio * unique digit) = 90 e) 10 Total: 210 + 360 + 45 + 90 + 10 = 715 There, fixed

[@MrRyanroberson1]

once my grandpa and I were discussing his cats: he has 10 cats, but we never see more than 6 at a time, so maybe there are 6 shapeshifters choosing 10 skins. this problem is similar to that of this video, but ours had the rule of no repeated cats. without such a rule, you can just go: sum(sum(sum(sum(n)))). sum(n)=n(n+1)/2, (sum(n^2)+sum(n))/2=.... its long and inefficient, but t works.