week 1 practice problems
Day 1:
Q1.
The repeating decimals
x = 0.ababab...
and
y = 0.abcabc....
satisfy
x + y = 33/37
Find the 3 digit number abc.
S1.
(10a+b)(1/100 + 1/10000...) = (10a+b)/100[1/1-1/100] = (10a + b)/99
(100a + 10b +c)(1/1000 + 1/1000,000....) = (100a+10b+c)/999
(10a + b)/99 + (100a+10b+c)/999 = 33/37
=> 999(10a+b) + (100a+10b+c).99 = 33.99.999/37 = 27.33.99
=> 111(10a+b) + (100a+10b+c).11 = 99^2 = 9801
=> 2210a + 221b + 11c = 9801______[1]
=> a <= 4
2210*4 = 8840 => 221b + 11c = 961
b = 4 => 11c = 961 - 884 = 77 => c = 7
abc = 447
Also in [1] if we take mod 11 then:
2210a + 221b = 0 mod 11
221(-a +b) = 0 mod 11
=> a = b mod 11
Since a,b are single digit => a = b
221a.11 + 11c = 9801
=> 221a + c = 891
a = 4 => c = 7
Q2. Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs.
S2.
Let's do step by step.
Subset size: 3 => There are 10 ways.
Total: 10
Size: 4 =>
10 ways to pick 4 adjacent.
For 3 adjacent and 1 separate: First pick 3 adjacent (10 ways) and then choose 1 from remaining 5(5) = 10*5 = 50
Total: 10 + 10 + 50 = 70
Size: 5 =>
10 ways to pick 5 adjacent.
4 adjacent and 1 separate: 10* (remaining 4) = 40
3 adjacent and 2 not touching: 10*5C2 = 10*10 = 100
Total: 70 + 10 + 40 + 100 = 220
Size: 6 =>
10 ways for 6 adjacent.
5 adjacent and 1 separate = 10*3 = 30
4 adjacent and 2 not touching = 10*4C2 = 60
3 adjacent and 3 not touching =
10 ways to pick 3 adjacent.
Let's say we pick 1,2,3. Now 4,10 are gone.
So we need to pick remaining 3 from 5,6,7,8,9.
5C3 = 10 ways to do this.
So total: 10*10 = 100.
But when we pick any 3 from 5,6,7,8,9 we will also pick 5,6,7 and 6,7,8 and 7,8,9.
So there will be 10*3 such instances when the 2 blocks of 3 are adjacent.
And we have double counted them.
So subtract 15 to get 85.
Total: 220 + 10 + 30 + 60 + 85 = 405
Size > 6 (7,8,9,10):
Now each subset of these size will have at least 3 adjacent.
Why:
Let's try to do otherwise and pick 7:
1 _ 3 _ 5 _ 7 _ 9 _
We have picked 5 but still left with 2 to pick and any we pick now will make 3 adjacent.
So add 10C7 + 10C8 + 10C9 + 10C10 to final count.
That is: 120 + 45 + 10 + 1 = 176
405 + 176 = 581
Day 2:
Q1) What is the three digit number that is equal to 4 times the product of its digits?
S1.
None of the digits can be 0.
c has to be 2,4,6,8
100a + 10b + c = 4abc
=> a = (10b + c)/(4bc - 100)
=> 4bc - 100 > 0 => bc > 25
Now try values of c one by one:
c = 2 => b > 12.5 not possible since b is a single digit
c = 4 => b >= 7
b = 7 => a = 74/12 not integer
b = 8 => a = 84/28 = 3, it works.
b = 8, c = 4 => a = 3
Now check:
384 = 4.3.8.4 = 4.96 = 384.
Answer = 384.
Q2. Show that no square integer ends with 4 ones or 4 nines.
S2.
Square of any odd integer mod 8 = 1.1,3.3,5.5,7.7 = 1
If it ends in 1111 then n = k.10,000 + 1111
k mod 8 = 0 + 111 = 7
So not possible.
Similarly
k.10,000 + 9999 mod 8 = 0 + 999 mod 8 = 7
H.P.
Day 3:
Q1) Find all positive integers (m) such that for all odd positive integers (a), if (a^2 <= n) then (a | m).
S1:
Initial try:
1,9 n = 9
1,9,25 n = 30(it has to be a multiple of 15)
1,9,25,49 Now n has to be a multiple of 105 but that would mean 81 < 105 but 105 is not div by 9 so let's try 315 but that's not div by 11 and 13.
So looks like n = 9,30 are the only 2 numbers?
Here is the full solution:
Let a be the greatest odd integer s.t. a^2 <= n
=> n < (a+2)^2
So
a^2 <= n < (a+2)^2
So all the odd numbers before 'n' should divide 'n'.
So (a-4), (a-2), 'a' each of them will divide 'n'.
We know that any 3 consecutive odd numbers are pairwise co-prime.
Why?
gcd(2n+1,2n+3) = gcd(2n+1,2) = gcd(odd,2) = 1
gcd(2n+1,2n+5) = gcd(2n+1,4) = gcd(odd,2^2) = 1
So 'n' has to be at least (a-4).(a-2).a
=> (a-4).(a-2).a <= n^2 < (a+2)^2
=> a^3 - 6a^2 + 8a < a^2 + 4a + 4
=> a^3 - 7a^2 + 4a - 4 < 0
=> a^2(a-7) + 4(a - 1) < 0
Since a >= 1 and a^2 > 0 => a-7 < 0 => a < 7.
So the last odd integer for which it might work is 5.
Also we can see above that a cubic equation < quadratic won't hold for long.
So let's try for a = 1.
1^2 <= n < 3^2
=> n = {1,2,3,4,5,6,7,8} (1 divides all)
3^2 <= n < 5^2
=> 9 <= n < 25
=> n = {9,12,15,18,21,24} (1,3 divide all)
25 <= n < 49
=> n = {30,45} (1,3,5 divide all)
Q2.Prove that for different choices of signs (+) and (-), the expression
+-1+-2...+-(4n+1)yields all odd positive integers less than or equal to (2n+1)(4n+1).
S2.
If we take all signs positive then sum = S = (4n+1)(4n+2)/2 = (4n+1)(2n+1)
That's the max sum and it matches the one given in the problem.
Since it is product of 2 odd numbers, it is odd as well.
Now to generate the next odd number which is S - 2 we simply flip the sign of 1 from + to -.
To get S - 4, we revert 1 to + but flip 2 to -.
To get S - 6 we revert all but flip 3.
Flipping sign of 'k' subtracts '2k' from S and subtracting even number from an odd number will once again give an odd number.
In fact, every possible arrangement of signs will yield an odd integer.
.....
To get S-2*(4n+1) we revert all and flip the last sign of (4n+1).
From here to get the next odd number, we let the sign of (4n+1) be -.
And again repeat with 1,2,3 .. upto (4n-1). Now let the sign of (4n-1) remain -.
And keep doing it until you get 1.
And you will get 1 for sure.
Why?
Because the least odd number we can obtain like this is -(2n+1)(4n+1).
And we are generating each odd number in between => 1 will also be generated.
------------
More formal approach.
S = max sum = odd
flipping any sign won't change parity.
So all possible sums are odd.
We need to show that we can go all the way down to 1 without any gaps.
Let K be set of integers from 1 to 4n+1.
Let A be set of integers with negative signs.
Possible sum = S - 2[sigma(a) for each 'a' in A.]
We have to show that 2.sigma(a) can range from 0 to S-1.
=> show that sigma(a) can take every value from 0 to (S-1)/2
We will instead show that sigma(a) can take every value from 0 to S.
Empty subset will give 0.
Now single element subsets will give 1,2,3... 4n+1 all values.
Now retain 4n+1 and one by one add 1,2,3... so we get all values from 4n+2 to 4n+1+4n.
In this way we will reach upto (4n+1)(2n+1) H.P.
Day 4:
Q1. Prove that the sum of the squares of 3, 4, 5, or 6 consecutive integers is not a perfect square.
S1.
3 => (n-1)^2 + n^2 + (n+1)^2 = 3n^2 + 2 mod 3 = 2 (squares leave 0,1 mod 3)
4 => (n-2)^2 + 3n^2 + 2 = 4n^2 - 4n + 6 mod 4 = 2 (squares leave 0,1 mod 4)
5 => 4n^2 - 4n + 6 + (n+2)^2 = 5n^2 + 10 mod 4 = n^2 + 2 mod 4 = 2,3 (squares leave 0,1 mod 4)
6 => 5n^2 + 10 + (n+3)^2 = 6n^2 + 19 + 6n
Let's take mod 4
n % 4 = 0 => 3
n%4 = 1 => 3
n%4 = 2 => 3
n%4 = 3 => 3
But squares leave (0,1) mod 4.
Q2. Prove or disprove:
The sum of the squares of 11 consecutive integers is a perfect square. If yes, give an example.
S2.
=> n^2 + 10 = 11k^2 = k^2 + 10k^2
k = 1 gives n = 1 as one of the solutions and integers will range from -4 to 6.
Q3) Let p be an odd prime. Let q and r be primes such that p | q^r + 1.
Prove that either 2r | (p − 1) or p | (q^2 − 1).
S3. Prerequisites: Multiplicative order And Fermat's little theorem.
Given:
q^r = -1 mod p
=> q^2r = 1 mod p
=> k | 2r (where k is order of 'q' mod 'p').
and
q^k = 1 mod p.
'r' is prime so 'k' can be 1,2,r,2r.
Now we have a relation between 'k' and '2r' and the question asks for relation between '2r' and 'p-1'. As soon as we see 'p-1' we think FLT(Fermat's little theorem).
Using FLT:
a^(p-1) = 1 mod p where gcd(a,p) = 1
So here:
q^(p-1) = 1 mod p
=> k | (p-1)
So we have
k | (p-1)
k | 2r
And k can be 1,2,r,2r
Case 1: k = 1
q^1 = 1 mod p
=> q = 1 mod p
But given q^r = -1 mod p
=> 1 = -1 mod p
=> 2 = 0 mod p
but p is odd prime. So not possible.
Case 2: k = 2
q^2 = 1 mod p
=> p | q^2 -1 (which is one of the conditions given in the question).
Case 3: k = r
q^r = 1 mod p
But given q^r = -1 mod p (not possible same as k = 1)
Case 4: k = 2r
q^2r = 1 mod p
Given q^r = -1 mod p (so it matches)
k | p-1 => 2r | p-1 (which is also one condition in the question)
H.P.
Comments
Post a Comment