Relocating a Hydra

There are infinite rooms, numbered with the integers.

 There is initially a single hydra in room $0$. Each room can hold any number of hydras.

At any time, you can either:

i) Cut off the head of one of the hydras in room $n$, and that results in two hydra spawning, one in room $n-1$ and one in room $n+1$. 

ii) If there are hydras in both room $n-1$ and room $n+1$, you can cut off the heads of one hydra each in both those rooms, and that results in a single hydra spawning in room $n$.

Starting with one hydra in room $0$, with some  sequence of the above head-cuts, can you relocate the hydras to some other room $R$? (i.e. you end up with some number of hydras only in room $R$ and nowhere else). 

What are the possible values of this $R$?

Scroll down for a solution.

.

.

.

.

.

Suppose there are $a_n$ hydra in room $n$.

Consider the function

$$f(z) = \sum a_n z^n $$

Now by chopping off a hydra head in room $n$, the change in the value of $f$ is

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

The other step (which is basically a reverse of the other) results in a change of 

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

Now if we pick $z = -w$ where $w$ is the cube root of unity, we see that $f(-w)$ is unchanged!

Initially $f(-w) = 1$. If we manage to get exactly r hydras in room $R$ (and no other hydras), then we must have that

$$1 = r (-w)^R$$

This implies $r = 1$ and $R = 6k$.

Thus it is necessary that $R$ must be a multiple of $6$.

It is also sufficient!

All we need to demonstrate is that we can relocated the hydra to room 6.

Now consider the transformation (which shows the state of the rooms -1 to 7)

$$\begin{aligned}& \dots 0 1 0 0 0 0 0 0 \dots \\& \dots 1 0 1 0 0 0 0 0 \dots \\& \dots 1 1 0 1 0 0 0 0 \dots \\& \dots 1 1 1 0 1 0 0 0 \dots \\& \dots 0 2 0 0 1 0 0 0 \dots\end{aligned}$$

Now the steps above are reversible, can be done in any direction starting from anywhere where there is a hydra.

So we apply the above set of steps (call it the 1 to 2-1 step) to the single hydra above to get (note we are no longer showing the room -1 and room 7)

$$ \dots 2 0 0  2 0 0 1\dots $$

Now apply the 1 to 2-1 step in the left direction to the single hydra to get

$$  \dots 2 0 0 3 0 0 2 \dots$$

Now we apply the reverse of the 1 to 2-1 steps (thus effectively changing a 2-1 to 1) to get

$$ \dots 1 0 0 2 0 0 2 \dots $$

And again to get

$$ \dots 0 0 0 1 0 0 2  \dots $$

And again

$$ \dots  0 0 0 0 0 0  1  \dots $$

Which gives us the relocated hydra in room 6, and we are done!

Infinite Version of Fox in a Hole

 The fox-in-a hole is a classic puzzle where there is a fox in one of 5 holes along the x-axis. Every morning you can check a hole for the fox. If you find it, you win. Otherwise that evening the fox moves to an adjacent hole. You can check any hole the next morning and so on. The goal is to catch the fox, irrespective of where it starts from.

An infinite version is as follows.

There are holes along the x-axis on the points $1,2, \dots$ i.e the positive integers. There is a fox in some hole somewhere. Your goal is to catch it. 

Everyday you can check any hole in the morning. If you miss, that evening the fox moves to an adjacent hole (the only hole adjacent to hole 1 is hole 2). You check again the next morning and if you miss the fox moves in the evening and so on.

Can you eventually catch the fox?

Scroll down for a solution.

.

.

.

.

.

Solution:

It is enough if we can solve a finite version of this!

$\textbf{Infinite from finite}$

Suppose you knew the fox was at hole $ \leq N$ and that there was an algorithm to catch it within $f(N)$ days if that were so. If we run the algorithm for $f(N)$ days and don't catch the fox, then we know it started at a hole $> N$. 

We can use this to solve the infinite version as follows:

Consider the sequence $x_n$, defined as $x_1 = 1$ and

$$x_{n+1} = f(x_1) + f(x_2) + \dots + f(x_n) + n$$

Clearly $x_{n+1} - \sum_{i=1}^{n} f(x_i) \to \infty$ and so, given any $M > 0$, eventually $$x_n > M + f(x_1) + f(x_2) + \dots + f(x_{n-1})$$

Our infinite version strategy is now:

Assume the fox is at a hole $\leq x_1$. Run the finite algorithm for $x_1$. If we don't catch it, assume it is at hole $\leq x_2$ and run the finite algorithm for $x_2$ and so on.

If the fox started at hole $M$ initially, then after $n$ steps of the above, the fox will at max be at the hole $M + f(x_1) + \dots + f(x_n)$.

Thus eventually, one of our $x_K$ will be greater than the current hole of the fox, and we will catch it, when we run the finite algorithm for $x_K$.

$\textbf{Finite Algorithm}$

A finite algorithm for $\leq N$ is as follows:

Assume the fox started at an even spot and make a sweep down from $2[(N+1)/2]$. If we don't catch it, we know it started at an odd number and is at a hole $\leq N + 2[(N+1)/2]$. We can now make another sweep down, starting with a high enough hole numbered with the correct parity.

This gives $f(N) = O(N)$, and we eventually catch the fox in $O(M)$ days, where $M$ is the initial hole of the fox.

Oddness of Binomial Coefficients

 There are well known theorems like Lucas' or Kummer's which allow one to figure out exactly which binomial coefficients $\binom{n}{k}$ are odd.

The goal of this (slightly open ended) puzzle is to not use these theorems and still come up with a characterization of the $n,k$ for which $\binom{n}{k}$ is an odd number.

Scroll down for one simple "elementary" way.

.

.

.

.

.

We prove the following:

$\textbf{Claim:}$ Given an $n = \sum 2^{e_i}, e_i \text{ distinct} $ , then we have that $\binom{n}{k}$ is odd iff $k$ is the sum of some subset of the $2^{e_i}$. i.e $k$ is written only using the "set" bits of $n$. The empty set corresponds to $k = 0$.

$\textbf{Proof:}$

Consider polynomials where the coefficients are either $0$ (for even) or $1$ for odd, with the rule that $1 + 1 = 0$.

So we have $1 - 777x$ being equivalent to $1 + x$, because negative of odd is still odd etc.

And $13 + 200x + 999x^2 $ is equivalent to $1 + x^2$ since $200$ becomes $0$ and even times anything is even and so evens act like zero.

[In advanced terms we are working over $GF(2)$]

Now consider $(1 + x)^2 = 1 + 2x + x^2 = 1 + x^2$

Similarly $$(1  + x)^4 = ((1 + x)^2)^2 = (1 + x^2)^2 = 1 + x^4$$

Thus by induction we see that

$$(1 + x)^{2^m} = 1 + x^{2^m}$$

Thus if $n = \sum 2^{e_i}$ (i.e we look at the binary representation of $n$) then

$$(1 + x)^n = \prod (1 + x)^{2^{e_i}} = \prod \left(1 + x^{2^{e_i}}\right)$$

Now

$$\prod \left(1 + x^{2^{e_i}}\right) = \sum x^{m_i}$$

where $m_i$ are exactly the numbers which can be written as the sum of some subset of $2^{e_i}$. Since this gives a binary representation of $m_i$, the representation is unique and the coefficient is $1$.

This proves the above claim.

$\textbf{Additional Remark:}$ This method also works for an arbitrary prime $p$ and we have the following:

$\textbf{Claim:}$ $\binom{n}{k}$ is not divisible by $p$ iff each digit of $k$ in base-$p$ is $\leq$ the corresponding digit in $n$ (in base-$p$).

Note that the characterization we got earlier for $p=2$ is equivalent to this.

Sum of Large and Small divisors of 24n + 1

 Suppose $N = 24n + 1$ is a positive integer, which is not a perfect square. ($n$ is also a positive integer).

A large divisor of $N$ is a divisor of $N$ which is $ > \sqrt{N}$.

A small divisor of $N$ is a divisor of $N$ which is $ < \sqrt{N}$.

Let $L$ be the sum of the large divisors of $N$ and let $S$ be the sum of the small divisors of $N$.

Show that $$ L = S  \mod 24$$ 

For eg, $145 = 29 \times 5$ has the divisors $1, 5, 29, 145$ and $145 + 29 = 6 = 1 + 5 \mod 24$.

Scroll down for a solution.

.

.

.

.

Solution:

Any number $a$ which is relatively prime to $24$ is of the form $a = 6m \pm 1$.

Now $$a^2 - 1 = 36m^2 \pm 12m = 12m (3m \pm 1) = 0 \mod 24$$

This is because $m(3m \pm 1)$ is an even number (either $m$ is even, or $3m \pm 1$ is).

Now since $N$ is not a perfect square, we can pair off the divisors of $N$ as $sl = N$ with $s$ being a small divisor and $l$ being a large divisor.

Note that both $s$ and $l$ are relative prime to $24$, with $sl = 1 \mod 24$.

Now $s^2 - sl =  1 - 1 = 0 \mod 24$, i.e $s(s-l) = 0 \mod 24$. Since $\gcd(s, 24) = 0$, we must have that $s = l \mod 24$.

Thus $\sum s = \sum l \mod 24$.

$\textbf{Additonal Remarks:}$ Similarly we can show that the sum of divisors of a number of the form $24 n - 1$ is divisible by $24$.

An Integral Limit from Berkeley Math Problems Book

The book "Berkeley Problems in Mathematics" contains some hardcore math problems which Berkeley had used for its Phd program clearing requirement in the 70s and 80s.

Here is a nice one from there.

Suppose $f:[0,1] \to \mathbb{R}$ is a continuous function. Find

$$\lim_{n \to \infty} n \int_{0}^{1} x^n f(x) dx$$

Scroll down for a couple of solutions:

.

.

.

.

$\textbf{Solution 1}:$

This is a "heavyweight" and uses the Weierstrass approximation theorem.

The approximation theorem says that any continuous function on a closed interval can be approximated as close as we want, using just polynomials.

We first begin with the observation that for any fixed $M$

$$\lim_{n \to \infty} n \int_{0}^{1} x^n x^M dx = \lim_{n \to \infty} \frac{n}{n + M + 1} = 1$$

This implies that, for any polynomial $P$ we have that

$$\lim_{n \to \infty} n \int_{0}^{1} x^n P(x)dx = P(1)$$

For ease of notation, let $$I(n,g) = n\int_{0}^{1} x^n g(x) dx$$

Now given our $f$ and an $\epsilon > 0 $, there is a polynomial $P_{\epsilon}$ such that $$|f(x) - P_{\epsilon}(x)| < \epsilon \quad \forall x \in [0,1]$$

i,e

$$-\epsilon + P_{\epsilon}(x)  \le f(x) \le \epsilon + P_{\epsilon}(x)$$

And thus we have

$$ I(n, -\epsilon) + I(n, P_{\epsilon}) \leq I(n,f) \leq I(n, \epsilon) + I(n, P_{\epsilon})$$

i.e.

$$ \frac{-n\epsilon}{n+1} + I(n, P_{\epsilon}) \leq I(n,f) \leq \frac{n\epsilon}{n+1} + I(n, P_{\epsilon})$$

Taking $n \to \infty$ we get

$$-\epsilon + P(1) \leq \liminf I(n,f) \leq \limsup I(n,f) \leq \epsilon + P(1)$$

And thus

$$-2\epsilon + f(1) \leq \liminf I(n,f) \leq \limsup I(n,f) \leq 2\epsilon + f(1)$$

SInce $\epsilon > 0$ was arbitrary, it follows that

$$\lim_{n \to \infty} I(n, f) = f(1)$$

$\textbf{Solution2:}$

This is more elementary. 

Let $$c_n = \frac{1}{\sqrt[n]{n}}$$

Note that $c_n < 1$, $\lim c_n = 1$ and $\lim c_n^{n+1} = 0$ 

Now since $f$ is continuous, we can bound $f(x)$ in some interval $[m,M]$ and thus

$$\frac{mn}{n+1} c_n^{n+1} \leq n\int_{0}^{c_n} x^n f(x)dx \leq \frac{Mn}{n+1}c_n^{n+1}$$

Thus $$\lim_{n \to \infty} n \int_{0}^{c_n} x^n f(x)dx = 0$$

Since $c_n \to 1$, given an $\epsilon > 0 $, for sufficiently large $n$, we have that

$$|f(x) - f(1)| < \epsilon \quad \forall x \in [c_n, 1]$$

And we get

$$ \frac{n(f(1) - \epsilon)}{n+1} (1 - c_n^{n+1}) \leq n\int_{c_n}^{1} x^n f(x) dx \leq \frac{n(f(1) + \epsilon)}{n+1}(1 - c_n^{n+1})$$ 

Taking $n \to \infty$ we get

$$f(1) - \epsilon \leq \liminf n \int_{c_n}^{1} x^n f(x)dx \leq \limsup n \int_{c_n}^{1} x^n f(x)dx \leq f(1) + \epsilon$$

Since $\epsilon$ was arbitrary it follows that

$$\lim_{n \to \infty} n \int_{c_n}^{1} x^n f(x) dx = f(1)$$

Thus 

$$\lim_{n \to \infty} n \int_{0}^{1} x^n f(x) dx = $$

$$\lim_{n \to \infty} n\int_{0}^{c_n} x^n f(x) dx + \lim_{n \to \infty} n\int_{c_n}^{1} x^n f(x)$$

$$ = 0 + f(1) = f(1)$$