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}$)

3 consecutive summing to 13

 You permute each of the digits $0, 1,2, \dots, 9$ and write them in a single row.

A) Show that no matter what the permutation, some 3 adjacent elements of the row sum to at least $13$.

B) Can you find a permutation where no 3 adjacent elements sum to more than $13$?

Scroll down for solution

.

.

A) Say the permutation is $x_0, x_1, \dots, x_9$.

Now one of $x_0$ or $x_9$ is $< 9$. We can assume $x_0 < 9$.

Let $S_i = x_i + x_{i+1} + x_{i+2}$.

Since $x_0 < 9$ we must have that $S_1 + S_4 + S_7 > 36$ and thus $\text{max} \{S_1, S_4, S_7\} > 12$.

B)  9 3 1 7 4 2 6 0 5 8

Peter Winkler's factorial problem

 A cute problem from Peter Winkler's collection of math puzzles.

$$ S = \{n! | 1 \leq n \le 100, n \in N\}$$

Can we remove a single element from $S$ such that the product of the elements of the resulting set is a perfect square?

Scroll down for a solution.

Product of elements of $S$ is

$$ P = 1!  2! \dots 99!  100! $$

Pair up terms $(2n-1)! (2n)! = ((2n-1)!)^2 2n$

Thus

$$P = (1!  3!  5! \dots 99!)^2 (2 . 4 . 6 \dots 100) $$

$$ =  (1!  3!  5! \dots 99!)^2 . 2^{50} . 50!$$

Thus removing $50!$ from $S$ will give us the desired result.

Volume of an n dimensional region

 What is the volume of the region in $R^n$ defined as follows

$$ V_n = \{(x_1,x_2, \dots, x_n) \in R^n | x_i \ge 0 \text{ and } \sum x_i \leq 1 \}$$

Scroll down for a clever proof (if you know the source, please comment)

.

.

.

Transform the space with $y_j = \sum_{1 \le i \le j} x_i$

This is a linear transformation that gives a new region defined as

$$ W_n = \{(y_1,y_2, \dots, y_n) \in R^n | 0 \le y_1 \le y_2 \le \dots \le y_n \le 1 \}$$

$W_n$ is just a subset of the hypercube $[0,1]^n$. The hypercube can be split into $n!$ regions of equal volume, each region corresponding to a sort order among the coordinates. $W_n$ is one of them.

Thus volume of $W_n$ is $\frac{1}{n!}$

Since the determinant of the linear transformation from $V_n$ to $W_n$ is $1$, the volume of $V_n$ is $\frac{1}{n!}$ too!

Exactly 80% success

A basketball player is practising free throws. Their current success rate (ratio of successful throws to total) is exactly 70% (or 0.7 in terms of ratio). After a few more throws that success rate is 90%. 

Show that at some point the success rate was exactly 80%.

Scroll down for a solution

.

Look at (misses, hits) on the integer lattice and x-y coordinate plane. If a miss occurs, we increment x coordinate, else we increment y coordinate.

Initially we are on the line $3y = 7x$ (70% hit rate) and reach the line $y = 9x$ (90% hit rate), crossing the line $y = 4x$ (80% hit rate) at some point, with some hit (i.e by incrementing the y-coordinate).,

The only way to cross the line $y = 4x$ vertically is to actually land on it first (every x = N line intersects y = 4x at (N, 4N) which is part of the integer lattice. Thus we achieve exactly 80%,

Product of three consecutive positive integers

 Can the product of three positive consecutive integers be a perfect square?

Scroll down for a solution

.

Assume the three integers are $n-1, n, n+1$ and that $(n-1)n(n+1)  = n(n^2-1)$ is a perfect square.

Since $n$ is relatively prime to both $n-1$ and $n+1$ (and hence their product $n^2-1$), we must have that $n^2-1$ is a perfect square too.

A problem from INMO

 In a triangle $ABC$ (sides $a,b,c$ opposite $A,B,C$), angle $A$ is twice $B$.

Show that $$a^2 = b(b+c)$$

Try not to use trigonometry if possible.

Scroll down for a solution

.

.

Let AD be the angular bisector of A, D lying on BC (might help to draw a figure).

Then by angular bisector theorem

$$BD = \frac{ac}{b+c}, DC = \frac{ab}{b+c}$$

BAD is isosceles, with $AD = BD$. Also triangle $ADC$ is similar to triangle $BAC$.

$AD/AB = DC/AC$ gives the result.

There are non-trigonometric proofs of the angular bisector theorem. For eg, prove for right angled triangles and use affine transform etc.

An accessible problem from Donald Newman's book

 "A problem Seminar" by Donald J Newman has many excellent problems which require math undergrad/grad knowledge. Below is one of the more accessible problems, solveable by a non-math person.

Each coin is either 10 or 9 grams. Given 4 such coins, find the weight of each using a scale (not a balance, a scale which gives the true weight) no more than 3 times.

Scroll down for a solution.

Suppose the coins are A,B,C,D.

Weigh A+B. It must be 19, otherwise it is trivial. Now weigh A+C. It must be 19, otherwise it is trivial.

Now we must have B=C. Now weigh B+C+D = 2B+D. This has the same parity (odd or even) as D. Thus we know D, which gives us B=C and then A.

Sum of squares of distances from vertices of a triangle

 If $ABC$ is a triangle with centroid $M$, and $P$ is any point then show that

$$PA^2 + PB^2 + PC^2 = 3PM^2 + \frac{1}{3}(AB^2 + BC^2 + AC^2)$$

Scroll down for a surprising solution.

Let $A_1,B_1, C_1$ be the midpoints of $BC, AC$ and $AB$ respectively.

Triangle $A_1B_1C_1$ (referred to as medial triangle of $ABC$) is similar to $ABC$ 

Using Appolonius theorem we get

$$PA^2 + PB^2 = 2(PC_1^2 + AC_1^2) = 2PC_1^2 + 2\frac{AB^2}{4}$$

$$PB^2 + PC^2 = 2(PA_1^2 + BA_1^2) = 2PA_1^2 + 2\frac{BC^2}{4}$$

$$PC^2 + PA^2 = 2(PB_1^2 + CB_1^2) = 2PB_1^2 + 2\frac{AC^2}{4}$$

Adding we get

$$PA^2 + PB^2 + PC^2 = PA_1^2 + PB_1^2 + PC_1^2 + \frac{AB^2}{4} + \frac{BC^2}{4} + \frac{AC^2}{4}$$

Thus if $A_nB_nC_n$ is the medial triangle of $A_{n-1}B_{n-1}C_{n-1}$  ($ABC = A_0 B_0C_0$) we have that

$$PA_{n-1}^2 + PB_{n-1}^2 + PC_{n-1}^2 = PA_n^2 + PB_n^2 + PC_n^2 + \frac{A_{n-1}B_{n-1}^2}{4} + \frac{B_{n-1}C_{n-1}^2}{4} + \frac{A_{n-1}C_{n-1}^2}{4}$$

 

We can easily show that $A_n, B_n, C_n$ all converge to $M$ ($A_nM = 3A_{n+1}M$), and observing the above is a telescoping series and that sides of a medial triangle are half the original triangle leads us 

$$PA^2 + PB^2 + PC^2 = 3PM^2 + \frac{AB^2 + BC^2 + AC^2}{4}(1 + \frac{1}{4} + \frac{1}{4^2} + \dots) $$

$$ = 3PM^2 + \frac{1}{3}(AB^2 + BC^2 + AC^2)$$

Allow opponents to make a mistake

 Long time no bridge hand!

Here is a puzzle.

You end up in 4S playing a team game (bidding and hands below, you are South).

IMPS  N/S	Partner ♠ xxx ♥ xxx ♦ Kxx ♣ Kxxx
	You ♠ QJT9xx ♥ Qx ♦ AQx ♣ AQ

W	N	E	S
			1S
P	2S	P	4S
P	P	P

LHO leads a low heart to RHO's Ace, who leads a heart back to LHO's King and a third heart which you ruff.

You have lost two hearts and have two spades to lose. Situation is hopeless. But, is there anything you can do? If you want to think about it, don't scroll further.

There are no legitimate chances and need a defensive error. If the spades divide Ax opposite Kx, you must hope to induce a first round duck and then crash the A and K together. How could you do that?

The opponents don't know you have a 6 card suit. Consider what might happen if you lead a diamond to dummy's K and then play a spade to the Q! (has to be the Q, no other card will do)

LHO looking at Ax of spades might very well duck, thinking you have KQT9x and have a guess in spades (they hope you go to dummy with CK next and play a spade to the K, setting up partner's J for the setting trick). If you indeed have KQT9x and they win the A from Ax, then you are forced to take the winning line of finessing their partner for the J.

It is a slim chance which is more likely to work against better opponents than not, but then what have you got to lose?

Parabola Arc Length

 Here is a problem with a cute solution.

Show that the arc length of the parabola $y = x^2$, from $(0,0)$ to $(1,1)$ is not greater than $1.5$.

Scroll down for a solution.

.

The arc length of $f(x)$ is given by the integral $\int \sqrt{1 + (f'(x))^2}$.

In our case, we are looking at

$$\int_{0}^{1} \sqrt{1 + 4x^2}$$

This can actually be evaluated without much trouble, and comes out to $\frac{1}{4}(\sqrt{5} + \sinh^{-1}(2)) \approx 1.47$

That is one way of trying to prove the $1.5$ upper bound but we will go for the "cute" proof with very little computations here.

Write 

$$\sqrt{1+4x^2} = \sqrt{(2x+1)^2 - 4x} = \sqrt{2x + 1 + 2\sqrt{x}} \sqrt{2x + 1 - 2\sqrt{x}}$$

Let $f(x) = \sqrt{2x + 1 + 2\sqrt{x}}$ and $g(x) = \sqrt{2x + 1 - 2\sqrt{x}}$

We apply the integral version of Cauchy-Schwartz inequality

$$ \int fg \le \sqrt{\int f^2} \sqrt{\int g^2}$$

To get

$$\int_{0}^{1} \sqrt{1+4x^2} \le \sqrt{\int_{0}^{1} (2x + 1 + 2\sqrt{x})} \sqrt{\int_{0}^{1} (2x + 1 -2\sqrt{x})}$$

$$ = \sqrt{1 + 1 + \frac{4}{3}}\sqrt{1 + 1 - \frac{4}{3}} = \sqrt{\frac{20}{9}} < \frac{3}{2}$$