Miscellaneous problems (sorted)

This discussion was started by someone posting seventeen problems at once, which made it very difficult to edit. In this version, the discussion has been sorted by question number, but the names of contributors have not been preserved. The original discussion may be found here .

QUESTION ONE

1. Find all solutions : 6x + 10y + 15z = 1

Hint:
Run Euclid

I know Euclid's algorithm and how to apply it for an eqn such as 243x + 198y = 9, but this equation in three variables stumps me. So you see, your hint was not all that useful.
I was hoping to look to your solution to this as an example problem to learn the application of the algorithm to more than 2 variables, so please post your solutions.

Apply Euclid more than once (ie 6x + 10y will always be off the form 2m, since hcf(6,10)=2)?

We can spot a solution 6-2 x 10+15=1. Also, we know that LCM(6,10,15)=30. So we know the general solution is

x=5m+1, y=3n-2, z=1-2m-2n.

[Comment: This question can also be done in a variety of ways, for example, considering mod 2,3,5 in turns, or run Euclid twice as suggested by Olof. This is one of those question anybody doing Olympiads must know.]

Sorry, but I can't quite see how you did Q1. Some further explanation would be greatly appreciated.

OK, I will do this another way:

The equation we are given is 6x+10y+15z=1

Looking in mod 3, we see that y = 1 mod 3
Looking in mod 5, we see that x = 1 mod 5
Looking in mod 2, we see that z = 1 mod 2.

Can we now find a solution? Yes, we have (x,y,z)=(1,-2,1) is a solution. Now, we can add an arbitrary multiple of 3 to y and an arbitrary multiple of 5 to x, as long as we correct z appropriately. Hence

(x,y,z)=(1+5m, 3n-2, 1-2m-2n), m,n are integers

is the complete solution.

QUESTION THREE

3. If p is a prime other than two and five prove that p divides infinitely many of the integers 1,11,111,1111... and 9,99,999,9999...

Hint:
Use Fermat's little theorem

By Fermat little theorem, we know that, for p prime not dividing 10,

10^p-1 = 1 mod p

Rearrange, we get p|99...9 (p-1 9's)

Now, if p is not 3, then p is coprime to 9 and we get p|11...1, and so p divides infinitely many, as any string of k(p-1) 1's is a multiple of (p-1) 1's.

If p is 3, note that 3|111 and we are done by the same argument.

[Comment: This question is also pretty standard. It features in a past tripos. There are slightly harder versions, e.g. proving the list 10001,100010001,1000100010001,... has no primes.

QUESTION FOUR

4. For a positive integer k, prove that there are k consecutive integers each divisible by a square greater than 1.

Hint:
Chinese Remainder Theorem

Please give me the statement of Chinese remainder theorem and apply it to a simple problem for me to understand its application, and of course, this problem. I have not come across such a problem.

[Comment: Standard application of CRT. If you are not familar with CRT, we can always look at the question from first principles by finding strings of non-'square-free' numbers: and probably start off by {4}, {8,9}, {48,49,50},... before getting the idea of applying CRT.]

QUESTION FIVE

5.Prove that if 2ⁿ | N, 2ⁿ also divides the last n digits of N.

Hint:
2ⁿ divides 10ⁿ

By division algorithm, let N=a10ⁿ +b, where 0< = b < 10ⁿ . Now 2ⁿ |N, and 2ⁿ |10ⁿ , so 2ⁿ |b, as required.

[Comment: This is a standard test for divisibility by 2ⁿ . A similar one exists for 5ⁿ ]

QUESTION SIX

6. S_n = (3 + root5)ⁿ + (3 - root5)ⁿ
Prove that S_n is an integer and that S_n+1 = 6S_n - 4S_{n - 1}
Prove that the next integer greater than (3 + root5)ⁿ is divisible by 2ⁿ .

Hint:
Once you obtain the recurrence relation, the remaining parts are trivial. To obtain the recurrence, consider the quadratic with roots 3±sqrt(5)

What is meant by "recurrence relation" ?

Hint:
Recurrence relation is just equation for a sequence (a_i ) , relating a_n to the previous terms. It is also called difference equation. In this question, you can just directly substitute in S_n to show that the recurrence is satified. The last part is based on the fact that 0 < 3-sqrt(5) < 1, so S_n is the next integer above (3+sqrt(5))ⁿ . Use induction.

In your original hints you mentioned "To obtain the recurrence, consider the quadratic with roots 3±sqrt(5)".
How can you deduce the recurrence relation from this quadratic (the co-efficients are obviously the same, but I cannot the see the way into it from there)? Sounds intruiging. We have:

$λ^{2} - 6 λ + 4 = 0 \Leftrightarrow λ = 3 \pm \sqrt{5}$ .

i.e. $(3 \pm \sqrt{5})^{2} = 6 \times (3 \pm \sqrt{5}) - 4$

now multiply by $(3 \pm \sqrt{5})^{n}$ and recover the recurrence.

Another way is to directly substitute for $S_{n}$ , and the result will come out after a few lines of working.

S_n is an integer: We find that S₀ and S₁ are integer. Hence by the recurrence relation (done above), S₂ , S₃ , ... are integers. We also found S₁ =6 divisible by 2, and obviously 1|S₀ , so do induction on the recurrence we get 2ⁿ |S_n . Now find that 0 < S_n -(3+sqrt(5))ⁿ < 1, hence result.

QUESTION SEVEN

7. Prove that 2ⁿ > n³ if n > 9.

Hint:
Induction

Obviously induction is to be used, but I was not able to complete the problem using induction. That's why I posted it in the first place.

Assume true for n=k, so 2^k > k³ . Then 2^k+1 > 2k³ . You therefore need to show that 2n³ > = (n+1)³ for n > 9, which you can do using calculus.

For the inductive step, we shall prove that 2> (1+n^-1 )³ for n> 9. Clearly RHS is decreasing, so suffice to show this holds true for n=10, but RHS=1.331 < 2=LHS. It is now trivial task to verify n=10 satisfies the inequality 2ⁿ > n³ .

[Comment: A very standard proof by induction.]

QUESTION EIGHT

8. Prove that there are infinitely many sets of five consecutive positive integers a,b,c,d,e such that a+b+c+d+e is a perfect cube and b+c+d is a square.

Hint:
Notice if a,b,c,d,e are consecutive integers then a+b+c+d+e=5c, etc.

All those relations did not get me anywhere. I have an idea as to how the proof should be but am not able to write it down formally and would like you to do that.]

a+b+c+d+e = 5c = P³ , b+c+d = 3c = Q² . Therefore you need to show that there exists infinitely many squares with a factor 3 (consider 9 xany other square), and that there are infinitely many Q's and P's such that 5Q² = 3P³ (consider prime factorisation).

(refer to Olof's post) Find that, for c in the form 675m⁶ , a+b+c+d+e=3375m⁶ which is a cube, and b+c+d=2025m⁶ , which is a square. Since m is chosen freely from Z , we get there are infinitely many c's.

[Comment: Try solving questions such as a³ +b³ =c⁴ or a³ +b⁴ =c⁵ by the same technique.]

QUESTION NINE

9. Prove that if three distinct integers are chosen at random there will exist two among them such that 30 | a³ b - ab³

Hint:
Factorise a³ b-ab³

I did factorise a³ b - ab³ , but I did not know what to do because I have never come across this type of problem, which says that out of ANY three distinct integers, there will exist two amongst them such that.....What is the significance of that statement in the problem ?

The significance of choosing 3 integers is that it will not work if one of the numbers is a particular integer (e.g. try a = 1, b = 2). Since each integer you have chosen is distinct, the 3rd number cannot be 1 as well, so it will work for 2 and this 3rd number.

First, factorise a³ b-ab³ =ab(a² -b² ). Now, for any a,b integers, we can show that 2 and 3 both divides a³ -ab³ :

If a or b is even, then 2|ab(a² -b² ), and if both are odd, their squares are odd, so the diffence of square is even.

If a or b is a multiple of 3, then the result follows trivially. If not, we know that a,b =/= 0 mod 3, so a² =b² =1 mod 3 and a² -b² is a multiple of 3.

The reason why we need to choose a,b from 3 numbers is the make 5|a³ b-ab³ . Starting with our set {a,b,c}, Either there is a multiple of 5 among the set (so we are done), or none of them are. In the latter case, consider mod 5:

1² =4² =1, 2² =3² =-1

so we can choose two numbers from this set to make a² -b² a multiple of 5 by pigeonhole.

[Comment: Some standard result should be known, for example squares mod 3 are 0,1, squares mod 5 are 0,±1, mod 8 are 0,1,4. Also, (p-1)/2 powers in mod p are 0,±1. Proving these will probably increase confidence in their use.]

QUESTION TEN

10. 7 people enter a lift which stops at 3 unspecified floors. At each floor,nobody enters the lift but atleast one person leaves. The lift is empty at the top. In how many ways can this happen ?

Hint:
Brute-force would work.

I am weak in combinatorics and I am not able to actually work out the number of ways here because nothing much seems to be given.

I would employ brute-force method here. Since there are only 3 floors, and there must be at least one person leaving at each floor, we are down to the problem of finding all ordered triplet of non-negative integer which sums to 4, so we have (4,0,0),(3,1,0),.... (list them!).

Consider each case separately, we find that there are 1 way for the first slot=4, 2 ways for first slot=3, ..., 5 ways for first slot=0. So in total there are 1+2+3+4+5=15 ways of doing so.

[Comment: Brute-force often probably not produce nice solutions in Olympiad, but when you have nothing better ....]

QUESTION ELEVEN

11.Factorise 5¹⁹⁸⁵ - 1 into a product of three integers each greater than 5¹⁰⁰ .

Hint:
One factor is trivial (try factorising 1985). The other 2 are a little bit more subtle.

QUESTIONS TWELVE TO FOURTEEN

12. An international society has members from 6 different nations. The list of members contained 1994 names numbered 1,2,3,4... 1994. Prove that there is at least one member whose number is the sum of 2 members from his own country or twice as large as the number of one member from his own country.

13. If a chess player plays 132 games in 77 days, prove that for a certain number of consecutive days he has played exactly an aggregate of 21 games.

14. If there are 1985 points inside a unit cube, prove that we can always choose 32 of them in such a way that every closed polygon with these points as vertices has a perimeter which is less than 8 root3.

Hint:
Pigeon-hole

Well, to be absolutely frank, all I know about these problems is that I have to apply the PHP. But I am stumped because these problems of such complexity in the PHP and really have no idea what to do !

Hint:
Pigeon-hole principle states that, if there are n holes and n+1 objects, then there must be at least one hole with more than 1 object. I'll use this to prove 14.

Since we are given a unit cube, it makes sense to dissect it into smaller cubes. But how should we dissect it? There are 2 ways of seeing what to do. We can either work out 1985/32=62+fractional part, or see that 8sqrt(3)/(sqrt(3) x 32)=1/4. Either case, we see we have to dissect the cube into 64 identical cubes with side length 1/4.

Now, 31 x 64=1984, which is one short of 1985. So we conclude that there must be one of our little cubes containing 32 or more points. Now, the 32-gon has each side bounded by sqrt(3)/4, which is the diagonal of the cube. So we get the perimeter of the 32-gon is at most 32sqrt(3)/4=8sqrt(3). But this bound is clearly unattainable. QED

I'll write out my attempt at 13. We have to assume that the player play at least one game every day otherwise the result is false. If he played all his games on the first day, for example, then he would never have played 21 games in consecutive days.

Now suppose he plays > = 1 game each day, but there is no set of consecutive days in which he plays exactly 21 games. Define f(n) as the number of games he played in total, during days 1,2,...,n. f(n) is strictly increasing with f(77) = 132 and for any m,n in [1,77] we know f(m) =/= f(n) + 21 otherwise he would have played exactly 21 games during days m+1,m+2,...,n.

We know that |range f(x)| = 77 because f is injective (because it is strictly increasing). Now we prove a simple intuitive result:

Lemma

If the set D is a subset of {1,2,...,n} and D doesn't contain any consecutive numbers, then |D| < = (n+1)/2.

Proof of Lemma

It clearly holds for n = 1,2. Suppose it holds for 1,2,...,n-1 where n > = 3. Then for any subset D of{1,2,...,n} without consecutive numbers then if D contains n then D can't contain n-1 so:

D{n} is a subset of {1,2,...,n-2} with no consecutive integers, so
|D{n}| < = ((n-2)+1)/2 by the inductive hypothesis, i.e. |D| < = (n+1)/2.

(NB D{n} means the set D with n excluded.)

If D doesn't contain n then D is a subset of {1,2,...,n-1} with no consecutive integers and by the inductive hypothesis |D| < = ((n-1)+1)/2 < = (n+1)/2

Hence result by induction.

Now we can partition {1,2,...,132} into the following sets:

{1,22,43,...,106,127} (set 1)
{2,23,44,...,107,128} (set 2)
...
{6,27,48,...,111,132} (set 6)
{7,28,49,...,112} (set 7)
{8,29,50,...,113} (set 8)
...
{21,42,63,...,126} (set 21)

where the first 6 sets contain 7 elements and the other 15 contain 6.

Now range f is 77 integers in [1,132], no two of which differ by 21. By the lemma, at most (7+1)/2 = 4 of these can come from set 1 since set 1 has 7 elements. Likewise, range f can only share 4 elements with sets 2,3,...,6. Sets 7,8,...,21 have 6 elements, so range f cannot share more than (6+1)/2 elements with them, i.e. at most 3.

Therefore |range f| < = 6 x 4 + 15 x 3 = 69. However above we have shown |range f| = 77 so we have a contradiction, therefore he must play 21 games in consecutive days, QED.

An alternative proof, running a similar line of argument, is to use pigeonhole. Take the example {1,22,...,127}. If we partition the set as

{1,22} U {43,64} U {85,106} U {127}

we see that, by pigeonhole, if we pick more than 4 we have to have one of the doubleton as a subset of our selection. Similar comments on the other 20 sets. Now apply pigeonhole to our selection of 77.

QUESTION SIXTEEN

16. Prove that 5¹²⁵ - 1 / 5²⁵ - 1 is a composite number.

Hint:
This requires you to spot a factorisation of 5¹⁰⁰ +5⁷⁵ +...+1, which means you have to write it as a diffence of 2 squares. I think that is one of the question from the 1978-85 IMO & 40 supplementary problems.)

Once you have done this, you might like to try proving (7³⁴³ +1)/(7⁴⁹ +1) is composite, and in general, if p is an odd prime then

(p^{p^3} -1)/(p^{p^2} -1) is composite for p = 1 mod 4

(p^{p^3} +1)/(p^{p^2} +1) is composite for p = 3 mod 4