With all of the paradoxical and unintelligible threads arising from the thread on the origin of the universe, maybe we need at least one thread devoted to puzzling science/math questions that actually have answers.
One answerable question brought up in one of the universe thread involves two goats and a car.
This is a pretty lame way to start a puzzle thread, but here goes:
You're on a game show. There are three doors, 1, 2, & 3. Behind one of these doors is a new car, and behind the other two are goats.
The host asks you to pick a door. So you pick door #1. The host then opens up door #2, and out walks a goat. He then gives you the option of switching from door #1 (your original choice) to door #3. Should you switch?
Yes. But I don't feel like explaining why (just write out all possible endings and use common sense. If that does not work, the solution is on the wiki page for the monty hall paradox.).
---
A group of people having catagorical eye colors live on an island. They are all perfect logicians; if a conclusion can be logically deduced, they will do it. Assume no one knows the color of their eyes. Every night at 12:00am, a boatstops at the island. Any islanders who have logically deduced the color of their own eyes then leave the island, and the rest must stay. Everyone can see everyone else at all times and maintains a count of the number of people they see with each color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph, but nothing further.
On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (who has green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and 1 with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.
The Guru is allowed to utter one sentence over all their endless years on the island. Standing before the islanders on one given day, she says:
"I can see someone who has blue eyes."
Who leaves the island, and on what night?
There are no mirrors or reflecting surfaces. It is not a trick question, and the answer is logical. It doesn't depend on tricky wording or anyone lying or guessing, and it doesn't involve people doing something silly like creating a sign language. The Guru is not making eye contact with anyone in particular. She's simply saying "I see at least one blue-eyed person on this island who isn't me."
Yes. But I don't feel like explaining why (just write out all possible endings and use common sense. If that does not work, the solution is on the wiki page for the monty hall paradox.).
lol, I guess I'll give you *partial credit* for that answer
As for your problem, I suspect that all the blue eyed people will leave the island on the 100th night.
If you grind it out, in the simple case where there's one blue eye, one brown eye, and the guru, the blue eye leaves the first night. If there are two blue eye, two brown eye, and the guru, the blue eyes leave the second night. If there's three blues, three browns, and a guru, the blues leave the third night. And so on and so on.
I'm too lazy to write the inductive proof, but...ya, I'd bet bet my wiener on it.
Yes, correct. I'll give you 50% for getting the correct answer, 20% for asking the followup, and 30% pending you pass a lie detector test about not looking up the solution on the internet
As for the followup, this has bothered me ever since I learned of this problem. In a sense, I feel like the guru is necessary for the base case of the induction. Without the guru's line being uttered, there would be no way for the induction ball to get rollowing. Any inductive proof I've seen of this problem always incorporates the guru's line.
In another sense, since everyone already knew what the guru said, why would it make a difference? Well if we posit that these people were put on the island a year ago, then it seems as if according to this, the blues would all be off 265 days ago. If they've been there "forever" then the question is impossible/pointless to ask.
Honestly, I don't know if the followup fits this thread's criteria. Do you, Binge Artist, have anything more to say on the followup question? I've thought about it a lot before, and cannot reason it to be anything but me either missing a hidden contradiction somewhere, or this problem just being impossible to even ask.
Honestly, I don't know if the followup fits this thread's criteria. Do you, Binge Artist, have anything more to say on the followup question? I've thought about it a lot before, and cannot reason it to be anything but me either missing a hidden contradiction somewhere, or this problem just being impossible to even ask.
For example, after watching all the blue eyed guys leave, why didn't the rest just telepathically put the phrase "I see brown eyes" into the guru's mouth, ya know?
I think the answer to this question can be found by looking at a simple case, where there are three people: Two blue-eyed logicians and a green-eyed (but it doesn't matter) guru.
Now, just from the get-go, before the guru says anything, what can the logicians write on their "fact sheets"?
First, each can write: "There is a blue eye." and "There is a green eye".
After the guru speaks "I see a blue eye", a NEW fact can be added to their lists: "The other logician knows that there is a blue eye."
In other words, in your puzzle, before the guru spoke, it was true that everybody knew that "there is a blue eye". However, it wasn't true that Bill could say that "Carl knows that Dave knows that Eric knows...that Zed knows...that I know there is a blue eye."
Or, in sum, the guru's statement allowed everyone to add a statement (or statements) to their list. That is, it added to everyones "fact sheets".
Or, to sum it up in a clever way: "It's not what you know; it's what you know that other people know you know that other people know..."
But, ya, I suppose my question wasn't too clearly defined, so I'll try to think of a better one. Hopefully, I'll be able to think of one as good as what you posted!
^^^ What an aggravating problem... I glanced in here last night and then spend the better part of an hour playing with that.
Anyways, I finally figured out the answer. It's trivial to show it doesn't work for mod3 in 3 dimensions; in 2d it's a little tricky:
NSFW:
Consider two circles of unit radius, centered one unit apart (at points A and B), so they each pass through the other's center. f(A) and f(B) must be different, since they're one unit apart. The circles intersect at two points, C and D. Both those points are each a unit distance away from A and B by construction, so f(C)!=f(A) and f(C)!=f(B), with the same thing for f(D). But since f(A) & f(B) must be two different values, this only leaves one possible value for f(C) and f(D). Hence f(C)=f(D). If you look at the points we've constructed, they make up two side-by-side equilateral triangles.
Code:
A
/|\
/ | \
C | D
\ | /
\|/
B
What we've been doing is essentially building up part of a hexagonal lattice of points; continuing to generate points equidistant to pairs of points in the graph (like A&C) would eventually get us the whole lattice. But that won't help us; it *is* possible to consistently define a function mod 3 on the lattice that's not equal on neighboring elements.
What *will* work is to consider a rotation of the above graph. (I thought about rotation very early, dismissed it, and then spend probably 20 min screwing around with inter-lattice points and/or trying to find angles that'd give an 'extra-lattice' unit-distance connection, before realizing you can easily do the same thing with rotation.) Rotate the whole construction around point C, about 30 degrees, just enough so that the rotated point D' is exactly one unit away from point D. The result is hard to draw w/ascii, but easy to imagine -- you've got two diamonds jutting out from C, with the "ends" D and D' being one unit apart. Now we showed above that f(C)=f(D), and the same reasoning shows f(C)=f(D'). So f(D)=f(D'). But D and D' are a unit apart! QED.
I also played with trying to find out what number mod n you could create such a function for. Clearly it's possible for some n: construct a lattice, either hexagonal or square, on the plane. Set the lattice spacing to be less than 1, so the maximum diagonal distance 'across' a cell is exactly 1 (there's a little bit of wiggle room with the hexagonal lattice; with the square one it has to be precisely 1.) Then you have f(x)=constant in each cell. Since the cells are sized so no two points in them are a unit distance apart, the problem reduces to consistently "coloring" the cells. It's slightly more complicated than the normal coloring problem, since cells have to be a different "color" (value of f(x)) not only from their adjacent cells, but also from the next ones over. In the hexagonal lattice, the hexagons are just under 1 unit across, so you can "reach" any hexagon "within two jumps" -- i.e. each cell can't be the same as any cell touching it, or any cell touching a cell touching it. In the square lattice, it's almost the same, but by setting the spacing to be exactly 1/sqrt(2) you can make it so cells can be the same color as the cell two diagonals away.
Clearly for a hexagonal grid you need at least 7 colors (i.e. f being mod 7) to get it to work -- a given "center"cell and all its 6 adjacent surrounding cells are obviously each within 2 jumps of each other, so must all be different values. Surprisingly, mod 7 seems to be enough -- I wrote out part of a lattice, and ran into no problems. I got tired of filling in the lattice before I got a self-repeating chunk, but it looks like it's headed that way, so I'm pretty sure. (For the square grid 7 doesn't work; you need at least 8, but I didn't check to see if was enough.)
Anyways, that leaves me with a question for you BingeArtist -- do you know what the number n is that lets you have such a function mod n on the plane? It's got to be above 3. But my method above can only prove it's less than 7. However I can easily imagine getting a smaller n by using an f(x) that's not defined on a regular lattice -- you could use an irregular lattice or some sort of weird nonrepetitive Penrose tiling-like one (probably I should have been calling these "tilings" all along), or -- better yet -- use bizarre unmeasurable sets for the level sets of f(x).
Anyways, do you know if any of those things are possible? Or can you prove that there's no such f for mod 4/5/6? And is there a known generalization to d dimensions? If you know of some resources covering this, I'd appreciate it if you could point me to them. Or is this one of those one-off problems that float around on lists (like Redleader's q)?
Problem: Let's assume we have a number of hostages. We'll say that there are 17, though nothing about the number 17 matters - I pulled it out of a hat. Now they are about to potentially meet death via an execution squad. All 17 have their heads shaved and either a smilely or a frown written on the back of their heads. The assignment of s and s is completely random - it would be 1 and 16 , 6 and 11 , etc. Furthermore, this is done as the hostages are sedated, so there is no "trick" about them "feeling" what was written.
The hostages are lined up facing forward, in a row. Meaning that 2 can see (the back of the head of) 1, 17 can see the back of heads 1-16, and the middle can be sensibly filled in. Each will be asked, in turn, what is on the back of their head. If correct, they live. If wrong, they are executed. The questioning begins with hostage 17 (who can see 1-16) and moves forward, ending with hostage 1. So, for example, hostage 17 could say , when he really has and it's lights out! Assume all hostages can hear everything said during the execution phase.
The hostages are allowed to strategize about "anything" before the application of s and s, but the only words allowed to be uttered post application would be "smiley" or "frown," and this is only in response to the assassin's questioning. They are all individually isolated from each other between the time of the application and the time of the actual game.
Question: How many hostages will live, based on optimal strategizing alone? And what is this strategy?
The guy in the back of the line will say if the number of 's he sees is even, and if the number of 's he sees is odd. So it seems that the only guy risking his ass is the guy in the back.
^Ah, good. 100%. Optimal stategy results in only 1 death max, and that possibly being the guy in the back. I realise now that I wrote the problem terribly, but I think you got the jist of it.
It was only after doing as was done below that I realised that if I just starred at this and used common sense to infer the cancelations... I feel dumb now that I actually got the answer. But in any case, here's the rigorous way of going at it, which does add in uniqueness of the solution (note last line in the first array is pointless):
written on the back of their heads. The assignment of 
