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

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.