practice problems pending

Q1. How many distinguishable arrangements are there of 1 brown tile, 1 purple tile, 2 green tiles, and 3 yellow tiles in a row from left to right? (Tiles of the same color are indistinguishable.) 
S1.
7!/3!2!

Q2. Seven 6-sided dice are rolled. The probability that the sum of the numbers on the top faces is 10 can be written as n/6^7 where n is a positive integer. What is n?
S2.
x1+x2..x7 = 10
Each of them is minimum 1.
For stars and bars:
x1+x2...x7 = 3
9C6 ways out of 6^7 ways.
84/6^7
n = 84

Q3. Suzanne went to the bank and withdrew 800 dollars. The teller gave her this amount using 20 dollars bills, 50 dollars bills, and 100 dollars bills, with at least one of each denomination. How many different collections of bills could Suzanne have received?
S3.
20x + 50y + 100z = 800
2x + 5y + 10z = 80
5y will be even, y = 2k
2x + 10k + 10z = 80
x + 5k + 5z = 40
x = 5(8 - k - z)

x >= 1 => 8-k-z > 0 => k+z <8 => k+z <= 7

For k+z <= 7 with k>=1 and z>=1 how many solutions:
k = 1 => z = 1...6
k = 2 => z = 1..5
...
k = 6 => z = 1
Total 1 + 2 ...6  = 21
Answer: 21

Q4. For some particular value of N,  when (a+b+c+d+1)^N is expanded and like terms are combined, the resulting expression contains exactly 1001 terms that include all four variables a,b,c,d, each to some positive power. What is N?
S4.
x+y+z+w = at least 4 and at max N.
X+Y+Z+W = 0 to N-4
(N-4+4-1)C(4-1) = (N-1)C(3)
(N-2)C3
....
3C3

So 3C3 + 4C3 ... (N-1)C3 = (N)C4
This is hockey stick identity.
Proof:
nCk + nC(k+1) = (n+1)C(k+1) why? If I want to pick k+1 people from n+1 then a person A will or will not be there. Add those 2 to get this identity.

Now:
3C3 = 4C4
4C4 + 4C3 = 5C4
5C4 + 5C3 = 6C4
....
= NC4

NC4 = 1001
=> 
n.(n-1).(n-2).(n-3) = 1001.24 = 7.11.13.24
So RHS has to be product of 4 consecutive integers.
11.12.13.14
N = 14 = answer.

Q5. Each of 2023 balls is randomly placed into one of 3 bins. What is the probability that each of the bins will contain an odd number of balls?
S5.

Case 1:
Distinct balls distinct bins: PIE
Total: 3^2023

Now since sum of balls in 3 bins is odd(2023), here are the possible ways to get that:
OOO, OEE, EOE, EEO
By symmetry last 3 are same.
So x + 3y = 3^2023

Let's try to get a relation between x and y.
Consider
OOO and OEE
So Bin A has odd elements in both arrangements.
Bin B,C both have either odd or both are even.
B+C is always even.
Number of ways to split B+C into 2 groups such that each has even balls is same as such that each has odd balls.
How?
Let's paint one of the balls red. If 2 groups are even, move the red ball from the group having to the group not having it. Now both are odd numbered. And vice versa. So bijection.
So splitting even balls into OO and EE has equal ways.
But OEE is one more than OOO. Why?
That extra arrangement comes from the case where all 2023 balls go into Bin A. Now you can't make odd pair from 0,0.
So y = x + 1
x + 3x + 3 = 3^2023
4x = 3^2023 - 3
x = 1/4[3^2023 - 3]
Probability = 1/4[1 - 3/3^2023] = 1/4[1 - 1/3^2022] = Answer


Case 2:
Identical balls distinct bins => stars and bars.
Total: (2023 + 3 - 1)C(3-1) = 2025C2
Each bin odd => 
2x + 1 + 2y + 1 + 2z + 1 = 2023
x + y + z = 1010
1012 C 2

Answer:
1012.1011/2025.2024 = 1011/4050

-----------------------------------
Q2. Consider a string of  n 1's. We wish to place some + signs in between so that the sum is 1000. For instance, if n=190, one may put + signs so as to get 11 ninety times and 1 ten times, and get the sum 1000. If a is the number of positive integers n for which it is possible to place + signs so as to get the sum 1000 find the sum of the digits of a.
S2.
1111 > 1000
So at max one block can have 3 1s.
x.111 + y.11 + z.1 = 1000
And the original 'n':
n = 3.x + 2.y + z
z = n - 3x - 2y

1000 - 111x - 11y = n - 3x - 2y
n = 1000 - 108x - 9y = 1000 - 9(12x + y)

Now how many unique values of 'n' are there is equal to how many unique 't' values are there where
t = 12x + y
1000 > 9(12x+y) => 12x + y < 1000/9 => 12x + y <= 111
So with 12x + y you can make any integer from 0 to 111 by keeping x = 0 and y = 0 to 111.

But we have to also consider:
111x + 11y <= 1000
y <= (1000 - 111x)/11
1000 = 11.90 + 10
111x = 11.10x + x
1000 - 111x = 11.(90-10x) + 10 - x

y <= 90 - 10x + (10-x)/11
=> y <= 90 - 10x since max value of x is 9

For x = 0  to 9 
0 <= y <= 90 - 10x

t = 12x + y => 12x <= t <= 12x + 90 - 10x
=>
12x <= t <= 90 + 2x
x = 0 => t = 0 to 90
x = 1 => t = 12 to 92
x = 3 => t = 36 to 96 
...
x = 8 => t = 96 to 106
x = 9 => t = 108 to 108

So t ranges from 0 to 106 and then 108
total values: 108
sum of digits = 9


Q3.



For a positive integer n, consider non-negative integer-valued functions f on {1,2,…,n} satisfying 

f(i) ≥ f(j) for i > j and

(i = 1 to n) Sigma (i + f(i)) = 2023.

Choose 'n' such that Sigma(f(i)) part in the above is the least. How many such functions exist in that case?

S3.

(i = 1 to n) Sigma (i + f(i)) = 2023 = n(n+1)/2 + S where S =  Sigma(f(i)) which has to be minimized.
For S to be minimum n(n+1)/2 has to be max.
for it to be close to 2023, n(n+1) is close to 4046.
So n^2 is close to 4046 which is around 4096 or 2^12. So let's test 63.64 which is 4032 and hence n = 63.
So 4032/2 + S = 2023 => S = 2023 - 2016 = 7

0 <= f(1) <= f(2) ... f(63) <= 7 And f(1) + f(2) .. f(63) = 7

=> There will be 0s for the early values and sum of 7 at the end.
So distinct fs can be counted by distinct partitions of 7. Order won't matter of partitions since they have to be in increasing order.
7 [1]
6+1 [1]
5 + 2, 5 + 1 + 1 [2]
4 + 3, 4,2,1 4,1,1,1 [3]
3,3,1 3,2,2 3,2,1,1 3,1,1,1,1[2]
2,2,2,1 2,2,1,1,1 2,1,1,1,1,1[3]
1,1,1,1,1,1,1[1]

Total 15 such partitions hence 15 such functions.

Q4.
Find the number of triples  (a,b,c) of positive integers such that: ab is a prime; bc is a product of two primes; abc is not divisible by the square of any prime; and abc≤30..
S4.
a = 1, b = 2, c = 3,5,7,11,13 = [5]
a = 1, b = 3, c = 2,5,7 = [3]
a = 1, b = 5, c = 2,3 = [2]
a = 1, b = 7, c = 2,3 = [2]
a = 1, b = 11,13 c = 2 [2]
Total: 14

Now, b = 1
a = 2, c = 3.5
a = 3, c = 2.5
a = 5, c = 2.3
Total: 3
Answer: 17

Q5.
Let N be the number of ways of distributing 52 identical balls into 4 distinguishable boxes such that no box is empty and the difference between the number of balls in any two of the boxes is not a multiple of 6. If N=100a+b, where a,b are positive integers less than 100, find a + b.
S5.
p + q + r + s = 52 = 4 mod 6
Each of p,q,r,s should be different mod 6.

We have to choose 4 from (0,1,2,3,4,5) and add them s.t. they leave 4 mod 6.
Alternatively.
0+1+2+3+4+5 = 15
15-x1-x2 = 4 mod 6 => 11 = x1+x2 = 5 mod 6

0,5
1,4
2,3

are such pairs to be omitted.
=> the remaining remainders will add up to 10.

Let those remainders br r1,r2,r3,r4.
4! ways to assign them.

Now, p = 6q1 + r1, q = 6q2 + r2 ...
Adding:
6(q1+q2+q3+q4) + (r1+r2+r3+r4) = 52
6(q1+q2+q3+q4) = 42
=> q1+q2+q3+q4 = 7

So how to distribute 7 groups of 6 balls among 4 boxes such that none is empty.

Case 1:
Remainders are 1,2,3,4
So no box will be empty.
Stars and bars gives 10C3 = 120

Case 2:
Remainders are 0,5,2,3 or 0,5,1,4
Count 1 of them and double that.
So one group of 7 will have to go to the box with remainder 0.
6 left. Stars and bars: 9C3 = 84
84*2 = 168

Total: 24*(168 + 120) = 24*288 = 6912 = 100a + b => a = 69, b = 12 => a+b = 81










































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