4. Let m and n be integers greater than 1. Consider an m x n rectangular grid of points in the plane. Some k of these points are coloured red in such a way that no three red points are the vertices of a right-angled triangle two of whose sides are parallel to the sides of the grid. Determine the greatest possible value of k.

It is trivial to prove the result is true for m=2 and all n, and n=2 and all m. I then proved that if it is true for (m,n) = (i,j-1) and (i-1,j), then it is true for (m,n) = (i,j), and the general result follows. I think.

Paul

Actually, the induction step wasn't particularly obvious (or simple)! I can explain it if you'd like.

Paul

4 is k=m+n-2 i think because i could see how it should be arranged along the twoperpendicular sides minus the one in the corner so m+n -2 but had no idea how to prove it!

Umm ... now I need to remember it!

I think I said it is sufficient to prove that given any m x n grid with m+n-2 red points, there must be at least one red point in every row/column (because then adding another point will create one of the forbidden triangles).

Now, suppose our conjecture (that k < = m+n-2) is true for (m,n) = (i,j-1) and (i-1,j), and consider an (i,j) grid. Let i be the number of columns and j the number of rows. If (at least) one column is empty, we can can create an (i-1,j) grid with i+j-2 red points, contradicting our assumption. Similarly, no row can be empty. Hence our conjecture holds for (i,j).

Also, as I stated in a previous post, we can easily prove the conjecture holds for m=2 and all n, and n=2 and all n. After a little reflection, we can see that this (I hope!) proves the conjecture for all m and n.

Of course we must also show that k = m+n-2 is possible, and this can be done using Ruth's method.

Paul

Or you can use induction directly, i.e. claim that for an mxn grid with the desired property the number of red points is < = m+n-2.

Given an mxn grid, pick any red point. We know it either belongs to an otherwise empty row or an otherwise empty column. Chuck this row or column out. This gets rid of exactly one red point and reduces the value of m+n-2 by one so we're done on applying the induction hypothesis to the smaller grid.

For Q5 I think the difficult part is dealing with the case a = b. (It is easy to see we require a = b for otherwise WLOG a < b. Then reducing mod b! we get c! = -a! =/= 0 (mod b!) so b! doesn't divide c! so b > c. Therefore a!b! < a! + 2b! so (a!-1)(b!-2) < 2 which gives a few easy cases to check.)

But the a = b case doesn't appear obvious. We get 2a! + c! = a!² with c > a (since a!|c! and we cannot have a = c as then a! = 3) so 2 + c!/a! = a!. Now I think one way of finishing is to reduce mod a+1. It is easy to see that for composite a > 3 we have a+1|a!. If a is prime we have a+1|a!+1 (this is Wilson's theorem). So in any case for a > 3 we have a! = 0 or -1 (mod a+1) so on reducing the equation 2 + c!/a! = a! mod a+1 we get 2 + 0 = 0 or -1 (mod a+1) so a+1|2 or a+1|3 which contradicts a > 3. So we must have a = 0,1,2 or 3 and from here it's trivial.

But I'm not really sure you're supposed to know Wilson's theorem in Olympiads and the above seems very clumsy anyway so maybe Paul, Angelina or Demetres or anyone else who's solved it can help me out here.

If $m=1$, $a!=2+(a+1)$ so $(a-1)!=1+3/a$ and therefore $3|a$, giving $a=3$ (as $a\ge 3$). If $m=2$, $a!=2+(a+1)(a+2)$ so $(a-1)!=(a+3)+4/a$ and $a=4$. But this doesn't satisfy the equation.
Thus (a,b,c) = (3,3,4) is the only solution.

Paul

Thank you, that's much simpler.