Fruits of procrastination

Tag: math olympiads

Exploring Indian Mathematical Olympiads

Indian math olympiad questions are famous (infamous?) for being very analytical. There mostly do not exist any clever one line proofs. Multiple cases have to be analyzed and exhaustively eliminated before arriving upon the correct answer.

I tried solving problems from the Indian National Mathematics Olympiad, 2013 today. My solutions are different (lengthier, and hence perhaps instructive) from the official solutions given online. Hopefully they can be of help to anyone interested in mathematical problem solving.

The Indian National Mathematics Olympiad (INMO) is offered to those candidates who have cleared the Regional Mathematics Olympiad (RMO). The questions that are given are of a difficulty level comparable with P1, P4 of the International Math Olympiad.

I do plan on running a seminar on competitive math problem solving this summer. This is useful for all sorts of things, like getting better at algorithms, improving analytical skills in finance, etc. Please do let me know if you’d be interested in that sort of thing.

  • Find all positive integers m,n and primes p\geq 5, such that m(4m^2+m+12)=3(p^n-1)

First, we make a couple of observations. As p^n-1 is a multiple of 2, m will also have to be a multiple of 2. This can be re-written as 4m^3+m^2+12m+3=3p^n. On factorizing the left hand side, we get (4m+1)(m^2+3)=3p^n. Hence, as the right hand side is a multiple of 3, either 4m+1 is a multiple of 3, or m is a multiple of 3.

If 4m+1 is a multiple of 3 and m is not, then it has to be a multiple of 9, as m\equiv 2\pmod 3 is the only possibility. This is impossible as p\geq 5. Hence, 3|m. Note that from our previous observation, we also know that 2|m. Hence, combining the two, we get 6|m.

Let m=6m'. Then we have (24m'+1)(12m'^2+1)=p^n (we obtain this after canceling out 3 on both sides). For m'\geq 2, we have 24m'+1\leq 12m'^2+1. Hence, as the right hand side is p^n, we have 24m'+1|12m'^2+1. This implies that 24m'+1|12m'^2+1-(24m'+1)=12m'(m'-2). The right hand side is a multiple of 12m' while the left hand side is not. Hence, this is only possible if m'-2=0, or m'=2. As m=6m', we get m=12.

From this, we can deduce that (24m'+1)(12m'^2+1)=49^2, and hence p=7 and n=4. (12,7) is the only solution. QED

  • Let a,b,c,d be positive integers such that a\geq b\geq c\geq d. Prove that x^4-ax^3-bx^2-cx-d has no integer solutions.

Let x be a solution. Clearly x=0 cannot be a solution, as then we would have d=0, which is impossible as d is a positive integer. Hence, let us assume that x is a non-zero integer. Then we have x^4-ax^3-bx^2-cx=d. Therefore, x|d. Let d'=\frac{d}{x}. Then we have x^3-ax^2-bx-c=d'. Continuing like this, we get x=a+b'+c''+d''', where d'''=\frac{d}{x^3}, c''=\frac{c}{x^2}, and b'=\frac{b}{x^2}.

In other words, we have x=a+\frac{b+c'+d''}{a+b'+c''+d'''}. Clearly, as a\geq b\geq c\geq d, we have \frac{b+c'+d''}{a+b'+c''+d'''}\leq \frac{a+b'+c''}{a+b'+c''+d'''}<1. Hence, $x$ is not an integer. Hence proved. QED

  •  Let n be a positive integer. Call a nonempty subset S of \{1,2,\dots,n\} good if the arithmetic mean of the elements of S is also an integer. Further, let t_n denote the number of good subsets of \{1,2,\dots,n\}. Prove that t_n and n are either both odd or even.

Clearly, this is equivalent to proving that t_n-n is always even. Note that subsets consisting of one element have an arithmetic mean that is an integer. Hence, we can prove that the number of good subsets of \{1,2,\dots,n\} containing at least two elements will be even. The way that we’ll prove this assertion is by forming a pairing between sets: if \{a_1,\dots,a_k\} is one such subset, then consider the set \{n+1-a_1,\dots,n+1-a_k\}. Clearly this set will also have an integer average, and the map i\to n+1-a is idempotent. Hence, the mapping is bijective.

Case 1: Let n be even. The only cases in which bijective pairing maps a set to itself is for every i in the set, n+1-i is also included in it. As there is no i\in\{1,2,\dots,n\} such that i=n+1-i, as n+1 is odd, a set for which bijective pairing fails will have to contain an even number of elements. Hence, t_{2k+1} is even for all k\geq 1. For sets of the form t_{2k}, if i and n+1-i are both included, then the average will be \frac{k(n+1)}{2k}, which is clearly not an integer as n+1 is odd. Hence, every good set can be bijectively paired with a different good set, which implies that the total number of good sets is even.

Case 2: Let n be odd. Let us study the good sets for which the map i\to n+1-i does not produce a different set. The only different is that when i=\frac{n+1}{2}, i=n+1-i. Hence, sets of both odd and even number of elements can map to themselves through this pairing. However, if we can prove that t_{odd} and t_{even} are both odd, then their sum will be even. Combining this with the fact that the number of sets which map to other sets is anyway even, we get a total number of even sets.

Let us consider t_{2k+1}. Any set of this form will have to contain the element \frac{n+1}{2}. The total number of such sets is hence {n-1\choose 1}+{n-1\choose 2}+\dots+{n-1\choose n-1}=2^{n-1}-1, which is odd.

Let us now consider t_{2k}. Then the element \frac{n+1}{2} cannot be contained in such a set. Hence, the total number of elements is {n-1\choose 1}+\dots+{n-1\choose n-1}=2^{n-1}-1, which is odd.

Adding both cases together, we get an even number of sets that map to themselves through this mapping.

Hence, the total number of sets is even, which proves our assertion. QED

  •  Let a,b,c,x,y,z be positive real numbers such that a+b+c=x+y+z and abc=xyz. If a<b<c, x<y<z, and a\leq x<y<z\leq c, then prove that x=a,y=b and z=c.

This is one of my favorite problems. Without loss of generality, let x-a\geq c-z. Then keeping a+b+c constant, bring c\to z and a\to a+(c-z)=a'. This keeps b unchanged, and hence a'z\geq ac (as (a+x)(c-x)\geq ac), which implies a'bz\geq abc. Now keeping z constant, bring a'\to x and b\to y. This again implies that xy\geq a'b, which implies that xyz\geq a'bz\geq abc. Hence, xyz\geq abc if any of these changes happens. Hence, as abc=xyz, none of these changes should happen, and a=x,b=y and c=z. QED

A beautiful generalization of the Nesbitt Inequality

I want to discuss a beautiful inequality, that is a generalization of the famous Nesbitt inequality:

(Romanian TST) For positive a,b,x,y,, prove that \frac{x}{ay+bz}+\frac{y}{az+bx}+\frac{z}{ax+by}\geq \frac{3}{a+b}

Clearly, if a=b, then we get Nesbitt’s inequality, which states that

\frac{x}{y+z}+\frac{y}{z+x}+\frac{z}{x+y}\geq \frac{3}{2}.

This is question 14 on Mildorf’s “Olympiad Inequalities”, and its solution comprises finding a factor to multiply this expression with, almost out of thin air, and then use Cauchy Schwarz and AM-GM inequalities to prove the assertion. My solution is the following:

On interchanging a and b, the right hand side remains the same. However, the left hand side becomes

\frac{x}{az+by}+\frac{y}{ax+bz}+\frac{z}{ay+bx}\geq \frac{3}{a+b}

On adding these two inequalities, we get

\frac{x}{ay+bz}+\frac{x}{az+by}+\frac{y}{az+bx}+\frac{y}{ax+bz}+\frac{z}{ax+by}+\frac{z}{ay+bx}\geq \frac{6}{a+b}

Multiplying both sides by \frac{1}{2}(a+b) and then adding 6 on both sides, we get

2(x+y+z)(\frac{1}{x+y}+\frac{1}{y+z}+\frac{1}{z+x})\geq 9

This is obviously true by Cauchy Schwarz. We will explain below how we got this expression.

Let us see what happens to \frac{x}{ay+bz}+\frac{x}{az+by} in some detail. After multiplying by \frac{1}{2}(a+b) and adding 2, we get

\frac{\frac{1}{2}(a+b)x+ay+bz}{ay+bz}+\frac{\frac{1}{2}(a+b)x+az+by}{az+by}\geq 2\frac{(a+b)(x+y+z)}{(a+b)(y+z)}=2\frac{(x+y+z)}{y+z}.

EDIT: I assumed that this was obviously true. However, it is slightly non-trivial that this is true. For \frac{a}{b}+\frac{c}{d}\geq 2\frac{a+c}{b+d}, the condition that should be true is that (b-d)(bc-ad)\geq 0. This is true in our case above.

After adding the other terms also, we get

2(x+y+z)(\frac{1}{x+y}+\frac{1}{y+z}+\frac{1}{z+x})

As pointed above, this is clearly \geq 9 by Cauchy-Schwarz.

Hence proved

Note: For the sticklers saying this isn’t a rigorous proof, a rigorous proof would entail us assuming that

\frac{x}{ay+bz}+\frac{y}{az+bx}+\frac{z}{ax+by}< \frac{3}{a+b}, and then deriving a contradiction by proving that

2(x+y+z)(\frac{1}{x+y}+\frac{1}{y+z}+\frac{1}{z+x})< 9, which is obviously false

A small note on re-defining variables to prove inequalities

I just want to record my solution to the following problem, as it is different from the one given online.

For a,b,c,d positive real numbers, prove that \frac{1}{a}+\frac{1}{b}+\frac{4}{c}+\frac{16}{d}\geq \frac{64}{a+b+c+d}

This has a fairly straight forward solution using Cauchy-Schwarz inequality, which for some reason I did not think of.

The way that I solved it is that I re-defined the variables: let a=8a', b=8b', c=16c' and d=32 d'. Then this is equivalent to proving that \frac{1}{8}\frac{1}{a'}+\frac{1}{8}\frac{1}{b'}+\frac{1}{4}\frac{1}{c'}+\frac{1}{2}\frac{1}{d'}\geq \frac{1}{\frac{a'}{8}+\frac{b'}{8}+\frac{c'}{4}+\frac{d'}{2}}

This is easily seen to be a consequence of Jensen’s inequality, as \frac{1}{x} is a convex function for positive x.

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.