# Combinatorics - The pigeonhole principle

• MHB
• Yankel
In summary: All differences (between two numbers with different remainders) are not divided by 11, but a number between 1 and 99 (the difference of two numbers with equal remainders) is a multiple of 11 iff it has two identical digits.
Yankel
Hello,

I am trying to solve a problem related to natural numbers. The solution is based on the pigeonhole principle, however I can't see the connection.

The is the problem:

Choose 12 two digit numbers. Divide each by 11 and write down the residue (i.e. do the modulu operation). Group the residues in different sets, in such a way that all numbers with the same residue are in the same set.
Can you find two numbers that when subtracted from one another (bigger - smaller) gives a two digit number with identical digits ? (e.g. 57-24=33).

Now choose a new set of 12 numbers. Can you find such numbers now ?

Are you findings random or is there a reason ? Try to write down a rule and to prove it.

---------------------------------------------------------------------------------------------------------------------------

So I have chosen 12 numbers and did all the residues. I have noticed that two numbers in the same set, i.e. two numbers having the same residue will give a subtraction which is a number with identical digits.

What I don't see, is what's the connection to the pigeonhole principle, what is the rule I am suppose to find and how to prove it using the pigeonhole principle.

P.S.

My chosen example was:

{33} {12} {24, 57} {25} {81} {17,39} {73,95} {41} {64}

I think I figured something here, not the whole story yet.

Two numbers will give the same residue will be in the same set. Numbers from the same set will give a two digit number with the same digit when subtracted.

If I divide by 11, then I have 11 different residues (0-10). When picking 12 numbers, I guarantee that at least one set will have two numbers in it, and then according to the pigeonhole principle, I will have two numbers giving the required result when subtracted.

The only thing missing here, is why two numbers in the same set give a number with identical digits when subtracted ? Is there a way to know which number it will be (e.g., 22, 33, ...) ?

Can I say that I will ALWAYS get two numbers that will give number with identical digits when subtracted ? No matter which 12 numbers I choose ?

A new discovery...all differences I got are divided by 11 with no residue...

Last edited:
A number between 1 and 99 (the difference of two numbers with equal remainders) is a multiple of 11 iff it has two identical digits.

## 1. What is the pigeonhole principle in combinatorics?

The pigeonhole principle states that if there are more objects than there are containers to put them in, at least one container must have more than one object. In combinatorics, this principle is often used to prove the existence of certain patterns or arrangements.

## 2. How is the pigeonhole principle used in combinatorics?

In combinatorics, the pigeonhole principle is used to prove the existence of certain combinations or arrangements. It can also be used to show that a problem has no solution, by demonstrating that there are not enough containers (or "pigeonholes") to hold all the objects.

## 3. What are some real-world applications of the pigeonhole principle?

The pigeonhole principle has applications in various fields such as computer science, statistics, and cryptography. In computer science, it is used in data compression and hashing algorithms. In statistics, it is used in the birthday paradox, which states that in a group of 23 people, there is a 50% chance that two of them share the same birthday. In cryptography, it is used to analyze the security of certain encryption schemes.

## 4. Can the pigeonhole principle be used to solve all combinatorial problems?

No, the pigeonhole principle is a useful tool in combinatorics, but it cannot be used to solve all problems. It is most effective when there is a clear imbalance between the number of objects and the number of containers or when there is a pattern that can be exploited.

## 5. Are there any limitations to the pigeonhole principle?

Yes, the pigeonhole principle has some limitations. It only applies to finite sets (since infinite sets cannot be put into containers) and it does not provide a specific solution or method for solving a problem. It also assumes that all objects and containers are distinct and that each object can only be placed in one container.

Replies
2
Views
1K
Replies
1
Views
2K
Replies
5
Views
1K
Replies
8
Views
1K
Replies
7
Views
1K
Replies
2
Views
2K
Replies
20
Views
4K
Replies
2
Views
2K
Replies
15
Views
1K
Replies
1
Views
2K