practice problems pending

 Problem 1. Let (a) be a positive real number. Prove that one of the positive real numbers

[
a,;2a,;3a,...;(n-1)a
]
is at most (1/n) distant from a positive integer.

S1.
Let's test for n = 2
The list is simply: 'a'.
And any real positive number is at most 1/2 away from a positive integer.
So it works for n = 2.

Let 1 <= k <= n-1.
We want to show that at least one k.a is at most 1/n away from a positive integer.
Let {k.a} be the fractional part of k.a.
Distance of {k.a} from a positive integer is min( {ka}, 1 - {ka}).
To understand, see the number line:

0______{ka}_______1
Its distance from 0 is {ka} and 1 - {ka} from 1.

Let's prove by contradiction.
Let's say for each 'k', 1 <= k <= n-1, {k.a}is more than 1/n away from the nearest integer.

Like this:
0___1/n___{ka}___1 - 1/n____1

So {ka} is always between 1/n and (n-1)/n.
Distance between 1/n and (n-1)/n is (n-2)/n.
So there are (n-2) gaps each of length 1/n.

Using pigeonhole argument, fractional parts of  a, 2a ... (n-1)a, once fitted into these gaps would result in at least 2 of them in the same gap.
Let those 2 be i.a and j.a where i < j.

So {ia} and {ja} are in the same gap.
=> | {ia} - {ja} | < 1/n

Now, let's consider ja - ia where 1 <= i < j <= n-1
k = j-i will also be between 1 and n-1
So k.a. will belong to our original sequence.

k.a = [ja] + {ja} - [ia] - {ia}
= ([ja] - [ia]) + ({ja} - {ia})
Let [ja] - [ia] be an integer 'm'.

ka - m = {ja} - {ia}
=>
|ka - m| < 1/n
=> distance of ka from an integer m is less than 1/n which is contradiction to what we assumed.
So original assumption was false.
H.P.

Problem 2. Let (n) be a positive integer not divisible by (2) or (5). Prove that there exists a multiple of (n) consisting only of the digit (1).
S2.
1
11
....
11111...11 ('n' digits)

Divide all of them by 'n'. Possible remainders are 0 .... n-1.
If you get remainder 0, you are done.
Else at least 2 of them share the same remainder.
1111(j times) - 1111(k times) = 0 mod n.
= 1111(j-k times) followed by 0000 = 0 mod n
Since n is not divisible by 2 or 5, for it to divide LHS it has to divide 1111(j-k times) H.P.



Comments

Post a Comment

Popular posts from this blog

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

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