War General and Prisoners

A war general has captured N of you and is holding you prisoners.

He has two prison camps which are on different islands (say A and B) and those islands are connected to the main land by a flimsy bridge each.

Getting bored, the general decides to play a game with you.

"

You will all be given N distinct real numbers. Each of you can see the numbers of the other prisoners but not yours.

Once you see the numbers, you each have to independently come to me and tell which island you want to be in for the night (A or B).

Next morning I will start calling out two prisoners at a time starting with the smallest number and calling out in order. These two prisoners need to take the bridge of their island and walk towards the main land at the same time.

The bridges are flimsy, so if two prisoners walk the same bridge at the same time, the bridge will explode and so will the prison camps killing everyone who hasn't been freed yet.

If they take different bridges, they both go free and I will continue calling out two at a time.

You can decide upon a strategy before I assign numbers to you.

"

What is the maximum number of prisoners that can guaranteed to be freed?


[Solution]

Digits in $2^n$

Let $a_n$ = number of odd digits in the base-$10$ expansion of $2^n$ and let $b_n$ = total number of digits in $2^n$.

For eg, $2^8 = 256$ and so $a_8 = 1$ ($5$ is the only odd digit) and $b_8 = 3$ (it is a 3 digit number).

Three problems:

A) Show that $$\sum_{n=1}^{\infty} \dfrac{a_n}{2^n} = \dfrac{1}{9}$$

B) Show that $$S = \sum_{n=1}^{\infty} \dfrac{b_n}{2^n}$$ is an irrational number.

C) Show that $S$ as defined in B) above satisfies $$ S \gt \dfrac{1169}{1023}$$


[Solution]

Sum of squares <= Sum of cubes

$a,b,c \gt 0$ and $abc = 1$

Show that

$$ a^2 + b^2 + c^2 \leq a^3 + b^3 + c^3$$

[Solution]

Sum of reciprocal squares

There are two parts to the problem

1) Show that $\frac{\pi}{4} \gt \sqrt{2-\sqrt{2}}$

2) Show that $\sum_{n=2}^{\infty} \frac{1}{n^2} \gt \frac{3}{5}$

Incidentally 2) implies 1) and is a stronger result than 1) which has an easier proof.

[Solution]

Lion and Lion Tamer

There is a circular cage which has the lion and a lion tamer (assume point masses) in there somewhere. Both the lion and the tamer run at the same speed.

Can the lion catch the lion tamer? (In finite time).


Solution (Highlight to view):

This is a pretty hard problem and the surprising answer is no!

It seems like the lion should be able to catch the lion tamer by directly moving towards lion tamer, but the lion tamer can escape! This is assuming they are moving points in the 2D plane. The lion can get arbitrarily close, but cannot coincide.


This problem was proposed by Richard Rado in 1920s and was solved by Abram Besikovitch in 1950s.

A solutions appears in the the book "A Mathematical Miscellany" by Littlewood.

I don't have good links, so this might be a starting point: lion and man problem.

Five pairwise products

You have four positive reals. They have six pairwise products. Five of them are $2,3,4,5,6$. What is the sixth one?

(Pairwise products of $a,b,c,d$ are $ab,ac,ad,bc,bd,cd$)




Solution (highlight to view):


Out of the given 5 products we must have that 4 of them are such that product of two is same as the product of the other two which is also the same as the product of the 4 unknown numbers. Moreover, the 6th missing product is this product divided by the 5th given product.

The only possibility with the given 5 products is $3 \times 4  = 2 \times 6$ and so the missing product is $\frac{12}{5}$.

Nice defense by Rajendra Gokhale

This hand occurred at a local tournament in Pune, India.

The defense was made by Rajendra Gokhale (rvg), who has won the premier teams event in the 2018 Indian nationals.

You hold J9x, Txx, Axx, JT8x and opponents reach 4S by the following auction. LHO being the dealer:

1NT - 2C
2H - 2S
4S

You choose to lead the J of clubs and see

IMPS None
West ♠ Qxxx ♥ AKxx ♦ T ♣ AQ9x
	South ♠ J9x ♥ Txx ♦ Axx ♣ JT8x

W	N	E	S
1NT	P	2C	P
2H	P	2S	P
4S	P	P	P

Declarer wins the A, with partner discouraging and runs the DT to your A.

You win and play a heart. Declarer wins the HA, cashes the HK and ruffs a heart. Declarer then plays the DQ pitching the last heart from dummy. Partner wins the K and returns a club which declarer wins the 9 dummy and plays a spade to the K winning.


At this point, defense has won 2 tricks (DA and DK) and partner needs to have the SA to have any chance. Even then, where is the 4th trick coming from?

Declarer is going to duck a spade to drop partner's A and that will be end of defense. What will you do?



When declarer played a spade towards the Q, rvg put up the Jack! Declarer covered with the Q which was won by partner's A. Partner now played the last heart to promote the S9 for the setting trick.

Nice defense!

Textbook 6H

This is a hand from the intra google bridge tournament (a global tournament among Google employees).

You are South holding -,JT8xxxx, AQx, AKx and open 1H after RHO passes as dealer. You hear partner bid 3H (10-12 limit raise with 4).  What will you bid?

Say you just somehow end up in 6H.


LHO leads the CT and you see:

IMPS E/W	Dummy ♠ AT32 ♥ A974 ♦ 865 ♣ QJ
	You ♠ - ♥ JT86532 ♦ AQ7 ♣ AK2

Contract:6H

First Lead: ♣T

How will you play?










The problem will be if hearts don't split and DK is offside. You can cater to some of that via an end play.

Win the club in dummy, cash SA throwing a diamond, and ruff a spade (key play).

Now play a heart to the A. If trumps divide, you can take the diamond finesse for the overtrick. If RHO has the KQ, you have to rely on the diamond finesse.

If LHO has the trump KQ (as it was at the table) now you can still practically guarantee your contract. Ruff a spade to hand, cash the clubs throwing a spade and exit a heart. Now LHO has to play a diamond or give a ruffnsluff.

As fate would have it, LHO had the DK too, so this was a required play to make the slam.

This hand was bid and made by Wei-Bung Wang (who has played internationally for the Taiwain junior national team). The other table was only in 4H so making it was a huge swing (as compared to going down).

Wei-Bung bid 6H directly after the 3H and this is his reasoning:

I opened second hand. RHO didn’t open 2S, LHO didn’t overcall 1S. Partner rates to have some spades. If he has 5-4-2-2 and no strength at all, the slam is still 26%. There’s no scientific way to stop at 4-level. There’s also no scientific way to reach grand slam.

Defensive 4H

In an IMP team game, you are East and hold x, AQx, QJxxx, Kxxx

(If you need to know what an x is, assume lowest spots).

Your partner is dealer and opens 2S , RHO bids 3C, you pass, LHO bids 4H which ends the auction.

Partner leads the SK and yoy see:

IMPS None	Dummy ♠ Axx ♥ x ♦ Axxx ♣ AQJ9x
		You ♠ x ♥ AQx ♦ QJxxx ♣ Kxxx

W	N	E	S
2S	3C	P	4H
P	P	P

Declarer wins the SA, cashes DA throwing a spade and plays a heart.

What is your plan?









If you go up with the HA, you get 2 hearts and a club, but that is all. Declarer can easily discard the last spade loser on clubs.


You must hope partner has Jx or Tx of hearts and play the Q!

Imagine you are declarer with KJ9xxxx  and see the Q show up. You could try winning the K and play low to cater to AQ with RHO. If declarer ducks and it is indeed AQ tight, RHO could maneuver a club ruff for partner.

Declarer could still get it right, but has to guess. If declarer guessess wrong, partner will get in with a heart to cash his spade. You now get 2 hearts, 1 spade and 1 club to beat the contract. If declarer guesses right you have just let them make an overtrick.


At MPs this is harder and going up with the A to guarantee the second heart trick is probably the percentage play.

Integer polynomial property

$P$ is a polynomial with integer coefficients. Show that if $a$ is an integer such that

$$ P(P(P(a))) = a$$

then

$$ P(a) = a$$


Solution Sketch:


This uses the fact that $P(x) - P(y)$ is divisible by $x - y$ to get a cyclic chain of divisibility conditions implying each one in the chain is $\pm1$ times the others. Some assumptions like $P(a) \gt a$ etc lead to contradictions.

First trick decision in 3H (and defensive tidbit too)

This was MP, but assume IMPS.

You are South and end up in 3H. LHO leads CQ.

IMPS None	North ♠ Kx ♥ AKx ♦ KQT98 ♣ Kxx
	South ♠ xxx ♥ QJTxx ♦ Jx ♣ xxx

W	N	E	S
1S	X	P	2H
P	3H	P	P
P

What is your plan? Do you cover or duck the CQ? Do you think you can make this?

At the table I ducked the CQ and the CJ continuation which held too.

LHO now shifted to a heart and it was all over. I could draw trumps and play on diamonds with a spade entry to dummy.

After the CJ held, LHO who held AJTxxx, x, Axxx, QJ could shift to the SJ (or T) to knock out the SK, then use a low spade to get to partner's hand to cash the setting club trick! RHO could have overtaken the CJ to give partner a ruff but that is losing defense when partner has QJx.

A simpler defense by West is to just play SA and another but that might not work against a hand like xx, Qxxxxx, Jx, xxx (though South might have bid 4H with that).

With the right defense this cannot be made whether you cover or duck the first trick.

Which is greater? $2^{128}$ or $3^{81}$

Which is greater?

$$2^{128}$$ or $$3^{81}$$

No calculators allowed.

Solution [Click here to expand/collapse]

$2^{128} = 340282366920938463463374607431768211456$

$3^{81} = 443426488243037769948249630619149892803$

So $3^{81} \gt 2^{128}$. QED (in about 4 hours).

Just kidding :)

Here is a proof without calculators.

Raise both sides to power of $\frac{1}{16}$.
We get $$2^8 \text{ vs } 3^{\frac{1}{16}}. 3^5$$ Now $3^{1/16} \gt e^{1/16} \gt 1 + \frac{1}{16}$ (using $e^x \gt 1 + x$)

Since $13 \times 16 = (15-2)(15+1) \lt 15^2 = 225 \lt 243$

We have that $1 + \frac{1}{16} \gt 1 + \frac{13}{243} = \frac{2^8}{3^5}$.
QED.

Classic trig equality

Show that

$$\displaystyle \tan(3\pi/11) + 4\sin(2\pi/11) =\sqrt{11}$$



[Solution (math.stackexchange link).]

Yet another inequality

$x_1, x_2, \dots, x_n$ are $n$ positive real numbers with sum $S$, $n \gt 1$.

Show that

$$ \sum_{i=1}^{n} \frac{x_i}{S - x_i} \ge \frac{n}{n-1}$$


Solution [Click here to expand/collapse]

Using AM >= GM we have that

$\sum y_i \sum \frac{1}{y_i} \ge n^2$

Applying this to (wlog, assuming $S = 1$) $$\left(\sum_{i=1}^{n} \frac{1}{1-x_i}\right) \left(\sum_{i=1}^{n} (1 - x_i)\right) \ge n^2$$ i.e $$ \sum_{i=1}^{n} \frac{1}{1-x_i} \ge \frac{n^2}{n-1}$$ And so $$ \sum_{i=1}^{n} \left(\frac{1}{1-x_i} - 1\right) \ge \frac{n^2}{n-1} -n$$ Which gives us what we want to prove.