cozilikethinking

4 out of 5 dentists recommend this WordPress.com site

Tag: math olympiads

Some solutions

I solved two math problems today. The solutions to both were uniquely disappointing.

The first problem was the first problem from IMO 1986:

Let d be a number that is not 2,5 or 13. Prove that out of the set \{2,5,13,d\}, we can select two different numbers a,b such that ab-1 is not a square.

A quick check would show that 2.5-1, 2.13-2 and 5.13-1 are all squares. This shows that of the two numbers that we select from \{2,5,13,d\}, one of them has to be d. We essentially need to prove that for d\neq 2,5,13, 2d-1, 5d-1 and 13d-1 are not all squares (a maximum of two of them might be. But all three cannot).

I tried figuring out some of the implications of all of them being squares, but couldn’t come up with anything concrete, as I didn’t write anything at all, and just tried to devise a strategy mentally. Ultimately, I came up with possibly the most mundane proof of all time.

Proof: Consider squares \mod 16 (I couldn’t come up with any contradiction up until \mod 8). The possible residues for squares \mod 16 are 0,1,4,9. Now my strategy was to plug in all possible residues \mod 16 in place of d, and checking that in every such instance, at least one of 2d-1, 5d-1 and 16d-1 gave a residue that was not 0,1,4,9\mod 16. This I could successfully verify. Hence proved.

The solution that I could find in the IMO compendium was much smarter, but involved some algebra that would obviously involve putting pen to paper.

The second question that I solved today was proving the Koszul formula, which states that

2g(\nabla_X Y,Z)=D_Xg(Y,Z)+D_Yg(X,Z)-D_Zg(X,Y)-g([Y,X],Z)-g([X,Z],Y)+g([Z,Y],X)

I’d seen proofs before in textbooks, that would involve writing down expansions, and then combining all of them in some clever way. The way that I came up with was pretty algorithmic, and perhaps even more elementary. It is simply the following: Take g(\nabla_X Y,Z). Use the torsion free condition to write it as g(\nabla_Y X,Z)+g([X,Y],Z). Now use the formula for connection acting on a tensor to write g(\nabla_Y X,Z) as D_Y g(X,Z)-g(X,\nabla_Y Z). Performing the two operations, we have D_Yg(X,Z)-g(X,\nabla_Y Z)+g([X,Y],Z). Performing this operation of first using the torsion free condition and then the formula for a connection on a tensor three times, we get the Koszul formula.

Math Olympiads #1

I’ve been obsessed with Math Olympiads and other kinds of competitive math for a loong time now. Although I should be doing more serious mathematics now that can actually get me a job, I shall ignore good sense and start my series of posts on Math Olympiad problems!

The first problem that I want to write about is a relatively easy one from IMO (International Math Olympiad) 1974. I think it was a long-listed problem, and didn’t actually make it to the test. It asks to prove the fact that

\displaystyle 343|2^{147}-1

(that 343 divides 2^{147}-1)

The important thing in this problem is to figure out that 343=7^3 and 147=3.7^2. Hence, we’re being asked to prove that 7^3|2^{3.7^2}-1.

We have the following theorem for reference: If a and b are co-prime, then a^{\phi(b)}\equiv 1\pmod b, where \phi(b) is the number of natural numbers that are co-prime with b. Fermat’s Little Theorem is a special case of this.

Now on to the calculations and number crunching. We have fleshed out the main idea that we’ll use to attack the problem. We can see that \phi(7^3)=7^3-7^3/7=6.7^2. Hence, as 2 is co-prime with 7^3, 2^{6.7^2}-1\equiv 0\pmod {7^3}. We can factorize this as (2^{3.7^2}+1)(2^{3.7^2}-1)\equiv 0\pmod {7^3}. Now we have to prove that 7^3 does not have any factors in common with 2^{3.7^2}+1. As 2^3\equiv 1\pmod 7, 2^{3.7^2}\equiv 1\pmod 7 too. Hence, 2^{3.7^2}+1\equiv 2\pmod 7. This shows that 2^{3.7^2}+1 does not have any factors in common with 7^3, and leads us to conclude that 7^3|(2^{3.7^2}-1), or 343|2^{147}-1. Hence proved.

I realize that the formatting is pretty spotty. I shall try and re-edit this in the near future to make it more readable.