Pigeonhole Principle (3)

Question

Let $a_1,a_2,a_3,....a_{100}$ and $b_1,b_2,b_3,....b_{100}$  be any two permutations of the integers from $1$ to $100$.

$a_1b_1,a_2b_2,a_3b_3,....,a_{100}b_{100}$

Prove that among the $100$ products given above there are two products whose difference is divisible by $100$.

Comments

It is not given that P1 and P2 has to different permutations they can be same.

---

with n numbers ,n! permutations are possible.. so, P1 and P2 can't be same..

---

Ok I got your point the two prmutations are different

May be your claim (in the previous comment) is true.

But showing it with examples does not prove your claim.

You have to prove that in general.

Answer 1

If among the products a₁b₁,a₂b₂,..........,a₁₀₀b₁₀₀ if we get two products a_ib_i and a_jb_j such that the difference in between them is divisible by 100 then the remainders after dividing a_ib_i and a_jb_j with 100 would be same.

Now, consider the numbers {0,1,2,......,99} as holes and the pigeons be the products {a₁b₁,a₂b₂,....,a₁₀₀b₁₀₀}

Now, we are putting the product a_ib_i in the hole r if it leaves the remainder r when divided by 100.

If we get that a hole contains more than one product then we are done.

Assume that all the 100 holes contain one product (a_ib_i ) each. 

Then there should be a product in hole 2 . Let the product be a_kb_k.

Hence a_kb_k = 100 q + 2. = (4 * 25) q + 2 = 4p + 2.

So, a_kb_k leaves remainder 2 when divided by 4.

Now, since the holes contain one product each there are 50 products in the odd numbered holes.

Let the products in the odd numbered holes be a_lb_l . Then a_lb_l leaves odd remainder when divided by 100.

So, a_lb_l is an odd number and odd number is formed only when both a_l and b_l are odd numbers.

Now, since a_lb_l is an odd number the remainder when divided by 4 can be either 1 or 3.

Now, the rest 50 products a_hb_h (say) are even and both a_h and b_h are even. So, the products a_hb_h are divisible by 4.

So, among the 100 products we are not getting any product which leaves remainder 2 when divided by 4.

But we know that a_kb_k leaves remainder 2 when divided by 4. Hence contradiction.

So, the holes cannot contain 1 product each. So, there must be more than one products in at least one hole.

So, among the given products there must exists two products such that the difference between any two is divisible by 100.