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

FIbonacci criteria

 Show that $F$ is a fibonacci number if and only if $5F^2 \pm 4$ is a perfect square.

i.e if one of $5F^2 + 4$ or $5F^2 - 4$ is a perfect square, then $F$ is fibonacci and vice-versa.

Surprising difference of cube roots

 Show that

$$\sqrt[3]{10 + \sqrt{108}} - \sqrt[3]{\sqrt{108} - 10}$$

is an integer.

Solution below.

.

.

If $a = \sqrt[3]{10 + \sqrt{108}}$ and $b = \sqrt[3]{\sqrt{108} - 10}$

Then we have that $ab = 2$ and $a^3 - b^3 = 20$.

By binomial theorem we also have $$(a-b)^3 = a^3 - b^3 - 3ab(a-b)$$

Thus the given expression ($a - b$) is a root of

$$t^3 + 6t - 20$$

$t = 2$ is the only real root.

A proof of Pythagoras Theorem

Here is a potentially new proof of the Pythagoras theorem I discovered recently. I could not find any prior proofs like these (including in the cut-the-knot pythagorean proof dump), so if you have seen it somewhere, please let me know.

ABC is the right triangle with sides a,b,c.

AD is the angular bisector of CAB and DE is the perpendicular from D to AB.

CD = x, DB = a-x.

It is easily seen that triangles ACD and ADE are congruent and so AE = AC = b and BE = c-b

Area of ACD + Area of ADB = Area of ABC gives

$bx + cx = ab $

And so $x = ab/(b+c)$

Now triangles DEB and ABC are similar and so

$$DE/AC = BE/BC$$

i.e.

$$x/b = (c-b)/a$$

$$a/(b+c) =(c-b)/a$$

Which gives

$$ a^2 = c^2 - b^2$$

Base b and generating functions

 Not a puzzle, just a quick observation noting the power of generating functions.

Say $b \ge 2$ is a positive integer. We give a quick proof using generating functions that every positive integer can be written uniquely in base $b$ with digits $0, 1, \dots, b-1$.

Let $n \ge 1$. Consider 

$$ G(x) = \prod_{k=0}^{n} (1 + x^{b^k} + x^{2b^k} + \dots + x^{(b-1)b^k})$$

Observe that the coefficient of $x^N$ shows the numbers of ways of writing $N$ is base $b$.

Now if $u = x^{b^k}$, then

$$ (1 + x^{b^k} + x^{2b^k} + \dots + x^{(b-1)b^k}) = (1 + u + u^2 + \dots u^{b-1})  = \frac {1 - u^b}{1-u}$$

Thus

$$G(x) = \frac{1-x^b}{1-x}\frac{1-x^{b^2}}{1-x^b}\frac{1-x^{b^3}}{1-x^{b^2}}\dots\frac{1-x^{b^{n+1}}}{1-x^{b^n}}$$

This telescopes to

$$ G(x) = \frac{1 - x^{b^{n+1}}}{1-x}$$

$$ = 1 + x + x^2 + \dots + x^{b^{n+1} - 1}$$

Thus every integer $N$ in the range $1$ to $b^{n+1} - 1$, can be written in base $b$ using at-most $n+1$ digits, taken from $0,1,2, \dots, b-1$. Since the coefficient of $x^N$ is $1$, the representation is unique.

A cute integral with golden ratio

 Show that

$$\int_{0}^{\infty} \frac{dx}{(1 + x^{\varphi})^{\varphi}} = 1$$

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

Scroll down for solution:

Using the substitution $x^{-\varphi} = t$ and the identity $\varphi^2 = \varphi + 1$ we get that

$$dx = -\frac{1}{\varphi} t^{-\varphi} dt$$

Thus the integral becomes

$$\frac{1}{\varphi} \int_{0}^{\infty} \frac{dt}{(1 + t)^{\varphi}}$$

Which is easy to calculate.

A putnam sequence problem

 Let $a_n$ be a sequence such that

$$a_1 = a \ge 2$$

and

$$a_{n+1} = a_{n}^2 - 2$$

Show that 

$$\left(1 - \frac{1}{a_1}\right)\left(1 - \frac{1}{a_2}\right)\dots = \prod_{n \ge 1} \left(1 - \frac{1}{a_n}\right) = \frac{\sqrt{a^2 - 4}}{1 + a}$$

The putnam problem was with $a = \frac{5}{2}$

Scroll down for a solution.

Since $a \ge 2$, we can find a $u \ge 1$ such that $a = u + \frac{1}{u}$ (for $a = \frac{5}{2}, u =2$).

The case $a = 2, u = 1$ is easy, so assume $u \gt 1$.

The recurrence then gives us

$$a_{n+1} = u^{2^n} + \frac{1}{u^{2^n}}$$

Let $$f(x) = \left(1 - \frac{1}{x + \frac{1}{x}}\right) = \frac{x^2 - x + 1}{x^2 + 1}$$

The value we are seeking is

$$f(u)f(u^2)f(u^4)f(u^8)\dots f(u^{2^n})\dots$$

Now notice that

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

Thus if we multiply

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

with $x^2 + x + 1$ we get

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

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

and similarly using 

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

we get

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

Since

$$\frac{x^{2^{n+1}} + x^{2^n} + 1}{x^{2^{n+1}} - 1} \to 1$$

(for $x >1$)

We see that

$$L = f(u)f(u^2)\dots f(u^{2^n})\dots = \frac{u^2 - 1}{u^2 + u + 1}$$

This we can rewrite as

$$ L = \frac{u - \frac{1}{u}}{u + \frac{1}{u} + 1} $$

Squaring gives

$$L^2 = \frac{u^2 + \frac{1}{u^2} - 2}{(a+1)^2} = \frac{a^2 -4}{(a+1)^2}$$

Thus 

$$ L = \frac{\sqrt{a^2 - 4}}{a+1}$$