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 distinct 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:
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.
This gives an idea that probability might be close to 1/4.
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.
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.
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 out 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
6,1,1 8C6.2C1/2! (invalid)
5,2,1 8C5.3C2
4,3,1 8C4.4C3
4,2,2 8C4.4C2/2!(invalid)
3,3,2 8C3.5C3/2!(invalid)
Add all valid and multiply by 3!
N = 2688
sum of digits = 24 = answer
Q11.
S11.
Since 2x1 tile can be laid horizontally or vertically, make the grid 7x2.
Note that if I lay a tile vertically, it won't come alone, it will come with another one, like this:
VV
VV
Horizontal tile can come alone
HH
So a vertical tile pair is as good as 2x2 tile here in terms of constraints.
Let's start with 3 pairs of vertical tiles:
------>
VV
VV
----->
VV
VV
------>
VV
VV
We also allowed to use at max one 2x2 tile so that gives us 3 more variations.
Now we can only place one HH pair.
And there are 4 gaps to do that as shown.
So total: 4*4 = 16 ways.
With 2 Vertical pairs:
------>
VV
VV
----->
VV
VV
------>
If we use 2x2, we get 2 more cases.
Now there are 3 gaps and we can put 3 HH rows still.
Stars and bars gives: 5C3.
Total: 10*3 = 30
With 1 VV pair:
------>
VV
VV
----->
One more case using 2x2.
2 gaps, 5 HH rows.
Stars and bars gives: 6C5 = 6
Total: 6*2 = 12
0 VV pair:
Only 1, all rows HH
Total: 12 + 30 + 16 + 1 = 59
Q12. In a certain country, the currency notes come in denominations of 1,2,4,8,16,… (the powers of 2) Bens. The rules stipulate that one cannot use more than two notes of any one denomination in a transaction. Find the number of ways in which one can give change for 100, following this rule.
S12.
Let's do it using recursion.
Every currency note can be used 0,1,2 times.
If we have to make up an odd number, we have to use a 1. We can't use 2 1s, since then it will become even. And we can't use 3, not allowed.
So,
for n = 2k + 1 we have to use exactly one 1 note.
For the remaining 2k we have to use all even numbers 2,4,8.. etc.
Number of ways to do that are same as making 'k' with 1,2,4 etc.
So f(2k+1) = f(k)
For n = even = 2k:
We can use 0 or 2 1s.
For 0 1s, again we have f(k) ways to build using even numbers.
For 2 1s, we have f((2k-2)/2) = f(k-1) ways to build using even numbers.
f(2k) = f(k) + f(k-1)
So
f(100) = f(50) + f(49)
Build a tree and build up:
Answer = 19.
Comments
Post a Comment