Problem of the year 2014.

So it's almost 2014 (in case anyone didn't notice).

One of my favorite new year activities is the problem of the year. So as not to spoil the fun I'm going to use other years to explain

The goal is to construct the natural numbers using the digits of the year. You need to use digits in order and can use plus, minus,times,divide, sqrt, concatonation, exponentiation and factorial.

for example a list with 1997 might start like this.

1^997=1
1^9*(9-7)=2
1^9+(9-7)=3

If it was 2005 then 2+0+sqrt(0!+5!)=13 would be allowed.  In 2025 20+sqrt(25)=25 would be allowed.

You're also allowed to use cube roots if you can find a 3. e.g. (2+0!)radical(27)=3.  would be ok in 2027. because we often write cube root like a square root except with a little 3 (yes I need to figure out how to insert equations properly into this format).


Anyway let'ssee how long an unbroken list we can make for 2014 collaboratively.

Nine Card Solution.

First I'm going to mention another game. Noughts and crosses  or tic-tac-toe. Everyone has played it and everyone older than 8 or so figured out how to play optimally. I'm going to claim that the nine card game is tic-tac-toe in a very precise sense.


Consider the magic square.

                      4  9  2
                                       3  5  7
                      8  1  6

It's known for every row, column and diagonal summing to 15. A little work will convince you that these are also the only ways to sum to 15, with exactly 3 distinct integers between 1 and 9.

As we all know how to play tic-tac-toe, we're done.

(edit: the middle row of the magic square appeared off-center,think it should be fixed now)

A puzzle about uniform random varibles

So we're drawing uniform random variables today. As seems customary they're i.i.d. uniform 0-1 random variables. We'll keep a running count of the sum of these and stop once the sum exceeds one.

So if our sequence is 0.2,0.7,0.4, 0.6 and so on our running totals will be 0.2, 0.9, 1.3, 1.9 and so on.

However we'd stop after the 3rd number as the sum is over 1. So in his case the number of draws would be 3.

The puzzle today is how many numbers we expect to draw.  That is if X is the number of draws find E[X].

Hat tip to Simon Spicer for showing me this one (neither he nor I knows where he got it from). Enjoy.

Nine card Puzzle

Today's puzzle is to analyze a two player strategy game.  Nine cards labeled 1 through 9 are placed face up on the table.

Player 1 takes a card.
Player 2 takes a card.
Player 1 takes a card.
Player 2 well you know takes a card.

This continues until either player holds 3 cards which sum to 15. By this I mean exactly 3 cards which sum to exactly 15. Holding 3 such cards is the win condition. i.e. when you pick up that 3rd set making card you win. Alternatively the game could go on until all 9 cards are used up and noone has a winnign set in which case it's a draw.

What happens if both players play perfectly? I initially saw this puzzle in  Mathematical Digest, an incredibly awesome mathematics magazine for high-schoolers, with a focus on competition math. As I said it's awesome and this seems like a good time to plug it.

For those of you who have seen it before I'll leave you with trying to figure out which generalizations (if any) are "nice". By generalization I mean having the cards as some multi-set of integers (i.e. allow repeats) and when a win is holding k cards summing to n (choose values of n and k). Possibly allowing multiple pairs of (k_i,n_i) to grant the win.

River crossing puzzle

There is a puzzle I heard a few years ago which goes like this.
Eight people want to cross a river.
They are A policeman and a criminal, a father and his two sons and a mother and her two daughters.
The trouble is that the boat they have can only carry 2 of them at a time and only the mother, father and policeman can row.
However the criminal will hurt anyone he is left alone with if the policeman is not there to restrain him. If the father is left with the daughters and the mother isn't there to protect them he will hurt them regardless of the policeman's presence. Similarly the mother will hurt the sons if she is left alone with them and the father is not there to protect them. How do they cross?

Here is an app with a much less creepily worded version of the problem. The policeman and criminal are replaced by a farmer and a dog. The father and his sons by a boy and his hamsters, the mother and daughters by a girl and her bunnies. Hurting by teasing.

Two related problems are the Jealous Husbands Problem and the Missionaries and Cannibals Problem

In the JH problem you have three husbands and there wives.  Everyone can row the boat but at no time may a wife be left without her husband and with another man. In the M+C there are three missionaries and three cannibals. Everyone can row the boat but you can never have the missionaries outnumbered by the cannibals on a particular bank.

International laughs-Chad and Romania

This is the flag of Chad

This is the flag of Romania

Yes the joke is that these look pretty much identical. The shades of Blue, are admittedly different but well how did this happen??? Alot of countries use a tri-colour design and these are the three primary colours, so there is some sense in which if 2 countries are picking the same flag this might well be it.

Chad adopted it's flag on the 11th of June 1959, and retained in 1960 when independence from France was established. At the time Romania's flag had a coat of arms in the middle, this was changed to another coat of arms in 1965 and finally changed to the current flag on December 27, 1989.

In 2004 there where apparently rumours of Chad bringing this up in the united nations. Then president of Romania Ion Iliescu make a public statement that his country would not give up the flag.

13 Coins Solution

So here are the solutions to the 13 coin conundrum .

Part a was solved in the comments but to rehash it.

You begin by observing that the 13 coins must all be the same weight mod 2. If this was false, i.e. if there was a coin of even weight and a coin of odd weight then removing one of them would leave the rest of the coins with a total weight which is odd, and hence that cannot be split into 2 equal bits.

One then iterates this observation by observing that they must be the same weight mod 4,8,16 etc. Eventually you get beyond the size of the largest coin and hence they are the same weight. The easiest way to see this is to divide the weights by 2 if they are all even and to ad 1 and divide by 2 if they are all odd.

Part b requires less ingenuity but more advanced techniques. Consider the vector space over Z  generated by the 13 weights. It is clearly finite dimensional. Write each weight as a vector in this space and apply the result of part a to each co-ordinate.

Similiarly for part c it's a vector space of size 2 over R (i.e. part b).