Replicating Amoebas

 This is a puzzle from Peter Winkler who himself got it from some field medalist apparently.

You have an amoeba at $(0,0)$. An amoeba can replicate by splitting itself,  and placing them one to the right and one above.

So if an amoeba is at $(x,y)$ after the replication of that, there will be no amoeba at $(x,y)$, one at $(x+1, y)$ and one at $(x, y+1)$.

This replication can only happen if the two target spots are empty. Otherwise the amoeba will not replicate. 

For eg starting with $(0,0)$ consider the following.

A split, now we have $(1,0)$ and $(0,1)$. 

The $(0,1)$ splits, now we have $(1,0), (1,1), (0,2)$.

Now if the $(1,0)$ wants to split, it cannot, because one of the targets $(1,1)$ is occupied.

Ok now for the puzzle.

You start with one amoeba at $(0,0)$. 

How many replications do we need to clear the square (including the inside of it) $(0,0), (2,0), (2,2), (0,2)$ of amoebas?

Solution.

.

.

.

.

.

The answer is, it is impossible to clear that grid!

We come up with an invariant. Give weight $1$ to the initial amoeba. If an amoeba of weight $w$ splits, give weights $\frac{w}{2}$ to each of its clones. Thus the total weight of amoebas is preserved.

Now the weights are non-positive powers of $2$ and given the location of the amoeba, you can actually determine its weight.

The weights look something like this ($(0,0)$ is bottom left of matrix)

$$\begin{matrix} \vdots & \vdots & \vdots & \vdots \\ \frac{1}{8} & \frac{1}{16} & \frac{1}{32} & \frac{1}{64} &\dots \\ \frac{1}{4} & \frac{1}{8} & \frac{1}{16} & \frac{1}{32}  & \dots \\ \frac{1}{2} & \frac{1}{4} & \frac{1}{8} & \frac{1}{16} & \dots \\ 1 & \frac{1}{2} & \frac{1}{4} & \frac{1}{8} & \dots \end{matrix}$$

Now the sum of all the weights in the grid of our interest  is $$ 1 + 2 \times \frac{1}{2} + 3 \times \frac{1}{4} + 2 \times \frac{1}{8}  + \frac{1}{16} = 3 \frac{1}{16}$$

The sum of weights of all the possible spaces is $S + \frac{S}{2} + \frac{S}{4} + \dots = S^2 $ where $S$ is the sum of the weights of the bottom row. 

It is easily seen that $S=2$, so the whole infinite grid sum is $4$.

Thus the sum of weights outside our grid of interest is no more than $4 - 3\frac{1}{16} < 1$.

Thus it is impossible to clear that grid, starting with a single amoeba at $(0,0)$, of initial weight $1$: there has to be some amoeba inside the grid to preserve the total weight of $1$.

A generalization of sum of squares

 Let $A_1, A_2 \dots A_n$ be $n$ points in the 2D plane, with centroid $M$.

Show that for any point $P$ in the plane

$$ \sum_{i = 1}^{n} PA_{i}^2 = n PM^2  + \sum_{i=1}^{n} MA_{i}^2$$

Bonus: Given a magic fairy that tells you the sum of squares of distances of any point $P$ to $A_1, A_2, \dots, A_m$ where you don't know $m$ or the $A_i$, show that you can find $m$ in a finite number of queries to the magic fairy.

Solution

.

.

.

.

.

Surprisingly this has an easy proof using complex numbers!

Let $a_1, a_2, \dots, a_n$ be complex numbers that sum to $0$,

Then we have that for any complex number $z$,

$$\sum_{i=1}^{n} |z-a_i|^2 = \sum_{i=1}^{n} (z-a)\overline{(z-a)} = $$

$$ \sum_{i=1}^{n} (z\overline{z} - z\overline{a_i} -\overline{z}a_i + a_i\overline{a_i}) = $$

$$ n z \overline{z} + \sum_{i=1}^{n} a_i\overline{a_i}  = n |z|^2 + \sum_{i=1}^{n} |a_i|^2$$

This gives us the identity we seek. The centroid $M$ corresponds to $0$, the sum of $a_i$.

The bonus puzzle solution follows along the lines of the previous guessing puzzle, and I will leave it to you.

Guessing the area from sum of squares of distances

 There is an equilateral triangle $ABC$ in the 2D plane. You don't know where it is, but have access to a magical fairy that, given a point $P$ in the same plane, will give you the value of $$f(P) = |PA|^2 + |PB|^2 + |PC|^2$$ i.e. the sum of squares of distances from $P$ to $A,B,C$ (henceforth we will drop the absolute sign)

i) Can you find out the area of triangle $ABC$ using only a finite number of queries to the fairy?

ii) Can you find the minimum number of queries you need to (and are sufficient) to guess the area?

iii) Can you find the locations of the three vertices?

Solution

.

.

.

.

.

Part i)

In a previous post we showed the following:

For any triangle $ABC$ with centroid $M$ and any point $P$ in the same plane

$$ PA^2 + PB^2 + PC^2 = 3 PM^2 + AM^2 + BM^2 + CM^2$$

(Can easily be proven using complex numbers too, if required).

i.e we have $$f(P) = 3 PM^2 + S$$

where $S$ is a constant, independent of $P$ (and is actually a constant times the area of $ABC$, for equilateral $ABC$).

Now pick points $X, Y$ (say $(0,0), (1,0)$) and query the fairy for $X$ and $Y$.

We have that $$f(X) - f(Y) = 3(XM^2 - YM^2)$$

i.e $M$ lies on the locus of points $Q$ such that $$QX^2 - QY^2 = k$$

$k$ is a constant.

By simple co-ordinate geometry, this actually can easily be seen to be a line perpendicular to $XY$ (extended, if needed).

Thus using two points, we narrow down $M$, the centroid of $ABC$ to a straight line. With another point $Z$ (say $(0, 1)$), we get another line, and take the intersection of the two lines.

Once we have the location of $M$, we can compute $XM^2$ directly, and then use the already obtained $f(X)$ to compute the area of the equilateral triangle $ABC$, using

$$ AM^2 + BM^2 + CM^2 = f(X) - 3 XM^2$$

Thus three queries are sufficient. 

Part ii)

Three queries are also necessary.

Suppose two were enough, (say X and Y), then as before $M$ lies on a line perpendicular to $XY$. Now if $M$ were the actual point, then the reflection $M'$ of $M$ on $XY$ gives the same $f(X)$ and $f(Y)$. Thus two queries are not enough.

Part iii)

Pinpointing the vertices is impossible! Any rotation of the $ABC$ around the centroid gives the same $f(P)$ values.

 

An unexpected approach to a quadratic system of equations

Positive reals $a,b,c$ satisfy

$$ a^2 + b^2  + ab = 121$$

$$b^2 + c^2 + bc = 169$$

$$ c^2 + a^2 + ca = 400$$

What is the value of $ab + bc + ca$?

.

.

.

.

.

.

This can be solved using geometry!

Consider triangle $OAB$ with $OA = a$ and $OB = b$ and $\angle{AOB} = 120^{\circ}$.

Using cosine rule, $AB^2 = a^2 + b^2 - 2ab \cos(120^{\circ}) = a^2 + b^2 + ab$. Thus $AB = 11$.

Area of triangle $AOB$ = $\frac{1}{2} ab \sin(120^{\circ}) = \frac{\sqrt{3}}{4} ab$

Now add point $C$ such that $OC = c$ and $\angle{AOC} = \angle{COB} = 120^{\circ}$.

We thus have a triangle $ABC$ with sides $AB = 11, BC = 13, AC = 20$ and area  (by adding up areas of $AOB, AOC, BOC$

 $$\frac{\sqrt{3}}{4} (ab + bc + ca)$$

By Heron's formula, since the sides are known, we get area $=66$.

This gives $$ab + bc + ca = 88 \sqrt{3}$$

A magic trick with 2 magicians and 3 spectators

 Show that the following magic trick is possible.

Two magicians call three spectators and have them sit on three chairs. One magician (call them B), goes out of the room. The other magician (A) spreads out 27 cards in front of the spectators, and each is asked to take a card of their choice. 

Once the spectators choose, A points to a card from the remaining 24 and has the spectators add it to their set of three cards (i.e. A does not touch that card). The spectators are allowed to shuffle the four cards. B is then called back and one of the spectators hands B the four shuffled cards. Looking at the 4 cards, B now announces which spectator chose which card.

.

.

.

.

.

Solution:

Lets label the chairs (and hence the spectators) 1,2,3. The magicians agree upon this before hand.

There are $6 \binom{27}{3} =17550$ possibilities for spectators cards. The number of possibilities for the 4 cards handed to B is $\binom{27}{4} = 17550$. Thus we need to find a pairing for each possibility of the spectator's pick to a 4 element superset.

Now look at this as a bipartite graph.

One vertex set is the set of spectator possibilities (call it $S$) and the other is the set of 4 elements subsets (call if $F$).

Each spectator possibility $s \in S$ has exactly 24 neighbours in $F$. Each 4 element set $f \in F$ has exactly $6\binom{4}{3} = 24$ neighbours in the spectator set $S$.

This is a regular bi-partite graph and by a simple application of Hall's theorem, has a perfect matching. 

A brief sketch is:

If $L$ is a subset of $S$ and $N(L) \subset F$ is the set of neighbours of $L$, then the number of edges in the induced subgraph of $G(L, N(L))$ is $24|L|$. Since the degree of each vertex of $F$ is 24, the degree of the $F$ vertices in $G(L, N(L))$ is at most $24$. Thus we must have that $24 |N(L)| \ge 24 |L|$ and thus $|N(L)| \ge |L|$, satisfying the condition of hall's theorem. 

Cute problem from Moldova Math Olympiad

 $a,b$ are real numbers that satisfy

$$a^3 - 3ab^2 = 29$$

$$b^3 - 3a^2b = 34$$

What is the value of $a^2 + b^2$?

Meta puzzle: Which year did this problem appear?

.

.

.

.

Solution:

The solution becomes simple if you think complex!

$$(a+ib)^3 = (a^3 - 3ab^2) - i(b^3 - 3a^2b)$$

Thus $$(a+ib)^3 = 29 - 34i$$

And so $$(a^2 + b^2)^3 = 29^2 + 34^2 = 1997$$

and

$$a^2 + b^2 = \sqrt[3]{1997}$$

Note that we basically have the identity

$$(a^2 + b^2)^3 = (a^3 - 3ab^2)^2 + (b^3 - 3a^2b)^2$$

Sum of consecutive positive integers

 A classic.

Show that integers of the form $2^m$ are the only positive integers that cannot be written as the sum of two or more consecutive positive integers.

.

.

.

.

Solution:

Suppose we try to write $X$ as the sum of consecutive positive integers.

$$X =  a + (a+1) + \dots + (a+n)$$ 

i.e.

$$2X = (n+2a)(n+1)$$

Note, since we need two or more, we must have that $n > 0$, and $n + 2a > n+1$.

Note that $n+2a$ and $n+1$ are of different parities.

If $X$ was a power of $2$, then the only way we can factor $2X$ into factors of different parities is if one of them is $1$. But we have $n+1 \ge 2$. So, powers of $2$ cannot be written in that form.

For any other $X  = 2^m Y$ ($Y > 1$, odd), we can pick the factors to be $2^{m+1}$ and $Y$ and compute the appropriate $n$ and $a$.

Integral perimeter and Hypotenuse problem

 The IOQM seems to have some nice problems, though the solutions given by the many of the Indian book authors/coaching classes are sometimes wrong and/or lacking for the harder problems.

Here is a problem where one of the books got the wrong answer, even though the problem isn't hard.

The altitude dropped on the hypotenuse of a right triangle is the integer $12$. Given that the hypotenuse and the perimeter of the triangle are integers too, what is the smallest possible length of the hypotenuse?

.

.

.

Solution:

If $c$ is the hypotenuse (and $a,b$ are the legs), then we have that $12 c = ab$ (by equating the area of the triangle). $a+b+c$ and $c$ are both integers.

We also have that $(a+b)^2$ is a perfect square.

$$(a+b)^2 = a^2 + b^2 + 2ab = c^2 + 24c$$

By imagining a semicircle of diameter $c$, we can easily see that $c \ge 24$, and note that for any $c \ge 24$, a right triangle exists.

Now $c^2 + 24c$ has to a perfect square, and $c=25$ is the smallest that works.

The book had the answer as $24$ which is wrong.

Distinct Remainders, a problem from IOQM.

 Here is a cute problem for IOQM.

What is the smallest $n$ such that $1^4, 2^4, \dots , 14^4$ all leave distinct remainders when divided by $n$?

Solution.

Now $x^4 - y^4$ = $(x-y)(x+y)(x^2+y^2)$, we want this to be non-zero $\mod n$.

If $n \lt 28$, then we can find distinct $x, y \le 14$ such tht $x+y = n$.

We also have that $(13+1)(13-1)$ is divisible by $28$.

$29 = 5^2 + 2^2$

$(11+1)(11-1)$ is divisible by $30$.

Now consider $n=31$. For $31$ to not be a candidate we must have that $x^2+y^2$ is divisible by $31$.

But, it is well known that if $p$ is a prime of the form $4m+3$, and it divides $x^2+y^2$, then it divides $x$ and $y$.

Thus $31$ is our answer.

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 IOQM 2022 problem

 Seems like there is a new exam for qualification to the regional math olympiads in India now. It is called IOQM 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.