Mathematics

[Law]

Got a cool maths puzzle? Want help with your homework? Just like maths?


I'll share my favourite puzzle:

100 logicians are on an island. 50 have blue eyes, 50 have brown eyes. There are no mirrors and none of the logicians can communicate with each other. All know that only blue and brown eyed people inhabit the island, none know it's 50-50. At the end of each night, a boat arrives and all men who know their own eye color may leave.

I sneak on the island and tell all 100 logicians, "I see a man with blue eyes" then I flee.

Who, if anyone, leaves the island, and when?

 

[roytheshort]

I know you, you want stupid answers. The only way I can ruin your fun is by posting the actual answer!

The answer is that on the 100th day, all 100 blue-eyed people will leave. It's pretty convoluted logic and it took me a while to believe the solution, but here's a rough guide to how to get there. Note -- while the text of the puzzle is very carefully worded to be as clear and unambiguous as possible (thanks to countless discussions with confused readers), this solution is pretty thrown-together. It's correct, but the explanation/wording might not be the best. If you're really confused by something, let me know.

If you consider the case of just one blue-eyed person on the island, you can show that he obviously leaves the first night, because he knows he's the only one the Guru could be talking about. He looks around and sees no one else, and knows he should leave. So: [THEOREM 1] If there is one blue-eyed person, he leaves the first night.

If there are two blue-eyed people, they will each look at the other. They will each realize that "if I don't have blue eyes [HYPOTHESIS 1], then that guy is the only blue-eyed person. And if he's the only person, by THEOREM 1 he will leave tonight." They each wait and see, and when neither of them leave the first night, each realizes "My HYPOTHESIS 1 was incorrect. I must have blue eyes." And each leaves the second night.

So: [THEOREM 2]: If there are two blue-eyed people on the island, they will each leave the 2nd night.

If there are three blue-eyed people, each one will look at the other two and go through a process similar to the one above. Each considers the two possibilities -- "I have blue eyes" or "I don't have blue eyes." He will know that if he doesn't have blue eyes, there are only two blue-eyed people on the island -- the two he sees. So he can wait two nights, and if no one leaves, he knows he must have blue eyes -- THEOREM 2 says that if he didn't, the other guys would have left. When he sees that they didn't, he knows his eyes are blue. All three of them are doing this same process, so they all figure it out on day 3 and leave.

This induction can continue all the way up to THEOREM 99, which each person on the island in the problem will of course know immediately. Then they'll each wait 99 days, see that the rest of the group hasn't gone anywhere, and on the 100th night, they all leave.

 

[Law]

Roy, you could at least not copy directly from the website. Mine has 50 blue-eyed individuals, not 100. :/

 

[roytheshort]

I didn't copy it, in the time it took for me to answer your question the islanders had children.

 

[Law]

What are the islander's breeding rates? Seems pretty fast...

 

[roytheshort]

Brown eye genes are dominant, so if they have babies fast enough and wait a couple thousand years they will all know they have brown eyes.

 

[Law]

All the brown-eyed individuals carry the blue-eyed gene.

 

[GVmG]

They can't communicate with each other yet they bred.

Meanwhile I can communicate with people and I'm still single... what a cruel life.

 

[Law]

Logicians are great at dating.

"It has been concluded you are the 43rd most attractive male on the island, I am the 43rd most attractive female. Shall we mate?"

 

[roytheshort]

How about everyone just removes their own eyes, that way they know their eye colour is "Nothing".

 

[Alice]

Ah, I remember this one. First time I heard a very similar version with suicidal rabbits and poisonous carrots, that was some pretty messed up version.

Either way, here goes nothing.

Spoiler

If there was only one person with blue eyes, they would leave the first time after the visit, because they would see everyone else has brown eyes, and so they must be the chosen one.

If there were two people with blue eyes, each of them would see only one person with blue eyes. So each would conclude:
"If I have brown eyes, that one person will leave the first day.
If they don't leave, the second day it'll be clear that we both have blue eyes.
If they leave the first day, it'll mean they saw only brown-eyed people, and it'll be clear I'm brown-eyed, too. Either way, I'll leave the second day."

That reasoning can be generalised.
"I see N people with blue eyes. If I have the brown eyes, they'll leave the Nth day.
If they don't leave, it means I have blue eyes, and we'll all leave the N+1st day.
If they leave the Nth day, it'll mean each of them saw N-1 blue-eyed people, and that I'm brown-eyed. Either way, I'll leave the N+1st day."

Thus, blue-eyed people, each seeing 49 other blue-eyed people, are set to leave the 50th day, and the brown-eyed people, each seeing 50 blue-eyed people, are set to leave the 51st day.

So some people start couting down on some sort of diagrams or calendar things or whatever, then someone gets impatient, sees someone else's diagram and figures out from that how many blue-eyed people that person saw, and thus figured out their own eye colour. So that person leaves early, and the other ones are like, "what the heck just happened?", and they can't even complain to each other about it because they can't communicate. Then it turns out some people actually like living on that island, so they decide to stay in the end, adding to the confusion. Also, someone invites boatperson to a drink, and boatperson agrees, because she's the famous slacker Komachi Onozuka.

To sum it up, the real world is pretty darn complicated. Q.E.D.

--- EDIT ---

Gah, roy beat me to the proof. I mean, not the proof of the riddle, but of my final conclusion. >.<

 

[RekNepZ]

Anyone else watch Numberphile?

 

[Law]

What the hell was your rabbit version?

E: Yes, I know one of the people on numberphile actually!

 

[roytheshort]

Yes, I know one of the people on numberphile actually!

Oh la-de-dah! Look at mister "I know people on numberphile", do you also have tea with the Queen? What colour are her eyes?

 

[Law]

Oh la-de-dah! Look at mister "I know people on numberphile", do you also have tea with the Queen? What colour are her eyes?

Black. Black like the abyss.

 

[roytheshort]

Black. Black like the abyss.

 

[johnwo]

Here's one of my favorite math puzzles (repost of a math.stackexchange post I made):

Hank owns a car. He has been taking good care of his car; In fact, he has been taking such good care of it that the age of Hank, and the age his car combined is 56 years!

Coincidentally his car is twice as old as Hank was when his car was as old as Hank is now.

How old are Hank and his car?

'Tis a nice one!

 

[roytheshort]

What if Hank's a time traveler?

 

[Law]

H+C=56

"Coincidentally his car is twice as old as Hank was when his car was as old as Hank is now."

Hrm...

When the car's age was H, Hanks age was C/2.

That was C-H years ago.

H-(C-H)=C/2
2H-C=C/2
4H=3C

56/7=8

C=32 H=24?

Yeah that works.

E: That was actually really mindducky, it's very hard to translate that question into algebra.

 

[Alice]

So, assuming Hank has been taking care of his car from the very beginning, he really must have been quite attached. I mean, not everyone cares about their car 8 years before they are born.

Oooor Hank is a time traveller. Roy is all too good in these puzzles.

 

[Law]

Ooor Hank bought a used car cause he's only 24 and petrol is expensive plus he's trying to make it as a web-designer so is working from home. He's grown attached to it now, even though it's old and cranky and his mates make fun of it and it scares off his dates. He calls it Calvin because it reminds him of his uncle Calvin who was a smoker and always used to grumble and complain about everything. Calvin, once he settles down he'll get a new one, he'll miss you though, Calvin.

 

[Mercerenies]

Here's an old favorite of mine:

100 pirates (p1, p2, ... p100) are dividing up a treasure consisting of 50 indivisible gold coins of equal worth. The pirates have a total-order hierarchy, i.e. pirate p1 is the head pirate, p2 is a rank lower in the order, p3 lower still, ... The process works like this: The highest ranking pirate who is still alive proposes how he would like to divide the treasure. Then all living pirates (including him) vote on the proposal. If at least half of the pirates alive vote for the proposal, then it is accepted, otherwise the pirate who made the proposal is killed and the process is repeated.

The pirates are perfectly intelligent, logical and rational (see Blue Eyed Puzzle). Each pirate's priorities are, in this order: Survival, wealth (getting the highest number of coins possible), bloodthirstiness (seeing as many pirates killed as possible, other than himself). In other words a pirate will always choose an outcome in which he lives over one in which he dies. Given two outcomes in which he lives, he will choose the one where he gets more coins. And given two outcomes in which he lives and gets the same number of coins he will choose the one in which the highest number of other pirates die.

How will the gold coins be divided?

Source: http://wiki.xkcd.com/irc/Puzzles#Pirates

 

[Law]

That's a really good one. I'm going to suggest we don't post the answers in this topic.

I presume the pirates are also logicians? That is to say 100% perfectly logical.

E: Reread the question, yes it seems they are. (Arrrr)

If there were two pirates with 50 gold pieces to divide. The pirate proposing will always get voted down as the last pirate can ensure he gets all the gold. This leads me to think that perhaps it is always the case that the last pirate ends up with all the gold, not sure... Will think about it.

 

[Aleksandar Gavrilovic]

You and your prisoner friends are in for a LIFE sentence of solitary confinement at the Worlds Worst Prison (tm).
One day you all assemble at the prison cafeteria and get a visit by the prison guard:

"All right, maggots,
All of you 100 prisoners make me sick!
But i'll give you a chance to get out of this prison!
I'll put you all back in solitary confinement, but each day I'll chose one of you at random.
The one I chose will spend a whole day in the Special Room (tm)
I might pick the same guy twice in a row, or pick another person every day, or whatever I feel like!
In the Special Room (tm) you can't change anything except turn the lights ON or OFF.
You're under surveillance so if you change anything else, you'll all be EXECUTED!!!
At any time in the Special Room (tm) you may call for me and tell me that you know FOR A FACT that all 100 of you have already been in the room.
If that happens to be true, I'll let you all GO FREE OUT OF PRISON!
If not, I'll EXECUTE every one of you!
Now... you can talk it over and decide what you're all going to do but let me tell you:
After today none of you will ever see each other again here!
Think of a strategy together, and when you're done, go back to your cells!"

What's your strategy?

 

[Alice]

@Merceneries: I'll think about it, seems pretty interesting. I can tell the last pirate won't get all the gold, because the penultimate pirate would vote for his survival, so at least two survive.

@Aleksandar: now that's interesting, it seems like the sort of task that has multiple valid strategies...? I wonder if I can come up with something...

 

[Law]

I made a mistake I didn't realise proposer votes too. Merc, what happens in a tied vote?

 

[Alice]

I made a mistake I didn't realise proposer votes too. Merc, what happens in a tied vote?

If at least half of the pirates alive vote for the proposal, then it is accepted

Tied vote means that 50% vote for proposal, which is at least half. Unless there's some weird voting system involved, but let's not start this debate again...

Either way, I know the generalised solution now, i.e. how many of P pirates can survive if there are C coins, and how will the coins be divided. Generally, it works like that:

Spoiler

Number of surviving pirates:
- P, if P <= 2C+1
- between 2 and 2C+1, if P > 2C+1; the higher excess pirates to norm pirates ratio ( P-(2C+1) / (2C+1) ), the lower the number of surviving pirates is likely to be

That's how the coins distribution works:

If there are no more than 2C+1 pirates remaining, the dividing pirate (let's normalize him to p1, even if, say, there were technically 10 other pirates before) will give 1 coin to all other odd-numbered pirates, and take all the remaining loot; that's because if the following pirate would use the same strategy, the odd-numbered pirates would be even-numbered and they would get nothing, so, maximizing their wealth, they will vote for the current one. That's because if later pirate has a way of survival, the earlier pirate will only get YES from those pirates that will get more coins than from the latter. There's some really fancy alternation pattern there.

If there are excess pirates, they will have no way of surviving, and thus their wealth will be zero, as well; so, in order to maximize bloodbath (it's not their top priority, but it's still a priority) they'll do their best to get rid of the coins so that fewer pirates would survive, and the more excess pirates compared to surviving pirates there are, the higher are their chances of getting rid of the coins; in such case, the coins division is rather indeterminate, depending on the details some of these might end up in a volcano, or in a barkeeper's purse, or some might be fed to a friendly neighbourhood shark. If the number of coins stabilizes (there are no excess pirates and coins are somewhat safe), we're back to regular case. At least 2 pirates survive, because the higher order pirate will vote for their survival, even if there are no coins at all.

In the case of the task at hand, there are 100 pirates and 50 coins, since there are no more than 101 pirates, we have the easy case where everyone survives and no one gets rid of coins. A bonus task involved having 200 pirates instead, and we have a battle starting with 101 survivors and 99 desperates, with desperates getting ~2 new allies for each coin they get rid of. It's like some sort of zombie infestation battle, in a way.

 

[roytheshort]

Why aren't the pirates irrational? Are you telling me they're not drunk? What sort of pirates are these?

 

[Law]

Alice, I don't fully understand your answer. While I don't doubt it's truth, the "If the second pirate were to copy this strategy" argument doesn't make sense, since there's no reason the second pirate would have to follow the same strategy.

 

[Alice]

Tsk, just because you don't see the reason why the second pirate would follow the strategy, it doesn't mean there isn't one. Also, I decided not to get too elaborate, partially because I wanted to give you guys some fun, mostly because I didn't want to write too much. But since you asked, here's a simple overview of what would happen in the 100 pirates/50 coins case...

Spoiler

If the last pirate followed that strategy, he would share gold with 0 other pirates, get 50 gold and 1:0 votes. What else to ask for?
If the second last pirate followed that strategy, he would share gold with 0 other pirates, get 50 gold and 1:1 votes. The even-numbered pirate would get nothing. It's the most reasonable option for second-last.
If the third last pirate followed that strategy, he would share gold with 1 other pirate (the last), get 49 gold and 2:1 votes. The odd-numbered last pirate would agree, because he knows in the second-last iteration he would get nothing.
If the fourth last pirate followed that strategy, he would share gold with 1 other pirate (the second-last), get 49 gold and 2:2 votes. The odd-numbered second-last pirate would agree, because he knows in the third-last iteration he would get nothing.
If the fifth last pirate followed that strategy, he would share hold with 2 other pirates, get 48 gold and 3:2 votes. The odd-numbered pirates would outvote the even-numbered ones, because they know in the next iteration they would get nothing.

And so on, and so forth. This strategy is the most reasonable to optimize wealth and popularity. Funny, but true.

 

[roytheshort]

If the first one wants to maximize bloodshed why doesn't he just scuttle the ship?

 

[Law]

Roy make another joke and I'll have to throw a sheet over you again.

@Alice: My apologies, I thought you were attempting to give a full proof, rather than just an overview. Your proof makes sense now.

 

[roytheshort]

Roy make another joke and I'll have to throw a sheet over you again.

Your life.

 

[Law]

Your life.

SIgh.

*Throws sheet over Roy*

I'll take the sheet off when you apologise.

 

[roytheshort]

I'm going to apologize for that in like two years.

 

[Yal]

Q: You have a circle with a set radius R, and a set of N smaller circles, all with the same radius r which is <= R. r is chosen so that all N circles can fit in the larger circle without overlapping, and the area that is NOT covered by the N circles is referred to as A.

Assuming you choose r so that to minimize A.
For N=1, this means the smallest possible area A is zero, since with r=R, the whole circle will be covered by the set of small circles.
For N approaching infinity, the smallest possible area A is also zero, since the circles will approximately have the properties of points as they shrink in size.

For what N is the smallest possible A the greatest?
I.e, find the minimum of the discrete function A(N).

 

[johnwo]

Q: You have a circle with a set radius R, and a set of N smaller circles, all with the same radius r which is <= R. r is chosen so that all N circles can fit in the larger circle without overlapping, and the area that is NOT covered by the N circles is referred to as A.

Assuming you choose r so that to minimize A.
For N=1, this means the smallest possible area A is zero, since with r=R, the whole circle will be covered by the set of small circles.
For N approaching infinity, the smallest possible area A is also zero, since the circles will approximately have the properties of points as they shrink in size.

For what N is the smallest possible A the greatest?
I.e, find the minimum of the discrete function A(N).

Wouldn't that be N=2?
As R/2 = r would give two circles that would cover exactly 50% of the enclosing circle, and N >= 3 would give 1+(2/3)*√3 <= 1-A <= 1, which indicates that N=2 is the right answer.


I might be missing the point totally, as my main laguage isn't english, thus I often have trouble when trying to interpret math-questions and such; But if I did interpret the question correctly, I'm pretty certain my answer is correct!

Cheers!

 

[seanm]

The 3 Door Monty Hall problem is always fun to talk about, and no one likes the answer aha.

Say you are on a game show there are 3 doors in total. 2 have goats behind them, 1 has a new car behind it.

You are allowed to pick 1 door.
The host then opens one of the other doors to reveal a goat.
The host allows you to pick between the 2 remaining doors.

Should you switch to the other door, or remain on the door you've already selected?
Does it matter?

 

[johnwo]

The 3 Door Monty Hall problem is always fun to talk about, and no one likes the answer aha.

Say you are on a game show there are 3 doors in total. 2 have goats behind them, 1 has a new car behind it.

You are allowed to pick 1 door.
The host then opens one of the other doors to reveal a goat.
The host allows you to pick between the 2 remaining doors.

Should you switch to the other door, or remain on the door you've already selected?
Does it matter?

My answer:

Spoiler: Answer

You switch!

When picking your door at the start of the "game" you have a 1/3 chance of picking the car.
When you've picked a door, the host reveals a door with a goat behind it.

Since you only have a 1/3 chance of picking the car at the start, you have a 2/3 chance of picking a goat. If you pick a goat at the start and the host reveals another door with a goat, you will win the car if you switch.
Therefore, you have a 2/3 chance of winning the car if you switch, which is a greater chance of a win than if you stick with your first choice.

If you're unlucky and pick the car at the start, you'll still end up with a goat, which I'd say is also pretty sweet! xD

I put it in spoiler-tags as to not ruin it for anyone that wants to try to work it out themselves...!

Cheers!

 

[Yal]

Wouldn't that be N=2?

Nice catch, I didn't expect anyone to solve that without first having to find the optimal circle placement for N=3 and N=4. x3

 

[Alice]

Answering to the riddle from that old post...

What's your strategy?

Well, I found a kinda sorta reliable strategy to find out if all the other cellmates were in the prison *eventually*, but it's somewhat inefficient and executing it would probably end up lasting longer than the life sentence. Dunno what would be the better solution.

Generally, each prisoner has assigned a number from 1 to 100. Then, if prisoner 1 is picked for the first day, and every 100th day after that, he sets the light on. Otherwise, he sets it off. Prisoner 2 does the same when picked for second and every 100th day after that, etc. Then, every time the light is lit, the next prisoner can figure out which other prisoner has been previously there. Repeating that ad infinitum, assuming the prisoner selection is properly random, some prisoner eventually ought to come after all the others lit the light, and tell for a fact that all of them has been in Secret Room™.

Maybe not the best solution, but works. And let's face it, if the guard is a complete jerk and doesn't want to get the prisoners out ever, he'll just consistently refrain from picking a particular prisoner, making the release condition impossible to meet ever.

 

[Aleksandar Gavrilovic]

Answering to the riddle from that old post...

It's very good and on the right track, but it can be even better! The best solution I found had them out of prison in around 10-20 years

 

[Hiznopellagio]

I really love these kind of topics (even though most of the time I can't solve them). It looks like it's mostly filled with riddles though, so perhaps rename the topic to that? Just not to limit the puzzles to mathematics ones.

(I can just make a new Riddles topic, but that'd be a waste)

 

[Alice]

Hmm... I guess my solution can be scaled a bit, in a way. So, for example, it might not be split into days, but maybe weeks, months or sets of 100 days. In other words, whenever prisoner 1 enters during the first 100 days, they turn on the light, and all other prisoners who enter in the remaining part of the first 100 days, know for sure prisoner 1 has been there. Then, on 101st day, if prisoner other than 2 enters the Secret Room™, they turn off the light; otherwise, the light stays on, and subsequent prisoners know that prisoner 2 entered during their day. Days 201-300 are for prisoner 3, and so on; after prisoner 100 batch, prisoner 1 enters their watch once again.

That would still require 30-ish years under particularly good conditions, and it would probably need a few 100x100 iterations, making it a few times more (but a millenium should be most likely enough, I guess). I dunno what sort of black magic can bring it down to 10-20 years.

 

[Aleksandar Gavrilovic]

There's even a strategy which finishes in under 10 years on average!
Here's the run-down on the most popular strateges (spoiler alert)

 

[johnwo]

There's even a strategy which finishes in under 10 years on average!
Here's the run-down on the most popular strateges (spoiler alert)

First off... I was SERIOUSLY woundering if the spam-bot "filter" had already failed. Just reading that post, with no context in mind, sounds like the typical spam-bot post...
I was crossing fingers and toes, just hoping that the hyperlink was pointing to some generic scam-site...! xD

Secondly... What an awesome find! That paper was really fun to read, and it proves that, although trivial, man (as in mankind) are still stoked on finding the best, most effective solutions to problems. Great share!

 

[johnwo]

Classic riddle

Move one DIGIT to make this equation correct:

62 - 63 = 1

Just to clarify:

• You can't change/add digits/symbols.

Good luck!

 

[seanm]

Spoiler

63-63=0 ?

 

[Yal]

Move one DIGIT to make this equation correct:

Spoiler

2 - 63 = -61? You never said anything about adding non-digit characters as part of the solution.

 

[roytheshort]

Spoiler

2^6 - 63 = 1