practice problems pending

Q1. "In a room of n people (where n >= 2), prove that there are always at least two people who have shaken hands with the exact same number of people."

Q2. "In a tournament with n players (where n >=2 ), prove that at any given moment during the tournament, there are always at least two players who have completed the exact same number of games."

Q3. Twenty pairwise distinct positive integers are all < 70. Prove that among their pairwise differences there are four equal numbers.


Q4. Fifty-one small insects are placed inside a square of side 1. Prove that at any moment there are at least three insects which can be covered by a single disk of radius 1/7.

Solution1:
Possible number of handshakes: 0,1,2 ... n-1
But 0 and n-1 are not possible together, one of them has to be removed.
So now there are n people and (n-1) possible values.
By pigeonhole principle, at least 2 people need to have same number of handshakes.

Solution 2:
Same as above.

Solution 3:
1,2...68 are possible diffs.
20C2 = 190 pairs.
So many buckets with 3 values. But 4? How?

Let's look at a different approach.
Let's say a1,a2...a20 are the picked numbers in ascending order.
(a2-a1) + (a3-a2)... + (a20-a19) = a20 - a1
Max(a20-a1) = 68

Now, to do a proof by contradiction, let's assume that no more than 3 diffs are same.
To minimize the differences:
3*1 + 3*2 .. 3*6 + 7 <= 68
But LHS = 70 hence contradiction.
So we need at least 4 diffs to be same.

Solution 4:

First thought: What if the insects are small enough to fit in the gaps left after packing as many disks as possible inside the square?
Counter: Problem doesn't say that first you pack the disks and then settle the insects. It's the reverse. First the insects are settled in any way they want and then we have to show that at least 3 of them can be covered by a single disk. In fact if we pack them like this very tightly, a single disk placed overhead can easily cover them all!

So:
Let's divide the square into 25 smaller ones each with side = 1/5.
Now at least one of those squares will have at least 3 insects since 51/25 > 2 and using pigeonhole.
To cover that square fully the diameter of the disk should be more than the diagonal of the square.
2/7 > sqrt(2)/5 => 10 > 7.sqrt(2) => 100 > 98 which is true.
H.P.

Further, why did we choose 25 smaller squares? Why not 16 or 36?
If we choose 36, then pigeonhole will fail and we can't force 3 insects into one square.
If we choose 16, the pigeonhole will pass but the disk diameter won't be enough to cover the sqaure.
So 25 is the sweet spot.

Comments

Post a Comment

Popular posts from this blog

IOQM 2024 Paper solutions (Done 1-21, 29)

Image
Q1 (number-theory). The smallest positive integer that does not divide 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 is: Solution : This product has all the integers from 1 to 9. So smallest integer not dividing it would be the next prime after 9. Which is 11. Answer: 11 Q2 (combinatorics): The number of four-digit odd numbers having digits 1, 2, 3, 4, each occurring exactly once, is: Solution: Last digit has to be 1 or 3: 2C1 Choosing remaining 3 digits: 3C3 Arranging those 3 digits: 3! Answer: 2C1*3C3*3! = 12 Q3 (number-theory): The number obtained by taking the last two digits of \(5^{2024}\) in the same order is: Solution: To get last 2 digits from number, divide by 100 and take the remainder. So we have to compute mod 100. 25 mod 100 = 25 25.5 mod 100 = 125 mod 100 = 25 5^3.5 mod 100 = 25.5 mod 100 = 25 5^4.5 mod 100 = 25.5 mod 100 = 25 ..... So: 5^2024 mod 100 = 25. Q4 (geometry): Let ABCD be a quadrilateral with \(\angle ADC = 70^\circ\), \(\angle ACD = 70^\circ\), \(\angle ACB = 10^\circ\...
Read more

IOQM 2023 solutions

Image
Q1. Let n be a positive integer such that 1 ≤ n ≤ 1000 . Let M n be the number of integers in the set X n = { 4 n + 1 , 4 n + 2 , … , 4 n + 1000 } . Let a = max ⁡ { M n : 1 ≤ n ≤ 1000 } , and b = min ⁡ { M n : 1 ≤ n ≤ 1000 } . a = \max\{M_n : 1 \leq n \leq 1000\}, \quad \text{and} \quad b = \min\{M_n : 1 \leq n \leq 1000\}. Find a − b a - b . Solution: Quick tip: If n^2 = k then (n+1)^2 = k + (2n + 1) We will use this here. Also as the numbers grow larger the gap between 2 perfect squares becomes less and less. For. e.g. there are 10 perfect squares between 1 and 100 but only 4 perfect squares between 101 and 200. So X1 = {sqrt(5) ... sqrt(1004)} will have the most number of perfect squares. While X1000 = {sqrt(4001)...sqrt(5000)} will have the least. In X1 the first integer square root is 3 and we know that 1024 is the square of 32 so the last integer will be 31. Total: 31 - 3 + 1 = 29 integers in X1. In X1000, We know that 64^2 = 4096 so 64 is the first integer. 70^2 = 4900 and ...
Read more

Simon's factoring trick(complete the rectangle)

  "Complete the Rectangle" , also called Simon’s Favorite Factoring Trick , is a clever algebraic method for factoring expressions of the form: x y + a x + b y + c xy + ax + by + c Or more commonly, you'll see it used in a simpler form: x y + a x + b y + d xy + ax + by + d But especially when we’re given something like: x y + a x + b y + a b xy + ax + by + ab It becomes very easy to factor. Let me walk you through it step-by-step. 💡 The Key Idea We add and subtract a constant to turn the expression into a perfect rectangle (a.k.a. a factorable quadratic or product of binomials). The “complete the rectangle” version of this trick usually works best on expressions like: x y + a x + b y + a b xy + ax + by + ab We treat it like this: x y + a x + b y + a b = ( x + b ) ( y + a ) xy + ax + by + ab = (x + b)(y + a) ✅ Step-by-Step Example Factor: x y + 3 x + 2 y + 6 xy + 3x + 2y + 6 Step 1: Rearrange the terms: Group like this: x y + 3 x + 2 y + 6 xy + 3x + ...
Read more