A cute problem form India's UPSC exam

 UPSC is India's civil services exam, and surprisingly, the following cute problem appeared. Admittedly, it was a multiple choice question, and could be guessed easily.

Anyway, here is the question:

$a,b,c$ are positive integers such that 

$$\dfrac{bc + 1}{abc + a + c} = \frac{11}{43}$$

Then what are the possible values of $abc$?

Solution.

We can find all solutions. In fact there is a unique solution.

Take the reciprocal and do some minor algebra to get

$$a + \dfrac{c}{bc + 1} = \dfrac{43}{11} = 3 + \dfrac{10}{11}$$ 

Since $\frac{c}{bc + 1} \lt 1$, we must have that $a=3$ and $\frac{c}{bc+1} = \frac{10}{11}$.

Taking reciprocal again gives

$$b + \dfrac{1}{c} = \dfrac{11}{10} = 1 + \dfrac{1}{10}$$

$c = 1$ is not possible (LHS is an integer, while RHS is not). Thus $\frac{1}{c} \lt 1$ and so

$b = 1$ and $c=10$

Thus $(a,b,c) = (3,1,10)$ is the unique solution and $abc = 30$.

Powers of 2 series convergence from Peter Winkler

 Here is a cute problem from Peter Winkler.

The series below converges in the interval $[0,1)$

$$ x - x^2 + x^4 - x^8 + \dots + (-1)^n x^{2^n} + \dots $$

For $x \in [0, 1)$, call the value $f(x)$.

The question is, does the limit 

$$ \lim_{x \to 1-} f(x) $$

exist?

Solution.

A proof by Noam Elkies goes as follows (rephrased, not verbatim):

We can show that for $x \in [0,1)$, 

$$f(x) + f(x^2) = x $$

and so (by a repeated application of the above)

$$ f(x) = x - x^2 + f(x^4)$$

By the first identity, if the limit exists, it must be $\frac{1}{2}$.

Now for $0 \lt x \lt 1$ we must have that (using the second identity above)

$$ f(x) \gt f(x^4) \gt f(x^{16}) \gt \dots \gt f(x^{4^n}) \gt \dots$$

Thus if there was some $c$ such that $f(c) \gt \frac{1}{2}$, we must have that

$$f(c^{4^{-n}}) \gt f(c) \gt \frac{1}{2}$$

And since $c^{4^{-n}} \to 1$ as $n \to \infty$, the limit cannot be $\frac{1}{2}$ if $f(c) \gt \frac{1}{2}$.

A quick computation (wrote python code) upto $15$ terms shows that $f(0.9999) \gt 0.5006$.

7 rooks and 12x12 chessboard, An IMOQ 2022 problem

 Seems like there is a new exam for qualification to the regional math olympiads in India now. It is called IMOQ and is a set of fill in the blank questions, the answers typically being an integer between 0 and 99.

Here is an interesting problem I came across, where none of the folks claiming to solve it had a valid proof (though the final answer was actually correct).

The problem was:

You have a 12x12 chessboard. Find the smallest $N$ such that no matter how you place $N$ rooks on the board, one can find 7 rooks which don't attack each other.

We can easily show that $N=72$ is a lower-bound. Fill up 6 rows completely with the 72 rooks, and no matter how you pick 7 rooks, two will attack each other.

Most of the solvers got this part right, and then claimed that $N=73$ is the answer, claiming if you put the 73rd rook in the above configuration, then you can find 7. This is an invalid proof, as you have to show that, no matter which configuration you choose for the 73, you can find 7.

Below is the proof I had.

Claim: For an $n x n$ chessboard, if we place at least $nk + 1$ rooks ($0 \le k \le n-1$), then there will necessarily be atleast $k+1$ rooks that don't attack each other.

We prove by induction on $k$.

$k=0$ is easily seen.

Now suppose we are given a configuration of $nk+1$ in an $n x n$ chessboard, with $1 \le k \le n-1$

Consider a row with the minimum number of rooks. This number must be $\le \dfrac{nk+1}{n}$, and thus must be $\le k$. Without loss of generality we can assume this is the first row, and we can also assume there is a rook in the square corresponding to the first column and first row (just permute the rows and columns as needed).

Now we remove the first row and first column, resulting in a configuration of the $(n-1) x (n-1)$ chessboard, and if we can show that the resulting configuration has at least $k$ rooks, we are done, as the rook in the top left corner will not attack any of these $k$ rooks.

The maximum amounts of rooks that we remove are $k + n - 1$: $k$ rooks from the first row, and at most $n-1$ other rooks from the first column.

Thus the $(n-1)x(n-1)$ chessboard has at least $$nk + 1 - (k + n - 1) = (n-1)k -(n-1) + 1 = (n-1)(k-1)+1$$ rooks.

Now $ 0 \le k-1 \le n-2$ and so by the induction assumption, this has at least $k$ rooks that don't attack other.

Note that this proof also gives an algorithm to find $k+1$ such rooks.

Sqrt and square free

Given a positive integer $n$. Show that

$$ n = \sum_{k} \left[\sqrt{\dfrac{n}{k}}\right]$$

where $k$ runs through the square free numbers, $1 \le k \le n$ and $[x]$ is the integer part of $x$.

Solution:

Simpler solution (earlier complicated solution is still there below)

Every number can be written uniquely in the form $u^2 q$ where $q$ is square free.

Given a square free $q$, there are $[\sqrt{\frac{n}{q}}]$ numbers of the form $u^2q$ which are $\le n$ 

Now just add up for each squarefree $q$.

Complicated solution:

If $\lambda$ is the Lioville function: $\lambda(p^a) = (-1)^a$  for prime powers and $\lambda(ab) = \lambda(a)\lambda(b)$ for co-prime $a,b$

then using dirichlet convolution we have the identity $\lambda * 1 = s$, where $s$ is the indicator function for perfect squares. 

We can also show that the dirichlet inverse of $\lambda$ is $\mu^2$, where $\mu$ is the mobius function.

Thus we have $1 = \lambda^{-1} * s$

Which gives (using summation identities involving dirichlet convolution)

$$ n  = \sum_{1 \le k \le n} \mu^2(k) S(n/k)$$

where $S(n/k)$ counts the number of perfects squares $ \le \frac{n}{k}$, which is in fact $\left[\sqrt{\frac{n}{k}}\right]$.

$\mu(k)$ is non-zero only for the square free numbers, and that proves the identity,

Real root of $1=x+x^3$, powers and rational sums

 Let $a$ be the unique real number that satisfies $1=a+a^3$.

Let $S$ be any non-empty finite subset of the powers of $a$, i.e. $S \subset\{a^1, a^2, a^3, \dots, \}$.

A ) Show that if the sum of elements of $S$ is rational, then it is either $1$ or $2$.

B) Find two subsets which sum to $1$ and $2$ respectively.

C) Show that there are infinite such subsets.

.

.

.

The polynomial $P(x) = x^3 + x + 1$ is irreducible over integers by Crohn's criteria, since $P(2) = 11$. This implies $P(-x)$ is irreducible too. This basically means that $a$ cannot be the root of either a linear or a quadratic equation with integer coefficients. This easily implies the same for rational coefficients. 

We will state the above explicitly as Lemmas.

Lemma 1: $a$ is irrational

Lemma 2: $a$ cannot be a root of $Ax^2 + Bx + C = 0$, where $A,B,C$ are integers.

Note: we can prove the above lemmas in a more elementary fashion but will not do that here.

To prove A)

Notice that $\sum_{n=1}^{\infty} a^n = \frac{a}{1-a} = \frac{a}{a^3} = \frac{1}{a^2}$. 

We can show that $a \gt \frac{1}{\sqrt{3}}$ by using the fact that $x^3 + x -1$ is monotonic. Thus any finite sum of powers of $a$ is $\lt 3$.

 Notice $a^2 = \frac{1}{a} - 1$. This allows us to make the claim that:

Proposition: For any integer $n \ge 0$, there exist integers $A_n, B_n, C_n$ such that

$$ a^n = A_n \cdot a + \frac{B_n}{a} + C_n$$

Proof: Easily proven by induction, using $a^2  = \frac{1}{a} - 1$.

Thus the sum of any finite powers of $a$ can be written as

$$A \cdot a + \frac{B}{a}  + C$$ 

for some integers $A,B,C$.

If that is rational, by Lemmas 1 and 2, we must have that $A = B = 0$, and thus the sum must be $C$ which is an integer.

Since $0 \lt C \lt 3$, it must be either $1$ or $2$.

Part B)

$$1 = a + a^3$$

$$2 = a + a^2 + a^3 + a^4 + a^5 + a^6 + a^7$$

Part C)

If $$N = a^{j_1} + a^{j_2} + \dots + a^{j_k}$$

with $j_k$ being the largest, rewrite as

$$N = a^{j_1} + a^{j_2} + \dots + a^{j_k}(a + a^3)  = a^{j_1} + \dots + a^{j_{k-1}} + a^{1+j_k} + a^{3+ j_{k}}$$

to get a representation with $k+1$ terms instead of $k$. Repeat to get infinite representations.

Writing 1 as the sum of golden ratio reciprocal powers

 Let $\varphi = \frac{1+\sqrt{5}}{2}$ be the golden ratio.

For every positive integer $n \ge 2$, show that there is exactly one way to write $1$ as the sum

$$ \sum_{i=1}^{n} \varphi^{-a_i}$$

where $a_1 \lt a_2 \lt \cdots \lt a_n$ are $n$ distinct positive integers

For eg:

$$ 1 = \varphi^{-1} + \varphi^{-2} = \varphi^{-1} + \varphi^{-3} + \varphi^{-4}$$

We will start with a few Lemmas.

Let $t = \varphi^{-1}$ and we will use powers of $t$ for convenience.

Lemma 0: $t^{k} = t^{k+1} + t^{k+2}, \forall k \ge 0$

Proof: Easy to see.  

Lemma 1: For every $n \ge 1$, 

$$1 = t^{2n} + \sum_{j=1}^{n} t^{2j-1} $$

Proof: 

We get 

$$t^{2n} + \sum_{j=1}^{n} t^{2j-1} = t^{2n} + t^{2n-1} + \sum_{j=1}^{n-1} t^{2j-1}$$

$$ = t^{2n-2} + \sum_{j=1}^{n-1} t^{2j-1}$$

(by applying lemma 0)

By using induction, and $1 =  t + t^2$, we are done.

Lemma 2: If $a_1 \lt a_2 \lt a_3 \cdots \lt a_n$ are $n$ distinct positive integers such that $a_{i} + 1 \lt a_{i+1}, 1 \le i \lt n$  (i.e, there aren't consecutive numbers in the $a_i$), then

$$ \sum_{j=1}^{n} t^{a_j} \lt 1$$

Proof:

If $a_m \in \{2k-1, 2k\}$ then $t^{a_m} \le t^{2k-1}$

Since no $a_i$s are consecutive

$$\sum_{j=1}^{n} t^{a_j} \lt \sum_{k=1}^{\infty} t^{2k-1} = 1$$

Now for the main result.

Proposition: Given a positive integer $n \ge 2$, there is exactly one way to write $1$ as the sum 

$$ 1 = \sum_{j=1}^{n} t^{a_j}$$

where $a_1 \lt a_2 \cdots \lt a_n$ are $n$ distinct positive integers.

Proof:

By Lemma 1, we see that there is at least one way.

For $n=2$ it is easy to see the uniqueness.

We now prove by induction on $n$.

 Assume uniqueness for $n$.

Now suppose

$$ 1 = \sum_{j=1}^{n+1} t^{a_j}$$

with $a_1 \lt a_2 \lt \cdots \lt a_{n+1}$.

By Lemma 2, there is some $i$ such that $a_i + 1 = a_{i+1}$.

Let $i$ be the least $i$ such that $a_{i} + 1 = a_{i + 1}$. Note that $i \gt 1$ (otherwise the whole sum = $t + t^2 + \dots \gt 1$).

By Lemma 0, we have that $t^{a_i - 1} = t^{a_i} + t^{a_{i+1}}$. Since $i$ was the least $i$, there is no $j$ such that $a_j = a_i - 1$.

Thus, we now have a representation using $n$ terms

$$a_1 \lt a_2 \lt a_{i-1} \lt a_i - 1 \lt a_{i+2} \lt \cdots \lt a_{n+1}$$

By induction hypothesis this representation is unique, which must be as written in Lemma 1 and must be the same as 

$$ 1 \lt 3 \lt 5 \cdots \lt 2n-3 \lt 2n-2$$

If the newly created term $a_i - 1$ is one of $1,3,5, \dots, 2n-3$, then we must have $a_{i+1} = a_{i+2}$ which is not possible.

Hence we see that the original representation using $n+1$ terms be

$$ 1 \lt 3 \lt 5 \lt \cdots \lt 2n-3 \lt 2n-1 \lt 2n$$

Nice defense by Arvind Ranasaria

 In the recently concluded Willingdon Swiss pairs tournament in Bombay, my partner from Seattle made a very nice defense.

Arvind had opened 2S (red vs white) with the spades being AKQT9x, and his LHO eventually ended up in 3NT.

I was on lead with 642 of spades and led the 2 of spades.

Dummy showed up with a void and declarer had J8xx.

Arvind smoothly played the SK and followed with the ST!

Declarer now had to guess whether I was leading from Qxx or not. If I had the Q, the correct play is to duck. If not, playing the J was the winning play.

Declarer guessed wrong, and was -2.

Very nice defense!

A cloning problem from a reddit math contest

 A cute problem from reddit.

You have $2n$ people standing in an infinite row at spots say $1,2,3,..,2n$ (one person at each spot). A scientist performs the following steps repeatedly.

Clone every person on the row, and move the clones one position the right i.e. if there were $x$ people at position $k$, you create $x$ clones and place them at position $k+1$. Note that this is done for every position in parallel (so no moving clones twice etc). Previously empty positions could see folks being moved there.

After $2n-1$ repeats of the above steps, how many people will be there at position $n$?

Scroll down for a solution.

.

.

.

Suppose there are $p_j$ people at position $j$ ($j >= 1$).

Then the steps is basically replacing $p_{k+1}$ with $p_{k+1} + p_{k}$

This looks ripe for matrices, the steps are basically a linear transformation, but the matrix is large, of size $4n-1$ or so.

There is another way to look at this: polynomials!

Let $$f(z) = \sum_{n=1}^{\infty} p_n z^n$$

(Even though there is infinity, it is still a finite polynomial as all $p_i = 0$ after a certain point)

Then the steps are basically replacing $f(z)$ by $f(z) (z+1)$

Initially $$f(z) = z + z^2 + \dots + z^{2n}$$

After $2n-1$ steps we get

$$(z+z^2 +\dots +z^{2n})(1+z)^{2n-1} = $$

$$(z + z^2 + \dots + z^{2n}) (\sum_{r=0}^{2n-1} \binom{2n-1}{r} z^r)$$

(using binomial theorem on $(1+z)^{2n-1}$)

The number of people in row $n$ is coefficient of $z^n$ and that comes out to be

$$\sum_{r=0}^{n} \binom{2n-1}{r} = \frac{2^{2n-1}}{2} = 2^{2n-2}$$

(using $\binom{2n-1}{r} = \binom{2n-1}{2n-1-r}$ and adding them up to get $2^{2n-1}$)