The pigeonhole principle is the principal that states that if you play eight games of chess, two must be played on the same day of the week. If this isn't obvious think of which days you want to put the first seven games on. You'll be out of possible days to put the eighth game.
A classic demonstration of this is to show that two people have the same number of hairs. The argument goes like this:
1. No one has more than one million hairs (apparently the human average is around 150,000). This isn't a provable fact in the mathematical sense but we know it in the same way we know no one is 5 meters tall.
2. There are over seven billion people in the world.
3. Apply the pigeonhole principle.
Now this actually means that the average person is sharing the number of hairs they possess with something well north of seven thousand people.
An interesting discussion I remember having with a prof in grad school inspired by this was weather anyone is the only human in the world with k hairs, for some k? After all most people are clearly sharing a hair number with thousands, on the other hand someone has the most hairs and like most things the tails of the distribution are likely... well tails. Would we have a unique "winner" if we ranked people by most hairs? I don't know and my mind has gone back and forth a few times.
Wednesday, March 21, 2018
Wednesday, May 31, 2017
Chicken Farming
A chicken farmer can make 6kg, 9kg and 20kg bags of chicken. However he can't make anything else, so for example if you asked him for 7kg of chicken he couldn't do it. On the other hand if you asked him for 15kg he would be able to do that by selling you both a 6kg bag and a 9 kg bag.
A natural question to ask is which amounts can he make and which amounts can he not make, a sub-question here is to ask what the largest integer amount he cannot make is. It should be noted that he can make as many bags of each weight as he wants.
The solution (stop here if you want to play with it yourself for a few minutes, because spoilers ahead) is to notice that if you don't use any 20 kg bags you can make a lot of multiples of 3. In particular one can make 0,6,9,12,15,18 and so on bags every non-negative multiple of 3 except 3 itself.
The next thing to notice is that if you don't use a 20kg bag that that's all you can do! Adding 6s and 9s isn't ever going to give you something which isn't a multiple of 3.
Now if we use just one 20kg bag? Well then we can make 20,26,29 32,35,... . In other words we can make most positive integers which leave a remainder of 2 when divided by 3 (in a more formal phrasing numbers which are 2 mod 3) and nothing else. The exceptions being things less than 20 and 23.
That only leaves those weights which are 1 mod 3. We need at least two 20kg bags to get anything which is 1 mod 3, but using exactly two 20s we can make 40,46,49 and so on. This means the largest integer weight we can't make is 43kg.
Now the trick here was to notice that 6 and 9 share a common factor of 3. That's all well and good but what if the farmer can make lots of 3 arbitrary positive integers a,b and c? It turns out that this is an open problem but I'll leave it for another post.
A natural question to ask is which amounts can he make and which amounts can he not make, a sub-question here is to ask what the largest integer amount he cannot make is. It should be noted that he can make as many bags of each weight as he wants.
The solution (stop here if you want to play with it yourself for a few minutes, because spoilers ahead) is to notice that if you don't use any 20 kg bags you can make a lot of multiples of 3. In particular one can make 0,6,9,12,15,18 and so on bags every non-negative multiple of 3 except 3 itself.
The next thing to notice is that if you don't use a 20kg bag that that's all you can do! Adding 6s and 9s isn't ever going to give you something which isn't a multiple of 3.
Now if we use just one 20kg bag? Well then we can make 20,26,29 32,35,... . In other words we can make most positive integers which leave a remainder of 2 when divided by 3 (in a more formal phrasing numbers which are 2 mod 3) and nothing else. The exceptions being things less than 20 and 23.
That only leaves those weights which are 1 mod 3. We need at least two 20kg bags to get anything which is 1 mod 3, but using exactly two 20s we can make 40,46,49 and so on. This means the largest integer weight we can't make is 43kg.
Now the trick here was to notice that 6 and 9 share a common factor of 3. That's all well and good but what if the farmer can make lots of 3 arbitrary positive integers a,b and c? It turns out that this is an open problem but I'll leave it for another post.
Friday, May 19, 2017
Frequentist and blogging frequency
So I haven't used this blog in a while, but I'm back-ish. Which means I'm panning to start blogging again but may or may not actually get around to it this time.
In my first ever post I discussed the idea of a hypothesis test. However I didn't get into any of the technical details in that post. For example suppose I believe that my null hypothesis is that my coin comes up head 50% of the time for data I've flipped it 30 times and gotten 20 heads and 10 tails.
Does this mean that I need to give up the idea of a coin which produces heads exactly half the time? In the last post we spoke about the idea of rejecting a hypothesis which is inconsistent with the data, if we had 29 out of 30 heads we'd chuck the idea of a 50-50 coin, if we had 16 heads (again out of 30) we'd keep it. For 20 however it's less obvious. Where is the cutoff?
More generally where should the cutoff be? The usual answer to this is ask "How likely would I be to see data this or more strongly against the null hypothesis if the null hypothesis was indeed true?". We then reject the null hypothesis if this probability, which we call a p-value, is "small" and fail to reject it otherwise.
By tradition "small" is usually taken to mean less than 0.05, sometimes this tradition is broken, some fields have different traditions and some statisticians absolve themselves of this by saying "the p-value is... ".
Going back to our original question of 20 heads in 30 flips, how likely would I be to see data this or more strongly against the null hypothesis if the null hypothesis was indeed true? The surprising answer is: "It depends". A fuller version of this answer is "It depends on what you mean by more strongly against".
The probability of getting 20 or more heads from 30 flips works out to about 0.04937, just under the traditional 5% (0.05). However the probability of getting 20 or more heads OR 10 or less heads is twice that. Would 3 heads out of 30 stronger evidence that our null hypothesis is wrong than getting 20? Before you say "yes of course" what if we had exactly 15 heads but they alternated? i.e. HTHTHTHTHTHTHTHTHTHTHTHTHTHTHT.
Again the answer here seems like it should be "yes of course that's different" but this dependency isn't something we were thinking about beforehand. Worse it's pretty easy to find patterns in a lot of sequences so we could in principle keep adding in things more surprising than our (unnamed) string of 20 heads in 30 flips.
For this reason we need to specify in advance what counts as stronger evidence against our null hypothesis. This is called an alternate hypothesis. Sometimes it's appropriate to make the alternate hypothesis "p>1/2" (or "p<1/2") and sometimes it's appropriate to say p is not 1/2, sometimes it's appropriate to say p depends on the last flip or two in this some way.
Of course this isn't the only way to do things. There are others which perform better in some situations and worse in others. I'll (maybe) discuss these in a later post.
In my first ever post I discussed the idea of a hypothesis test. However I didn't get into any of the technical details in that post. For example suppose I believe that my null hypothesis is that my coin comes up head 50% of the time for data I've flipped it 30 times and gotten 20 heads and 10 tails.
Does this mean that I need to give up the idea of a coin which produces heads exactly half the time? In the last post we spoke about the idea of rejecting a hypothesis which is inconsistent with the data, if we had 29 out of 30 heads we'd chuck the idea of a 50-50 coin, if we had 16 heads (again out of 30) we'd keep it. For 20 however it's less obvious. Where is the cutoff?
More generally where should the cutoff be? The usual answer to this is ask "How likely would I be to see data this or more strongly against the null hypothesis if the null hypothesis was indeed true?". We then reject the null hypothesis if this probability, which we call a p-value, is "small" and fail to reject it otherwise.
By tradition "small" is usually taken to mean less than 0.05, sometimes this tradition is broken, some fields have different traditions and some statisticians absolve themselves of this by saying "the p-value is... ".
Going back to our original question of 20 heads in 30 flips, how likely would I be to see data this or more strongly against the null hypothesis if the null hypothesis was indeed true? The surprising answer is: "It depends". A fuller version of this answer is "It depends on what you mean by more strongly against".
The probability of getting 20 or more heads from 30 flips works out to about 0.04937, just under the traditional 5% (0.05). However the probability of getting 20 or more heads OR 10 or less heads is twice that. Would 3 heads out of 30 stronger evidence that our null hypothesis is wrong than getting 20? Before you say "yes of course" what if we had exactly 15 heads but they alternated? i.e. HTHTHTHTHTHTHTHTHTHTHTHTHTHTHT.
Again the answer here seems like it should be "yes of course that's different" but this dependency isn't something we were thinking about beforehand. Worse it's pretty easy to find patterns in a lot of sequences so we could in principle keep adding in things more surprising than our (unnamed) string of 20 heads in 30 flips.
For this reason we need to specify in advance what counts as stronger evidence against our null hypothesis. This is called an alternate hypothesis. Sometimes it's appropriate to make the alternate hypothesis "p>1/2" (or "p<1/2") and sometimes it's appropriate to say p is not 1/2, sometimes it's appropriate to say p depends on the last flip or two in this some way.
Of course this isn't the only way to do things. There are others which perform better in some situations and worse in others. I'll (maybe) discuss these in a later post.
Sunday, September 6, 2015
SATMO 2015
I'ma little late on this one but never the less.
On Saturday August 22nd the 4th South African Tertiary Maths Olympiad was held. The final results can be seen here. A large thanks to Stephan Wagner for organizing the contest, and to Margaret Archibald, Steven James, Celeste Johnson and Shunmuga Pillay for helping out with invigilating at Wits.
Also I must thank the Mathematical Science Students Council at Wits for advertising the event far far better than I could ever have done. In the end we had 35 Wits students sat the exam.
I plan to do another post on the statistics of the exam over the last few years fairly soon but for now I'll simply say congrats to the winners and to everyone who took part.
On Saturday August 22nd the 4th South African Tertiary Maths Olympiad was held. The final results can be seen here. A large thanks to Stephan Wagner for organizing the contest, and to Margaret Archibald, Steven James, Celeste Johnson and Shunmuga Pillay for helping out with invigilating at Wits.
Also I must thank the Mathematical Science Students Council at Wits for advertising the event far far better than I could ever have done. In the end we had 35 Wits students sat the exam.
I plan to do another post on the statistics of the exam over the last few years fairly soon but for now I'll simply say congrats to the winners and to everyone who took part.
Sunday, May 24, 2015
Math Bee
I've been asked to set a competition style maths contest for first year students at wits. For some reason or another the organizers decided to call this a (the?) math bee. The goal is 20 multiple choice questions of a level somewhere between the SAMO Seniors 2nd round and the SATMO.
I'd like to avoid the paper having too many of my own personal biases. To that end this post is a call for questions. If anyone has any that seem appropriate then please e-mail me them to me, I will thank you via blog post.
I'd like to avoid the paper having too many of my own personal biases. To that end this post is a call for questions. If anyone has any that seem appropriate then please e-mail me them to me, I will thank you via blog post.
Sunday, May 17, 2015
Jury Duty
I've been playing with some problem's from the book "50 Challenginh problems in probability with solutions by Frederick Mosteller (my great grand advisor as it happens).
Anyway one of the first problems compares two different juries.
The first is a one man jury where the juror gets it right with probability p. As there is only one juror his ruling applies.
The second is a three man jury with two jurors getting it right with probability p (independently) and the third coin-flipping juror who gets it right with probability 1/2 (again independently). In this jury majority rules. Which is to sy we need two of the three jurors to get things right.
Now the question asked is "which is better". A little algebra shows that they're both equally good, which is to say that the second jury reaches the right verdict with probability p.
So adding one "regular" (right with probability p) juror and one coin flipper doesn't change anything! What if we ad yet another coin flipper and another regular juror? Now we need three of five correct. Now things do change.
A little more algebra shows that we now get the correct verdict with probability,
ppp+2.25ppq+0.75pqq=
pp(p+q)+1.25ppq+0.75pqq=
pp+0.75pq+0.5ppq=
p-0.25pq+0.5ppq=
p+pq(2p-1)/4
Which means that is p>1/2 that adding two jurors to our three (as we did to our one) now improves the verdict. Similarly if p<1/2 (why we're using jurors who're worse than coin flips I don't know but if we did) adding jurors 4 and 5 makes things worse.
Does anyone have any intuition for why adding the first pair of jurors does nothjign but adding the second pair helps?
Anyway one of the first problems compares two different juries.
The first is a one man jury where the juror gets it right with probability p. As there is only one juror his ruling applies.
The second is a three man jury with two jurors getting it right with probability p (independently) and the third coin-flipping juror who gets it right with probability 1/2 (again independently). In this jury majority rules. Which is to sy we need two of the three jurors to get things right.
Now the question asked is "which is better". A little algebra shows that they're both equally good, which is to say that the second jury reaches the right verdict with probability p.
So adding one "regular" (right with probability p) juror and one coin flipper doesn't change anything! What if we ad yet another coin flipper and another regular juror? Now we need three of five correct. Now things do change.
A little more algebra shows that we now get the correct verdict with probability,
ppp+2.25ppq+0.75pqq=
pp(p+q)+1.25ppq+0.75pqq=
pp+0.75pq+0.5ppq=
p-0.25pq+0.5ppq=
p+pq(2p-1)/4
Which means that is p>1/2 that adding two jurors to our three (as we did to our one) now improves the verdict. Similarly if p<1/2 (why we're using jurors who're worse than coin flips I don't know but if we did) adding jurors 4 and 5 makes things worse.
Does anyone have any intuition for why adding the first pair of jurors does nothjign but adding the second pair helps?
Saturday, April 4, 2015
Another lightbulb puzzle
So last week was the first weekly Joburg Math meetup. Which basically means a bunch of friends meeting up and playing with math olympiad type problems. If anyone is interested these meetups happen on Sundays at noon in Motherland coffee Rosebank Mall, and of course everyone is welcome. hopefully they'll also give me new ideas for more regular math type blog posts.
Anyway here is a problem from The book Creative Mathematics by Alan Beardon, and soem generalizaions due to those involved in the meetup.
Problem 1. I have a line of n lightbulbs. Each lightbulb has a switch associated to it. The switch toggles (if on changes to off, if off changes to on) all bulbs except the one it's associated to. If all the bulbs start out as off, for whcih n can they be changed to all on?
Problem 2. What if I put the bulbs in an n1 by n2 grid. Again each bulb has a switch associated to it. The switch toggles all bulbs sharign either a row or coloumn with it's bulb. Another way to say that is that it toggles bulbs agreeing in with it's position in exactly one coordinate.
Problem 3. What if I have an n1 by n2 by... by nk grid. Now each switch toggles bulbs which agree in exactly k-1 co-ordinates.
Problem 4. We have the same grid as problem 3 but now the switches toggle bulbs agreeing with our bulb in exactly l coordinates for general l.
I won't say how far we got with these at the meetup because it would spoil the fun somewhat. I will say that only problem 1 actually occurs in Beardon's excellent book, so it's not to be taken as a given that there are nice solutions beyond that.
Anyway here is a problem from The book Creative Mathematics by Alan Beardon, and soem generalizaions due to those involved in the meetup.
Problem 1. I have a line of n lightbulbs. Each lightbulb has a switch associated to it. The switch toggles (if on changes to off, if off changes to on) all bulbs except the one it's associated to. If all the bulbs start out as off, for whcih n can they be changed to all on?
Problem 2. What if I put the bulbs in an n1 by n2 grid. Again each bulb has a switch associated to it. The switch toggles all bulbs sharign either a row or coloumn with it's bulb. Another way to say that is that it toggles bulbs agreeing in with it's position in exactly one coordinate.
Problem 3. What if I have an n1 by n2 by... by nk grid. Now each switch toggles bulbs which agree in exactly k-1 co-ordinates.
Problem 4. We have the same grid as problem 3 but now the switches toggle bulbs agreeing with our bulb in exactly l coordinates for general l.
I won't say how far we got with these at the meetup because it would spoil the fun somewhat. I will say that only problem 1 actually occurs in Beardon's excellent book, so it's not to be taken as a given that there are nice solutions beyond that.
Subscribe to:
Posts (Atom)