Fruits of procrastination

Month: May, 2020

Some problems from Indian National Mathematics Olympiad, 2014

I just want to add a couple of problems from INMO 2014 that I solved this morning. The first problem was slightly less tricky, and just involved pairing divisors with each other in the most obvious way. However, the second problem is quite devious, and is more of an existence proof than writing down an explicit winning strategy.

  • Let n be a natural number. Prove that \left\lfloor \frac{n}{1} \right\rfloor+\left\lfloor \frac{n}{2} \right\rfloor+\dots+\left\lfloor \frac{n}{n} \right\rfloor+\left\lfloor \sqrt{n} \right\rfloor is even.

We will prove this by induction. Let f(n)=\left\lfloor \frac{n}{1} \right\rfloor+\left\lfloor \frac{n}{2} \right\rfloor+\dots+\left\lfloor \frac{n}{n} \right\rfloor+\left\lfloor \sqrt{n} \right\rfloor. Note that f(1)=2 is even. Also, note that f(i)=f(i+1)+ the number of divisors of i+1. It is precisely at those divisors that 1 is added to f(i+1). If i+1 is not a square, then the number of divisors can be paired up as (d,\frac{i+1}{d}). Hence, the number of divisors should be even. Moreover, \lfloor \sqrt{i}\rfloor=\lfloor \sqrt{i+1}\rfloor. However, if i+1 is indeed a square, then \sqrt{i+1} is a divisor that cannot be paired up with a different divisor as \frac{i+1}{\sqrt{i+1}}=\sqrt{i+1} itself. However, \lfloor \sqrt{i+1}\rfloor=\lfloor \sqrt{i}\rfloor+1. Hence, we get two extra 1’s, which still keeps f(i+1) even. Hence, f(i) and f(i+1) have the same parity. Now as f(1)=2 is even, f(i) is even for all i\geq 1. Hence proved. QED

  • Written on a blackboard is the polynomial x^2+x+2014. Calvin and Hobbes take turns alternately (starting with Calvin) in the following game. During his turn, Calvin should either increase or decrease the coefficient of x by 1. And during his turn, Hobbes should either increase or decrease the constant coefficient by 1. Calvin wins if at any point of time the polynomial on the blackboard has integer roots. Prove that Calvin has a winning strategy.

Calvin’s first move should be to increase the coefficient of x by 1. We will prove that Calvin has a winning strategy by induction.

Observe that for x^2+x+2, Calvin has the following winning strategy: After the first move, the polynomial becomes x^2+2x+2. Now if Hobbes keeps increasing the constant coefficient, Calvin should do the same. If Hobbes reduces the constant coefficient at any step, the polynomial will becomes x^2+ax+(a-1)=0, which has the integer roots 1,a-1. Hence, Calvin has a winning strategy for x^2+x+2k when k=1.

Note that for the general polynomial x^2+x+2k, if both players keep increasing the coefficients without ever decreasing them, ultimately the polynomial becomes x^2+(1+k+3)x+(2k+k+3)=0, which has the integer roots 3,k+1. Hence, in order to avoid losing, Hobbes should reduce the constant coefficient at least once.

We will use a form of strong induction here. If Calvin has a winning strategy for x^2+x+2k, then he has a winning strategy for any x^2+(1+a)x+(2k+a)=0, where a\leq k+3.

Let us assume that Calvin has a winning strategy for x^2+x+2k. From the last statement, we know that this implies that Calvin has a winning strategy for x^2+(1+a)x+(2k+a)=0, where a\leq k+3. Now let us consider x^2+x+2(k+1)=0. If Hobbes keeps increasing the constant coefficient, then we know that Calvin should do the same, and that is a winning strategy. If after a moves, where a<k+1+3, if Hobbes decreases the constant coefficient on the (a+1)th move, then the polynomial becomes x^2+(1+a+1)x+(2k+2+a-1)=x^2+(1+a+1)+(2k+a+1)=0. By strong induction, we know that Calvin has a winning strategy for this. Hence proved. QED.

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