Brief Summary
This video explores the mathematics behind creating secure passcodes, focusing on whether repeating digits increases or decreases security. It begins with a four-digit passcode scenario, then expands to six-digit passcodes and generalizes the findings. The key takeaway is that repeating a digit in a passcode can increase the number of possible combinations, making it harder to guess, especially for longer passcodes.
- Repeating a digit in a four-digit passcode with three distinct digits increases the number of possibilities compared to using four distinct digits.
- For six-digit passcodes, using five distinct digits (repeating one digit) yields the most possibilities.
- The general case for passcodes of length m using digits from 1 to n involves complex calculations using the inclusion-exclusion principle and can be referenced in the Online Encyclopedia of Integer Sequences (OEIS).
4 digits
A teacher is challenged to guess a student's four-digit smartphone passcode. The teacher observes fingerprint tap prints on four numbers: 1, 6, 9, and 0. Initially, the teacher calculates the number of possible orders for these four digits. There are four options for the first digit, three for the second, two for the third, and one for the last, resulting in 4! (4 factorial), or 24, possible combinations.
The teacher suggests a way to make the passcode harder to guess: use only three different digits, repeating one of them. For instance, if the tap prints are on 1, 6, and 9, one of these digits is repeated. To calculate the possibilities, consider the digit 1 being repeated. There are 4! / 2! = 12 ways to arrange the digits if 1 is repeated. Since any of the three digits could be repeated, the total number of possibilities becomes 12 * 3 = 36. Thus, repeating a digit increases the number of possible passcodes from 24 to 36, making it more secure against guessing based on tap prints.
6 digits
The video extends the passcode problem to six-digit passcodes. If six different digits are used, there are 6! (6 factorial) or 720 possible combinations. However, if only five different digits are used, with one digit repeated, the number of possibilities changes.
Assuming the digit 1 is repeated, there are 6! / 2! = 360 ways to arrange the digits. Since any of the five digits could be the one that's repeated, the total number of possibilities is 360 * 5 = 1800. This shows that repeating a digit significantly increases the number of possible six-digit passcodes, making it more secure than using six distinct digits. The video then generalizes this result for n-digit passcodes, providing a formula to compare the number of possibilities when using n distinct digits versus n-1 distinct digits with one repeated.
general case
The video explores the general case for creating passcodes of length m using digits from 1 to n, where m is greater than or equal to n. The total number of sequences of length m using n digits, allowing repetition, is n^ m. To find the number of passcodes where each digit is used at least once, the video introduces a clever trick using the inclusion-exclusion principle.
By defining ai as the number of sequences missing digit i, an explicit formula can be derived to calculate the number of sequences where all digits appear at least once. This allows determining the value of n that yields the most valid sequences for a given passcode length m. The video references the Online Encyclopedia of Integer Sequences (OEIS), noting that a sequence exists that corresponds exactly to this problem. For example, for a seven-digit passcode (m = 7), using five different digits maximizes the number of possibilities.
