practice problems pending

Q1. All of David's telephone numbers have the form 555−abc−defg, where a,b,c,d,e,f,g are distinct digits and in increasing order, and none is either 0 or 1. How many such numbers are possible?
S1.
So we have to choose and arrange 7 digits from 8 digits(2 to 9) in increasing order.
Or we lay them out in a line first and then remove 1 of them at a time.
8 ways to do that.
Answer = 8

Q2.
From the set of integers {1,2,3....2009}, choose k pairs {ai, bi} with ai < bi such that so that no two pairs have a common element. Suppose that all the sums ai + bi are distinct and <= 2009. Find the max possible value of 'k'.
S2.
Let's understand it with a smaller example.
Rather than 2009, let's use 9.
Each pair's sum <= 9 and each sum is distinct.
First instinct:
1+8
2+7
3+6
4+5

The problem is that their sums are not distinct.
They are all 9.

So let's try something else.
If we have to choose 'k' distinct sums each <= 9, what is their max possible sum?
9 + 8 + 7 ... 9- (k-1)
= 9-0 + 9-1 + 9-2 ... 9-(k-1)
= 9k - k.(k-1)/2____[1]

For making 'k' pairs, we need '2k' integers.
What is their least possible sum?
1 + 2 + 3 .... 2k = 2k.(2k+1)/2 = k.(2k+1)___[2]

Using [1] and [2], 
k.(2k+1) <= 9k - k.(k-1)/2
4k^2 + 2k <= 18k - k^2 + k
Divide by 'k' since k > 0
4k + 2 <= 19 - k
=> 5k <= 17
=> k <= 3.4
=> k = 3
So max possible pairs we can make are 3.

Now let's see if we can make 3 such pairs.
1 + 8 = 9
2 + 6 = 8
3 + 4 = 7

So this is one way.
Another way:
1 + 7 = 8
2 + 3 = 5
4 + 5 = 9

The simple logical way to construct these is +2, -1 method.
Increase by 2, decrease by 1.

Since we said we are using first 2k integers, we are using 1,2... 6
Total sum: 1 + 2 ...6 = 21
We want to make 3 distinct sums. To keep them minimum, let's keep them distinct.
Avg sum = 21/3 = 7
So desired sums = 6,7,8
How to get 6, starting with 1:
1 + 5 = 6
+2, -1
3 + 4 = 7
Again.
5 + 3 = 8


Now, let's extend it to 2009 case.
k.(2k+1) <= 2009k - k.(k-1)/2
Divide by k, and multiply by 2.
4k + 2 <= 4018 - k + 1
5k <= 4017
=> k <= 803.4
=> k = 803

Again, since we said we are using first 2k integers, total sum = 
1 + 2 ... 1606 = 1606* 1607/2 = 803 * 1607
We need 803 distinct sums, to keep them tightly packed, let's say we need 803 sums.
Avg = 1607
So the middle sum is 1607.
We start with 1607 - 401 and end at 1607 + 401.
1206 to 2008
1 + 1205 = 1206
3 + 1204 = 1207
....
803 + 804 = 1607

And

2+1606 = 1608

4 + 1605 = 1607

...

802 + 1206= 2008




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 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

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