Equalize the buckets

You start with two buckets of water. First bucket has $x$ litres and the second bucket has $y$ litres. Both have enough capacity to hold $x+y$ litres.

Now you do the following:

You take the bucket with the larger amount of water and from that pour water into the other bucket so that the other bucket has double the water.

So if $x \lt y$, then we go from $(x,y)$ to $(2x, y-x)$.

You keep doing this till the buckets have an equal amount of water. Note that in some cases, you will loop indefinitely.

For what initial $(x,y)$ will you be able to equalize the buckets, and not loop indefinitely?

All is not lost

This is a hand from a Swiss teams in the Seattle area.

You are South and hold A9, AKxxxx, xxx, xx. You hear opponents having a canape auction to 4S, LHO declaring and showing 4+ spades and equal or longer diamonds.

Partner leads the HT and you see

IMPS E/W
		East ♠ JTxxx ♥ Jxx ♦ Axx ♣ AJ
	South ♠ A9 ♥ AKxxxx ♦ xxx ♣ xx

The lead is either a singleton or doubleton. You have 3 tricks (SA and HAK).

If the lead is a singleton you can easily get a heart ruff for the setting trick.

If the lead is not a singleton, where is your fourth trick coming from? You have one easy option: partner has the Qx of spades and can promote his Q on the third round of hearts.

What if partner does not have the Qx of spades? Is there any other option? Partner could have the KQ of clubs, in which case you need to shift to clubs before your SA is knocked out. [Partner might have led the CK, yes.]

So the defense is really simple, win the first trick, cash the second heart to confirm is partner has a singleton (in which case, give a ruff immediately).

If partner has a doubleton heart, shift to a club. When you come in with the spade A, you can decide whether to play partner for the Qx of spades or the club. [Could partner figure out your problem and play the club in such a way as to make it clearer to you?]

But in your excitement in setting up a potential club trick, you win the first trick, and shift to a club immediately without cashing the second heart!

Declarer plays the CQ from hand,  low from partner and J from dummy. Next declarer plays a diamond to dummy  and cashes the CA throwing a heart! [You are too shocked to notice partner's cards, if you wanted to know...]

Now declarer plays a low spade. You go up with the A and cash your second heart, declarer playing the Q. Oops. Partner had a singleton heart all along, and you have botched up a sure shot defense.

Could partner still have the SQ which you can promote? Unlikely, declarer played a low spade instead of the J or T and you hold the 9, so looks like declarer probably has the KQ of spades.

But all is not lost.

Do you want to know what partner played on the second heart? Partner played a diamond.

Looks like declarer started with a 4=3=5=1 hand. He played a D to the A already, and partner threw a diamond on the second heart.

Give partner a diamond ruff! You partner defended accurately (not covering the CQ and throwing a diamond), giving you a chance to recover.

Don't let your previous mistake stop you from recovering. Alas, that is easier said than done.

Pens and Caps [Solution]

Kostub has agreed to post his solution to the business card problem, so I will be breaking order (What? There was one?) and posting a solution to the Pens and Caps problem.

The problem:

You have $n$ pens, and $n$ caps for the pens. For every pen, there is exactly one cap that fits. The rest are either loose or tight.

Someone has taken the caps out and jumbled them up. Can you fit the caps on their respective pens, in expected $O(n \log n)$ time?

Solution

---

You basically do a quicksort!

Choose a cap at random. Now split the pens based on that cap. Smaller pens on one side (cap is loose), larger on the other (cap is tight) and the one that exactly fits is kept aside.

Now you recurse. Any expected time analysis for random pivot based quicksort will work here too.