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

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

4.for a positive integer k,PT there are k consecutive integers each divisible by a square greater than 1.

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

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

7.PT 2ⁿ > n³ if n > 9.

8.PT 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.

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

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 ?

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

12.An international society has members from 6 different nations.The list of members contained 1994 names numbered 1,2,3,4... 1994.PT there is atleast 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, PT 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,PT 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.

15.Find all n such that n² | 2ⁿ + 1.

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

17.There are 5 pts in a plane.From each point,perpendiculars are drawn to the lines joining the other points.What is the maximum number of points of intersection of these perpendiculars?

18.Find the number of permutations of {1,2,3,4,5,6} in which the patterns 13 and 246 do not appear.

It is not good to ask more than one question at a time.
Please don't do this. We classify the questions by topic and can't do so when there are multiple questions in one message. We can also give clearer guidance if the questions come one at a time.

Toni

What does PT mean?

I'm guessing "prove that".

yes, PT means Prove that

Here are some hints:

1. Run Euclid
3. Use Fermat's little theorem
4. Chinese Remainder Theorem
5. 2ⁿ divides 10ⁿ
6. Once you obtain the recurrence relation, the remaining parts are trivial. To obtain the recurrence, consider the quadratic with roots 3±sqrt(5)
7. Induction
8. Notice if a,b,c,d,e are consecutive integers then a+b+c+d+e=5c, etc.
9. Factorise a³ b-ab³
10. Brute-force would work.
11. One factor is trivial (try factorising 1985). The other 2 are a little bit more subtle.
12. Pigeon-hole
13. Pigeon-hole
14. Another Pigeon-hole

I'll leave the others (16 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.)

Kerwin

Once you have done 16, 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

Kerwin

1.I know Euclid's algorithm and how to apply it for an eqn such as 243x + 198y = 9
but this eqn 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 pls post ur solutions.
4.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
6.what is meant by "recurrence relation" ?
7.Obviously induction is to be used,but I was not
able to complete the problem using induction.Thats why I posted it in the first place.
8.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.]
9.I did factorise acubed b - ab cubed,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 i the problem ?
10.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.
12,13,and 14. Well, to be absolutely frank,all I know about these problrems is that I have to apply the PHP.But I am stumped because these problems of such complexity in the PHP and really hae no idea what to do !

PS - I don't give up very easily.I have tried each of these problems atleast 4 times and have posted it only after every single direction in which I approached the problem yielded nothing !
9.

The following might help Niranjan (notice the might - I haven't had time to work through them all properly yet):
1. Apply Euclid more than once (ie 6x + 10y will always be off the form 2m, since hcf(6,10)=2)?
7. 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.
8. 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 * any other square), and that there are infinitely many Q's and P's such that 5Q² = 3P³ (consider prime factorisation).
9. 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.

btw, what's this pigeon-hole thing?

Regards,
Olof

Dear Kerwin,
Please post clean solutions to all these problems
I myself am searching for the solutions for seven of these !

OK, I'll do a brief outline of some:

4. Chinese Remainder Theorem states that, for pairwise coprime a₁ ,a₂ ,...,a_n , the simultaneous congruence

xº b_i mod a_i , i=1,2,...,n

is soluble and has unique solution mod a₁ ...a_n .

Now let a+1 be the smallest integer in the sequence, and p_k be the kth prime. The congruence

aº -i mod p_k ²

must be soluble. QED.

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

10. 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!).

12,13,14. 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)*32)=1/4. Either case, we see we have to dissect the cube into 64 identical cubes with side length 1/4.

Now, 31*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

Happy cracking

Kerwin

PLEASE POST CLEAN SOLS TO THE OTHER PROBLEMS

It is often valuable to try and struggle with the question, rather than looking at the answer straight after reading the question. Only by doing the question one learns more about problem-solving and appreciate the problem. Thus I only posted outline of solutions to some of them. Perhaps you would like to post your approach here?

Kerwin

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

Thanks,
Olof

Kerwin

I'll write out my attempt at 13. Overall I think the first 10 are considerably easier than the last 8, and I'm a bit stuck on 15.

Anyway, with question 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*4 + 15*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.

Kerwin

OK, I will post full solution to the first 10. I was thinking there may be some other people who would like to try them out first.

Q1. We can spot a solution 6-2*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.]

3. 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. Also, is it suppose to be a joke that there is no question 2?]

4. is done above.

[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.]

5. 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ⁿ ]

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

[Comment: Another similar question is to find the digit immediately in front, and the three digits immediately after the decimal point of (sqrt(2)+sqrt(3))¹⁰⁰⁰ .]

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

8. (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.]

9. 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.]

10. As above. 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 ....]

Kerwin

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.

Kerwin