Can You Solve The Code Lock Riddle? A GENIUS Math Shortcut
ฝัง
- เผยแพร่เมื่อ 5 ก.ย. 2024
- 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.c...
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: mindyourdecisio...
Twitter: / preshtalwalkar
Facebook: / 168446714965
Google+: plus.google.co...
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...
"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...
"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...
"Math Puzzles Volume 2" is a sequel book with more great problems. (rated 5/5 stars on 3 reviews) www.amazon.com...
"Math Puzzles Volume 3" is the third in the series. (rated 3.8/5 stars on 4 reviews) www.amazon.com...
"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...
"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...
"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...
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
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.
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
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.
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 (
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
A true combination lock! All real locks are permutation locks
That's great! I added this to the title.
I love you MindYourDecisions!
An actual combination lock, not a real one.
kennkong61, an actual combination lock, and a real combination lock are the same!
not true. there are numeric door locks which are combination and some which are permutation
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
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.
I used Python:
from itertools import combinations_with_replacement as c
print len(list(c(range(10), 4)))
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)
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.
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
Blow the safe.
Now I'm going to 9 bars.
The second method is beautiful.
Should be 10 multichoose 4, which equals 13 choose 4, which is 715?
I guess combinatorics kinda spoils the fun here.
Yup
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
but why is it 13C4 , i thought it was only 10 numbers ?
@@theophiluskoay5905 because you are putting the numbers and the boundaries between the numbers in order.
@@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.
Saw "puzzle", got excited, then saw it depended on being able to do complicated maths.
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.
@@Navajonkee logic puzzles >> maths puzzles
Or you could use the equation:
[(r + n - 1)!] / [r!(n - 1)!]
baileyboy125 exactly! This is the definition of K-combination multisubset
You have taught me so many great lessons, Thanks Presh Talwalker, You're AMAZING
I used: (10+4-1)!/(4!x(10-1)!) = 715
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!
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
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.
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.
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.
The general solution for N digits with length L can also be written as:
(N+L-1)! / (N-1)! L!
We actually learned this formula in school (though it wasn't necessary in the final exam) :D
The "quick elegant" solution was way more complicated and confusing than the first.
If you know stars and bars, it's faster to compute
Too late but I used the second method knowing that it was the combination method with variables are repeated, but I got a free demostration of that precious formula, thank you
I learned this in my Discrete Math class!
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
Did anyone else notice at 4:05 the 4th row of Pascal's triangle (1331) in the possible patterns?
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).
Isn't maths just so beautiful
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
Pascal's triangle pops everytime you talk about stuff like permutations combinations, and ESPECIALLY in binomial theorem.
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.
Nice problem...and timely! Will present to class tomorrow morning
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?
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.
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!
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)
Okaro X Agreed. Also, I think it's kind of more intuitive to place the stars, rather than the stripes.
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.
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!.
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.
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
FethiKara no
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
we learned about dis combo and permutations in algae bra 2
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.
If a*b+a*c+7 is a multiple of 18, prove that a+b+c is a multiple of 6.
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.
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
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.
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.
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.
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?
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.
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.
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?
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
Wow very clever solution. I am amazed!!!
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
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.
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
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
aaab being 0001 means 1000 would be baaa, not abbb.
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).
what 4 digits . sorry for bad understanding of maths
@@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).
because they have a poor grasp of english
I was happy i guessed the answer correctly before the reveal
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?
I like your videos friends. They help a lot of to the mind.
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!
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
My daughter and I came up with this same problem in a different form. If you have a bowl of n different mixed veggies, and a spoon that always scoops k pieces, the answer is:
(n+k-1)! ÷ [(k)! × (n-1)!]
n=10, k=4
13!÷(4! × 9!) = 715
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*
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.
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 :)
How did you use representation theory to solve this? What group are you considering? I assume it was S_4.
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.
Did you combine two conjugacy classes? Because there's 5 ways to partition 4, not 4.
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.
Instead of 9 bars you could also take 4 stars, so 13 over 4 instead of 13 over 9. The result is the same.
The number of patterns is Combination(#digits-1,#repeats).
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.
10! I'm 100% sure. Omg I'm so happy I solved something!!
Fuck. I'm not even close.
Haha
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.
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!
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.
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.
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.
Its a combination with repitition so it should be n+k-1 over k. So 10 + 4 -1 over 4 which gives us 715.
Alright, this is partitions of 4, not too hard, just gotta list em all.
1,1,1,1
2,1,1
2,2
3,1
4
When we have 1 digit to choose from, 10 ways.
2 digits, 90 ways
3 digits, 720 ways
4 digits, 5040 ways (10 choose x)
Add them together: 5040+720+90+90+10=5950.
and I screwed up... used permutation instead of combination, double counting 0011 and 1100... RIP
nice trick bro 👍👍 will surely try this
5:05 method 2 is NOT an alternative method that will get to the answer "more directly and with fewer computation". Method 1 is.
THis is helpful when betting 4-digit lottery BOX bets. It's how you can cover a larger percentage of the winning numbers by paying less. So bet $715 instead of $10,000 for a sure win.
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
you must patent did you figure it out
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?)
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 ?
So if I am right we tried to find how many different codes we can use to find all the possible answer.
I did:
_ _ _ _
Counting from 0 to 9999 ( 9999 ) then let the first digit be 0, so we have 999 numbers ( 0999) then let the 2 first digits be 0 ( 0099 ) now let the 3 first digits be 0 ( 0009 ).
Now let's add the all together:
9999+999+99+9=11.106
and for the last possible code, we have ( 0000 ) so that's 1
11.106+1=11.107
So there are 11.107 different possible codes we can use to a 4 digit code.
am I right? Let me know.
One line in Python:
len([i for i in range(10000,20000) if `i`[1]
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)!).
You are genius! What is your IQ level. Pls tell. Thank you
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.
C(10.4)
combinatorics goes way over my head.
Just did this in Mathematica with a single line:
Length[Union[Map[Sort, IntegerDigits[Range[0, 9999], 10, 4]]]]
In total there should be normally 10 thousand different combinations for it.
1 - 9999 and 0000
so 10,000
However, you can re arange a 4 digit number 24 times in any order. 1,2,3,4.
So out of all 10,000 combinations only 24 will work. so 24 out of 10 i believe.
However, If the code is a 4 digit number where all the digits are the same e.g 7777
7777 still has 24 different combinations of order, even though the sevens in reality dont move.
Same with three sevens e.g 1777, or two sevens e.g 1177. They both have 24 different combinations of order even if they dont actually move.
Im probably wrong but :p
Second solution is quite good
Method 1: From 1:43 to 4:23 (2 minutes and 40 seconds)
Method 2: From 5:13 to 10:59 (5 minutes and 46 seconds, over twice as long as method 1)
Would you really consider this a 'shortcut'? More brain power is needed to logically come up with and understand the procedure for method 2, thus taking more time. This also is the reason as to why this method takes twice as long to explain. Soooo as someone who's brain will probably forget this in less than a day, I'd prefer to use method 1.
Though very rare but I did figure it out because I knew this is a question of combinatorics
Method 1 was far easier for me to understand. But how do you calculate the x-choose-y values?
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
You'd better have some good insurance with a weak lock code like that. LMAO
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.....?
I have never heard of a kind of math that is 13 choose 9 so I was trying to figure out how it works and discovered something odd and likely not a coincidence. In the video you have 13 choose 9 represented as (13/9). First thing I tried was 13 factorial divided by 9 factorial. That equals 17,160. Now if I divide that answer by 24 (13+9), I get the correct answer in the video (715). What’s going on here?
I know this is a year old but you calculated the number of permutations, like if order counted, then you divided by 4! which gave you the combinations for 13 choose 9 (or 13 choose 4). The math for n choose r is n! / (r!(n-r)!)
3:13 didn't you miss one pattern with two unique digits? abab? So there should be 180 different codes with two unique digits.
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
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.....
An interesting challenge is is there a permutation stars and bars formula..
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
Can you tell why it worked?
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.
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)!] ??