Wednesday, December 25, 2013

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.


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.

Monday, December 23, 2013

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)

Friday, December 20, 2013

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.

Thursday, December 19, 2013

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.

Tuesday, December 17, 2013

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.

Monday, December 16, 2013

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.

Sunday, December 15, 2013

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).

Friday, December 13, 2013

Division by seven

So first up a justification for why I would want to write about dividing by seven. The short answer is that dividing by any of one through six is pretty trivial. Dividing by two ,three, four, five or six is straight forward primary school mathematics.  Dividing by one is appropriate for (insert group you’d like to insult here).  Seven is the first interesting case.  Long answer: Read the rest of this post and hopefully you’ll see.  Advertising answer: It’s fun to be able to rattle off 20 or 30 digits easily (also cheap and obnoxious but still fun), in front of people who don’t know how to do this.
Long ago in the dim reaches of grade five or so (in my case it was still called standard three) we learned short division.  For those of you who don’t remember grade five (or haven’t gotten there yet). I’ll outline how this works below. Suppose I want to divide 629 by 4. (Obviously skip this if know it).
Start out by writing

I can’t divide this all in my head but I do know that 4 goes into the first digit (6 in this case)  once and leaves a remainder of 2. So I write.

The next step is noticing that 4 goes into  22, five times and leaves a remainder of 2. So I write

Repeating this procedure a few more times (and adding in some zeros after the decimal point) gives us.

Which is to say that 629 divided by 4 is 157.25.

The refresher out of the way let’s try to divide 1 by 7. Start here.

Now fill in some of the rest of it (actually do it if you haven’t).
You’ll get this after 6 iterations.

From here we notice, that we’re pretty much where we started.
We have to divide 10 by 7 in both of the previous 2 pictures and we have an infinite string of 0s in front of us. So we’re going to get the same thing over and over and over again!!!

So 1/7=0.14285714285714285714285714…….
Just remember those six digits in order (less than a phone number and you remember yours) and you can pull off the trick of dividing one by seven.
It gets better though. Dividing two by seven is just as easy, in fact we have already done it!!
How you ask. Well start here

We’ve been here before? Dividing 20 by seven. We get the SAME repeating decimal with a different start point (not to beat anyone over the head with anything but yeah,3/7, 4/7,5/7 and 6/7 work the same way).

All you need to do is remember your start point (and the 6 digit string 142857) and you can divide by 7.
If you want to divide say 27 by 7 then. 27/7=3 remainder 6 so 3.857142857…..
This a pretty neat trick but even better there really isn’t anything special about 7. Provided we're willing to learna 16 digit string we can do division by 17. Division by 13 requires learing two 6 digit strings

This works for every positive integer which doesn’t have 2 or 5 as a factor (why 2 and 5 because they are 10s prime factors  and we're using base 10, yes this also works in every other base for exactly the same reasons). 

For example consider dividing 1 by 349. There are only 348 possible things to carry over when dividing 1 by 349  so when I go through the procedure of short division I’m guaranteed to get back to 1 (the first thing I carry) in at most 348 steps and things will repeat.  The period might not be 348 but it won’t be more.  For example the next 2 “interest numbers”  to divide by in base 10 are 13 and 17.
This is of length 16 and provided you can remember where to start you can figure out k/17 for pretty much any integer k. On the other hand
1/13=0.0769230769230769230… has period 6. So it only gets half of the the k/13s you could wish for.
2/13=0.153846153846…. also has period 6 and gets us the other half.
So when do we get everything from just 1 cycle??? The answer comes oddly enough from geometric series.

To see this we'll consider some examples.
Giving us 7*142857=999999.
Same thing goes through with 13. What this means is that
i.e. 13*076923=999999
The only way to have a period of length (a factor of) 6 is to be divisible by 10^6-1.

Clearly 17 does divide 10^16 - 1 but none of 10^8 - 1, 10^4 - 1, 10^2 - 1 and 10^1 - 1. So it’s period is actually 16.
There are other ways to think about this and it’s quite abit of fun to do so. But this post is getting long so I’ll stop here. 

Tuesday, December 10, 2013

13 Coins Puzzle

So a riddle today.

I have 13 coins. They like many other things have weights. These weights happen to be positive numbers (we're going for realism here).  They also have the property that if I remove any one coin I can split the remaining 12 into two groups of 6 which have the same total weight. Does this guarantee that all the coins have the same weight?

Part a. If the weights are integers.
Part b. If the weights are allowed to be any positive real.
Part c. Sod positivity and indeed reality. Let's let the weight of the coins be any complex number. .

Have fun. Solution to come soon.

Monday, December 9, 2013

What's in a name

So seeing as this blog is pretty new. I figured I'd explain where I got the name from. It's a pun on "fails to reject", a phrase which will be familiar to anyone with any statistics training. For those of you who haven't gotten around to taking a statistics course yet, this feels like an appropriate time to blog about hypothesis testing.

Imagine you find a coin. You decide to keep it so that you can flip it whenever you have a decision to make but don't want to think too hard about said decision. Sadly you're somewhat paranoid and worry that the coin might be biased, which is to say that it might give you heads more often than tails or tails more often than heads.

To spite the worry you figure that it's probably a fair coin. (Most of us actually do assume that coins we find on the street/beach/fires of mount doom are fair.) Using epic levels of  ignoring anything even remotely resembling  a discussion of the epistemology of this assumption for the moment I'm just going to say that we provisionally accept that the coin is fair because this is a "natural thing to do". The key word here is provisionally.

Now we'd like to see if the coin is actually fair. How do we do this? By actually flipping it of course. Now imagine for example that your first five flips turn out to be heads tails tails heads heads. This is pretty unremarkable and seems consistent with the idea that our coin is fair, and we might be tempted to accept the fact that our coin is fair. The trouble is that at this point we meet Alf who stares at our coin and decides (just because he feels like being contrary) that it's a coin that comes up heads 65% of the time (Don't we all know an Alf). As it turns out you've gotten 3 heads out of 5 flips, or 60% heads. Which seems more or less as consistent with 65% as with your 50%. Of course 50% feels a lot more natural to you  than 65%, but this joker at least claims that 65% seems more natural to him; sadly 3 out of 5 heads is pretty consistent with getting heads 65% of the time as well. It's also consistent with 60% heads or 61% heads.

Anyway you and Alf then flip the coin another 495 times to have a total of 500 flips. It turns out that your total number of flips is now 254. This is consistent with your 50% and not consistent with his 65% idea. He now needs to relinquish his idea of 65% heads in the face of data (yes, I'm being intentionally vague here about when exactly Alf should become overwhelmed by the data).  Alf now needs to reject his 65% hypothesis.

Which means you get to accept yours!!! Not so fast, along comes the even more annoying Bob (yes we're going alphabetical you should have figured this out when I named a character Alf). Bob has watched the whole exchange and been quietly muttering to anyone who'll listen that it's actually a 51% heads coins. He won't let you make the group accept your idea of a 50% coin. You can't accept the idea of the coin being fair yet because Bob could be right about the 51% but as the first 500 flips haven't been very different to what you expected you can hold onto your 50%  hypothesis. That is you can fail to reject your initial 50% estimate. As Bob is snarkily pointing out this isn't the same thing as accepting the 50% hypothesis.

Anyway you and Bob spend the next year locked in a coin flipping data collection battle and finally get one million total flips. These include exactly 501,218 heads. Bob is wrong (haha Bob). So Bob rejects his null hypothesis and you once again fail to reject yours. Finally Carl appears and claims the coin comes up heads 50.01% of the time. After using a hyperbolic time chamber for several millenia you manage to flip the coin 10^50 times , and it turns out that you have 5.0010001*10^49. heads. Yeah Carl seems right so you reject your null hypothesis (which is why you failed to reject instead of accepting) and Carl decides to fails to reject HIS null hypothesis. Later Daisy comes along and suggests it's actually a 50.00983839% coin and hilarity (or a least a lot of time) ensues testing both of these hypotheses.

Now we call one of these initial hypothesis a "null hypothesis" and we speak of rejecting or failing to reject the null hypothesis. Notice that we always fail to accept it (hence the blog title).

Of course at some point the effective difference between 50.01% and 50.0099% is something no-one actually cares about (hopefully).

Again I've left out the description of exactly how much data is needed to reject a null hypothesis, but that's probably a post for another day.