- Mistakes in Physics
- Parasites – Natural Born Manipulators: 5 Ways To Drive You Crazy
- The Invention Handheld Clouds of Cotton Candy
- NASA X-planes
- Bionics: How People Imitate Nature
- An Aztec And A Box Of Chocolates
- Traces of the Ancient Seas
- Everyday Combinatorics
- The Lava Lamp
- The biggest waves on the Planet
- Paraglide: Fly Like a Bird
- Caves: Dungeons & Caverns
- Scientific Astrology
- How Has Coronavirus Changed The World ?
Topic Last Updated on 15-07-2024
The Two Rules of Combinatorics
Let’s start with the good news: in combinatorics, there are only two rules that you need to know. If you master these, then you will understand the whole of combinatorics, which will greatly simplify your life. How exactly? We will demonstrate this later on. The bad news is that understanding these rules is not that easy.
Combinatorics | THE RULE OF SUM
The number of possible ways to select 1 object from 2 sets is equal to the total number of objects in these sets.
Consider an example. If there are 6 girls and 4 boys in a class, then there are 6 + 4 = 10 ways to choose 1 student. What if we were talking about tables or chairs instead of boys and girls? It’s simple enough — the same operations would apply. But it is necessary to select a pair of objects, instead of just a single object: an object from each set (in this case, there are 2). In that case, the following rule can be applied.
THE RULE OF PRODUCT
The number of ways to choose a pair of objects from 2 sets (the first object from the first set, the second object from the second) is equal to the product of the number of objects in these sets.
Again, let’s look at an example. Say you have 4 pens and 5 pencils. How many different pairs from these sets can you assemble? For the first pen there are 5 possibilities, for the second — also 5, for the third and the fourth — 5 again. In total, there are 4 × 5 = 20 possibilities.
This rule can work not only for 2 sets. If you also have 3 felt-tip pens, you can assemble the kit of felt-tip pens, pens and pencils in 3 × 4 × 5 = 60 ways. This can be proven in the same way: for each of the 20 ways of choosing a pen-pencil pair, there are 3 ways of choosing a felt-tip pen. And you already know how to proceed from there.
How do we go about distinguishing these rules from each other? Let’s say that, 2 teams of 5 people played in a Dota 2 tournament final, and you need to select a Most Valuable Player among the finalists. How many ways are there of doing this? The correct answer is 10. The sum rule can be used here since we select 1 element from 2 sets. What if we need to select 1 player from each team and reward them as the best in their respective teams, how many ways are there of choosing this pair? The answer is 25. Here, we applied the product rule — after all, you need to choose not just 1 element, but a pair! Figured it out? Then we can move on to examples from real life.
The Magic of Zeros and Ones
Information in a computer is stored in binary code, written in zeros and ones. A single memory cell, also a bit, contains either a 0 or 1. The question is: how many bits would we need to encode, for example, the 26-letter Latin alphabet? It is assumed that each letter is encoded with the same number of bits, and this number must be minimal so that the letters take up less memory space.
Don’t be alarmed if you don’t see a solution right away. In such cases, take the problem step by step by sorting out the simplest answers. What if there’s only one bit? It can be written as either 0 or 1. That is, there are only 2 ways or rather just 2 letters — not enough.
Suppose there are 2 bits or 2 cells. How many different 2-digit numbers can be made up of zeros and ones? Each cell can be represented as a set in which there is either 0 or 1. Then, our task is to select 2 elements from 2 sets. This is the product rule. We end up with 4 ways — again, too few.
In a similar way, taking 3 bits, we have 3 cells to fill. According to the same rule of product, we will have 2 x 2 x 2 = 8 different ways to produce a combination of zeros and ones.
Accordingly, 4 bits will give 2 x 2 x 2 x 2 = 16 ways, and 5 bits — 32 ways. This works for us since 32 is greater than 26. Therefore, at least 5 bits are required to encode the Latin alphabet. And we have arrived at the answer with the rule of product.
Unique Numbers for All
On August 14, 1893, France became the first country in the world to introduce a registration plate for vehicles. Later, almost all countries would follow their example. A registration number is a unique combination of letters and numbers; it is needed to uniquely identify the owner and their vehicle. Over nearly one and a half centuries, the number of cars in the world has come to exceed 1 billion units, and each one requires its own unique number. How has this problem been addressed?
Consider a plate number of 3 numbers and 3 letters — this format is used in countries such as Canada, Botswana, Sweden, Kazakhstan, and Russia. Here, we are not taking into account the regional code, which will be discussed separately.
Combinatorics | Cracking the Code
First of all, we can only use Latin characters for the letters. Accordingly, there are 10 possibilities for each digit and 26 possibilities for each letter. How many unique numbers can we come up with? We must select 1 combination of 3 sets of 10 digits and 3 sets of 26 letters. That is, we must apply the product rule:
10 × 10 × 10 × 26 × 26 × 26 = 17 576 000
Is that a lot or too little? For example, 35 million people live in Canada, or an average of about 2.7 million people in 13 provinces. Even if every resident, including children, has a car, everyone will be able to get a unique number.
In fact, 38% of the population, or more than 13 million people, live in Ontario. As you can see, this number of unique numbers would be sufficient for this province. But in 1997, the province decided to switch to a 4-letter and 3-digit format, thereby expanding the range of possible registration numbers. The population is similarly distributed in Russia — Moscow and Moscow Oblast are the most densely populated. As we said earlier, a regional code is assigned to a 3-digit number, and there may be several such codes for densely populated regions.
You can even calculate how many digits there should be in a telephone number in your city so that there are enough numbers for everyone! The product rule can be used in this case.
Combinatorics | Password Strength
Every modern mobile phone has password protection, the simplest form of which is the 4-digit pin code. Knowing the product rule, you can calculate how many different possibilities a hacker would need to sort through to figure out a password:
10 × 10 × 10 × 10 = 10 000
Would you consider this an impressive amount? Today, many phones have built-in protection against hacking — after several unsuccessful attempts to enter a password, your device will be blocked.
But if you think that a 4-digit pin is adequate, we have bad news for you. The British information security company MDSec released a device that can figure out any 4-digit password in a maximum of 111 hours. The trick is that the device enters a password and then waits for 40 seconds — this way, it bypasses the protection system. As a result, it can crack the device in 4.6 days of continuous operation.
How would this situation differ if letters were used in a password? First, apply the sum rule to determine how many ways there are of choosing 1 element from 2 sets:
10 numbers + 26 letters = 36 ways
Now, apply the product rule to determine the number of ways of choosing a password from 4 sets of 36 elements:
36 × 36 × 36 × 36 = 1 679 616 ways
It will take:
40 × 1 679 616 = 67 184 640 seconds, or 777 days
As an independent task, try to count the number of passwords that meet modern security standards:
At least 8 characters in password length
One uppercase letter (A–Z)
At least one lowercase letter (a–z)
One number (0–9)
At least one special character
(~`!@#$%^&*()+=_-{}[]\|:;”’?/<>,.)
And most importantly: in boosting your password protection, don’t forget the password itself!
WHAT DO THE COLORS ON A FLAG MEAN?
