To Infinity and Somewhat Past That!
August 28, 2012 5:26 AM Subscribe
Are there as many odd numbers as there are all numbers? Can one infinity be bigger than another? TED Ed and Minute Physics both take a look at some of the mind boggling realities of Infinity.
∞ + 1
posted by three blind mice at 5:35 AM on August 28, 2012 [3 favorites]
posted by three blind mice at 5:35 AM on August 28, 2012 [3 favorites]
When Georg Cantor came up with this stuff it was quite controversial and even held to be counter to the existence of god. Which is why to this day some fundamentalists are leary of set theory.
posted by TedW at 5:44 AM on August 28, 2012 [9 favorites]
posted by TedW at 5:44 AM on August 28, 2012 [9 favorites]
Years ago I watched a program on PBS that tried to explain different infinities. It made my brain hurt.
posted by tommasz at 6:00 AM on August 28, 2012
posted by tommasz at 6:00 AM on August 28, 2012
I just stumbled onto a neat infinity-related puzzle on the blog Futility Closet:
Imagine a plane table of infinite extent. Attached perpendicularly to the table is a rod of finite length, and above that, attached by a hinge, is a second vertical rod, this one infinitely long.
Operate the hinge. What happens? The infinite rod descends freely through the first 90 degrees, until it’s parallel to the tabletop. But it can’t go beyond this, because then at some point the solid rod would intersect the solid table.
Thus it’s impossible to “rest” an infinite rod on an infinite plane. “And so, you have the curious phenomenon of the hinged rod being supported at only one end!”
posted by martinrebas at 6:05 AM on August 28, 2012 [17 favorites]
Imagine a plane table of infinite extent. Attached perpendicularly to the table is a rod of finite length, and above that, attached by a hinge, is a second vertical rod, this one infinitely long.
Operate the hinge. What happens? The infinite rod descends freely through the first 90 degrees, until it’s parallel to the tabletop. But it can’t go beyond this, because then at some point the solid rod would intersect the solid table.
Thus it’s impossible to “rest” an infinite rod on an infinite plane. “And so, you have the curious phenomenon of the hinged rod being supported at only one end!”
posted by martinrebas at 6:05 AM on August 28, 2012 [17 favorites]
I remember a high school math teacher of mine who explained how there were different "Orders of Infinity," on of those tangents high school math teachers tend to take in between solving problems on the chalkboard. When he said, "Orders of Infinity," he always opened his eyes wide and said it slowly and with emphasis.
He explained it succinctly by noting how if you multiply an odd number by an odd number, you get an odd. But if you multiply an even number by either an even or an odd, you always get an even! So you'd think there'd be more evens than odds, since they're produced by 2 cases when odds are only produced by 1. But there's an infinite amount of each! Cantor came up with orders of infinity to explain this. The teacher closed his tangent by stating that Cantor eventually went insane.
I guess the teacher was pretty smart, because he retired from teaching around the age of 55 due to success with his financial investments.
posted by victory_laser at 6:13 AM on August 28, 2012 [5 favorites]
He explained it succinctly by noting how if you multiply an odd number by an odd number, you get an odd. But if you multiply an even number by either an even or an odd, you always get an even! So you'd think there'd be more evens than odds, since they're produced by 2 cases when odds are only produced by 1. But there's an infinite amount of each! Cantor came up with orders of infinity to explain this. The teacher closed his tangent by stating that Cantor eventually went insane.
I guess the teacher was pretty smart, because he retired from teaching around the age of 55 due to success with his financial investments.
posted by victory_laser at 6:13 AM on August 28, 2012 [5 favorites]
Thus it’s impossible to “rest” an infinite rod on an infinite plane.
It is also impossible to construct an infite rod or an infinte plane.
posted by sour cream at 6:17 AM on August 28, 2012 [18 favorites]
It is also impossible to construct an infite rod or an infinte plane.
posted by sour cream at 6:17 AM on August 28, 2012 [18 favorites]
Also, if the rod is of infinite length then moving the hinge will result in an arbitrary point an infinite distance from the hinge moving infinitely faster than the speed of light.
posted by Just this guy, y'know at 6:22 AM on August 28, 2012 [21 favorites]
posted by Just this guy, y'know at 6:22 AM on August 28, 2012 [21 favorites]
This kind of stuff is among my favorites in math: it's a little vertigo-inducing, but the one-to-one matching principle doesn't require any technical background to understand.
posted by weston at 6:23 AM on August 28, 2012 [2 favorites]
posted by weston at 6:23 AM on August 28, 2012 [2 favorites]
When Georg Cantor came up with this stuff it was quite controversial and even held to be counter to the existence of god. Which is why to this day some fundamentalists are leary of set theory.
Ha! That's crazy. Any decent marketer would just start referring to God as the "infinity of infinities", the infinite set of all infinite things, and then the problem's solved and we're back to "there's no escaping God". Only now with Math!
posted by Rory Marinich at 6:27 AM on August 28, 2012 [4 favorites]
Ha! That's crazy. Any decent marketer would just start referring to God as the "infinity of infinities", the infinite set of all infinite things, and then the problem's solved and we're back to "there's no escaping God". Only now with Math!
posted by Rory Marinich at 6:27 AM on August 28, 2012 [4 favorites]
Any decent marketer would just start referring to God as the "infinity of infinities", the infinite set of all infinite things, and then the problem's solved and we're back to "there's no escaping God". Only now with Math!
"I am the Aleph-Null and the Aleph-One."
posted by kmz at 6:31 AM on August 28, 2012 [7 favorites]
"I am the Aleph-Null and the Aleph-One."
posted by kmz at 6:31 AM on August 28, 2012 [7 favorites]
"One concept corrupts and confuses the others. I am not speaking of the Evil whose limited sphere is ethics; I am speaking of the infinite." JL Borges
posted by jet_manifesto at 6:35 AM on August 28, 2012 [3 favorites]
posted by jet_manifesto at 6:35 AM on August 28, 2012 [3 favorites]
I've been doing some thinking about Skolem's Paradox in the context of the transfinite cardinals. I've come to the "heretical" conclusion that speaking about "size" in the context of the transfinite cardinals doesn't make as much sense as is traditionally supposed by set theory. I don't have any close to mathematical proofs, just hunches. If anyone is interested, I tried to spell things out here. Long story short, I believe that all Cantor's diagonal argument shows is that there's no 1-1 mapping from N to its powerset on pain of contradiction... we should suppose nothing more about cardinality.
posted by Wash Jones at 6:36 AM on August 28, 2012 [1 favorite]
posted by Wash Jones at 6:36 AM on August 28, 2012 [1 favorite]
Ha! That's crazy. Any decent marketer would just start referring to God as the "infinity of infinities", the infinite set of all infinite things, and then the problem's solved and we're back to "there's no escaping God". Only now with Math!
You'd be depressed how much rubbish like this litters the lunatic fringes of set-theory...
posted by Omission at 6:40 AM on August 28, 2012 [1 favorite]
You'd be depressed how much rubbish like this litters the lunatic fringes of set-theory...
posted by Omission at 6:40 AM on August 28, 2012 [1 favorite]
my infinity...
is bigger than yours, friend
mine keeps going,
further past where yours don't end
and my forever
leaves yours far behind
so you just sit back, friend
and watch my spiral unwind
posted by flapjax at midnite at 6:48 AM on August 28, 2012 [2 favorites]
is bigger than yours, friend
mine keeps going,
further past where yours don't end
and my forever
leaves yours far behind
so you just sit back, friend
and watch my spiral unwind
posted by flapjax at midnite at 6:48 AM on August 28, 2012 [2 favorites]
Cantor had a hard time. His orders of infinity were rejected by the mathematicians of his time and he was institutionalized. Watch this documentary!
posted by Obscure Reference at 6:48 AM on August 28, 2012 [2 favorites]
posted by Obscure Reference at 6:48 AM on August 28, 2012 [2 favorites]
Rory, the problem there is that you then have the infinite set of infinite sets of infinite things -- the infinity of Gods. And then you have an infinite set of those.
That darn infinity -- it's like it never ends!
posted by Malor at 6:53 AM on August 28, 2012
That darn infinity -- it's like it never ends!
posted by Malor at 6:53 AM on August 28, 2012
Okay, for fun, a puzzle a grad school buddy told me:
Infinitely many mathematicians are locked in a dungeon by an evil wizard. The evil wizard makes them stand in a line, with one person in the back, a person in front of him, a person in front of them, etc, each person facing towards the front.posted by Elementary Penguin at 6:53 AM on August 28, 2012 [2 favorites]
The wizard puts a hat on the head of each person, which can be of one of infinitely many colors. Each person can see all the hat colors of the people in front of them, but not their hat, nor the hats of the people behind them. Then, starting from the back, he asks each person in turn what color their hat is. If they are correct, they live, otherwise they die. In either event, everyone can hear each answer, and whether the speaker lives or dies.
The mathematicians are given time to figure out how they should guess before they are lined up.
What is the best possible system? In other words, what method of guessing guarentees as many mathematicians live as possible?
I believe that all Cantor's diagonal argument shows is that there's no 1-1 mapping from N to its powerset on pain of contradiction... we should suppose nothing more about cardinality.
Whether a bijection exists between two sets is literally the definition of whether their cardinality is the same.
See also.
posted by kmz at 6:59 AM on August 28, 2012 [3 favorites]
Whether a bijection exists between two sets is literally the definition of whether their cardinality is the same.
See also.
posted by kmz at 6:59 AM on August 28, 2012 [3 favorites]
If there are infinitely many colors, it takes an infinitely long time to describe any color. Therefore all the mathematicians will survive, because they will never get past the guy at the back.
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 7:00 AM on August 28, 2012 [12 favorites]
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 7:00 AM on August 28, 2012 [12 favorites]
Well, Penguin, the first solution that comes to mind is for Mathematician #1 to guess the color of the hat immediately in front of him. He dies, but then #2 repeats that guess and lives. #3 dies, #4 lives, and so on. That solution would save half of them, and any solution that saves an infinite number of people must be correct.
Actually, because of the weirdness of infinity, I suspect any system that saved any fraction whatsoever of the mathematicians would be identical, so if every mathematician made a random guess, just as many would be saved.
posted by Malor at 7:00 AM on August 28, 2012 [7 favorites]
Actually, because of the weirdness of infinity, I suspect any system that saved any fraction whatsoever of the mathematicians would be identical, so if every mathematician made a random guess, just as many would be saved.
posted by Malor at 7:00 AM on August 28, 2012 [7 favorites]
“And so, you have the curious phenomenon of the hinged rod being supported at only one end!”
It's worth noting that, naturally, the infinite rod only has one end.
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 7:02 AM on August 28, 2012 [13 favorites]
It's worth noting that, naturally, the infinite rod only has one end.
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 7:02 AM on August 28, 2012 [13 favorites]
Thus it’s impossible to “rest” an infinite rod on an infinite plane.
Just lay it on top of the plane.
The impossible thing here is to have two non-parallel lines in a plane also be non-intersecting. You could do this on a hyperbola.
posted by DU at 7:03 AM on August 28, 2012
Just lay it on top of the plane.
The impossible thing here is to have two non-parallel lines in a plane also be non-intersecting. You could do this on a hyperbola.
posted by DU at 7:03 AM on August 28, 2012
If there are infinitely many colors, it takes an infinitely long time to describe any color. Therefore all the mathematicians will survive, because they will never get past the guy at the back.
NO FUN.
posted by Elementary Penguin at 7:04 AM on August 28, 2012 [1 favorite]
NO FUN.
posted by Elementary Penguin at 7:04 AM on August 28, 2012 [1 favorite]
Whether a bijection exists between two sets is literally the definition of whether their cardinality is the same.
I know, I know... I'm an off-the-rails-batshit-crazy people listening to AM radio when I'm not trainspotting. Point taken, point taken. I'm just thinking that a bijection between N and something shouldn't be what we base cardinality on.
I'll go back to decoding the hidden messages I see in the digits of the phonebook now -- in the hidden cave I have that the government hasn't found yet.
posted by Wash Jones at 7:06 AM on August 28, 2012 [1 favorite]
I know, I know... I'm an off-the-rails-batshit-crazy people listening to AM radio when I'm not trainspotting. Point taken, point taken. I'm just thinking that a bijection between N and something shouldn't be what we base cardinality on.
I'll go back to decoding the hidden messages I see in the digits of the phonebook now -- in the hidden cave I have that the government hasn't found yet.
posted by Wash Jones at 7:06 AM on August 28, 2012 [1 favorite]
If there are infinitely many colors, it takes an infinitely long time to describe any color.
This is like how it takes an infinitely long time to specify any number.
posted by DU at 7:07 AM on August 28, 2012 [1 favorite]
This is like how it takes an infinitely long time to specify any number.
posted by DU at 7:07 AM on August 28, 2012 [1 favorite]
s/number/integer/
But there's so many other things wrong with that objection to infinite colors, I could have used to the reals too. Map the infinite colors to the reals and you can still specify many colors with less than infinite information. .5, for instance, would be a color.
posted by DU at 7:08 AM on August 28, 2012
But there's so many other things wrong with that objection to infinite colors, I could have used to the reals too. Map the infinite colors to the reals and you can still specify many colors with less than infinite information. .5, for instance, would be a color.
posted by DU at 7:08 AM on August 28, 2012
With no beginning and no end, the only "location" on an infinitely long line would be the exact middle, right? Same for infinite volume- we would be forever at the exact center. All of us at once (assuming we are occupying the same infinite volume.)
posted by Phyllis Harmonic at 7:09 AM on August 28, 2012 [1 favorite]
posted by Phyllis Harmonic at 7:09 AM on August 28, 2012 [1 favorite]
DU is right. The guy at the back could certainly choose an infinitely complex irrationally-described color though. That would be a good strategy!
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 7:10 AM on August 28, 2012
posted by East Manitoba Regional Junior Kabaddi Champion '94 at 7:10 AM on August 28, 2012
But, ultimately, the solution where no mathematicians die saves just as many mathematicians as saving half.
posted by Malor at 7:11 AM on August 28, 2012 [4 favorites]
posted by Malor at 7:11 AM on August 28, 2012 [4 favorites]
The best possible system is for the first mathematician to describe the color of his own hat thusly, while all the other mathematicians listen very carefully:
"My hat is sort of [color of the hat in front of him], but with a tint of [color of the hat 2 spaces in front of him], except that in the right light it looks like [color of the hat 3 spaces in front of him], only a bit [color of the hat 4 spaces in front of him]ish..." and so forth.
None of the mathematicians will die, because it will take infinitely long for the first one to finish describing his own hat.
posted by ook at 7:11 AM on August 28, 2012 [4 favorites]
"My hat is sort of [color of the hat in front of him], but with a tint of [color of the hat 2 spaces in front of him], except that in the right light it looks like [color of the hat 3 spaces in front of him], only a bit [color of the hat 4 spaces in front of him]ish..." and so forth.
None of the mathematicians will die, because it will take infinitely long for the first one to finish describing his own hat.
posted by ook at 7:11 AM on August 28, 2012 [4 favorites]
Yes Malor, but unlike the traditional formulation, this question allows for infinitely many hat colours, not a binary choice of hats. And since we can order certain infinities as being relatively larger or smaller than others, I interpret the request to "guarentees as many mathematicians live as possible" as seeking an answer with the highest possible cardinality.
I don't have a better answer, though.
posted by ceribus peribus at 7:12 AM on August 28, 2012
I don't have a better answer, though.
posted by ceribus peribus at 7:12 AM on August 28, 2012
Clarification: You only get to say one color. If you say anything else, you die.
Also, we are making the ridiculous assumption that wizards exist, and that they hate mathematicians.
Wizards clearly hate physicists
posted by Elementary Penguin at 7:14 AM on August 28, 2012 [3 favorites]
Also, we are making the ridiculous assumption that wizards exist, and that they hate mathematicians.
Wizards clearly hate physicists
posted by Elementary Penguin at 7:14 AM on August 28, 2012 [3 favorites]
Infinity is not a number. Paradoxes that treat it as though it is are not really paradoxes at all.
posted by Decani at 7:14 AM on August 28, 2012 [7 favorites]
posted by Decani at 7:14 AM on August 28, 2012 [7 favorites]
But the cardinality of surviving mathematicians is demonstrably the same as the original number of mathematicians; it can't be more. And it can't be less, because you can draw a line from every pre-question mathematician to every survivor.
posted by Malor at 7:14 AM on August 28, 2012
posted by Malor at 7:14 AM on August 28, 2012
I'm going to put the solution in my profile, to save anyone who cares the effort of Googling for it.
posted by Elementary Penguin at 7:15 AM on August 28, 2012 [2 favorites]
posted by Elementary Penguin at 7:15 AM on August 28, 2012 [2 favorites]
The teacher closed his tangent by stating that Cantor eventually went insane.
What better way to excite kids about a subject than intimate its dark powers?
"I don't know if I dare expose you to the secrets of Emily Dickinson's poetry. It's been known to drive men to madness!"
posted by Egg Shen at 7:16 AM on August 28, 2012 [5 favorites]
What better way to excite kids about a subject than intimate its dark powers?
"I don't know if I dare expose you to the secrets of Emily Dickinson's poetry. It's been known to drive men to madness!"
posted by Egg Shen at 7:16 AM on August 28, 2012 [5 favorites]
Now I have to reload Elementary Penguin's profile page every half second so that I can post the answer here as though I thought of it just in time
posted by ook at 7:19 AM on August 28, 2012
posted by ook at 7:19 AM on August 28, 2012
---The teacher closed his tangent by stating that Cantor eventually went insane.
What better way to excite kids about a subject than intimate its dark powers?
I seem to remember that in secondary school Maths class we did notice that the lives of many mathematicians ended with "and he eventually went mad".
posted by EndsOfInvention at 7:20 AM on August 28, 2012
What better way to excite kids about a subject than intimate its dark powers?
I seem to remember that in secondary school Maths class we did notice that the lives of many mathematicians ended with "and he eventually went mad".
posted by EndsOfInvention at 7:20 AM on August 28, 2012
Thus it’s impossible to “rest” an infinite rod on an infinite plane.
I can usually rest unless there's a baby crying on the infinite plane.
posted by azaner at 7:20 AM on August 28, 2012 [3 favorites]
I can usually rest unless there's a baby crying on the infinite plane.
posted by azaner at 7:20 AM on August 28, 2012 [3 favorites]
None of the mathematicians will die, because it will take infinitely long for the first one to finish describing his own hat.
Are the mathematicians all immortal as well? Dying in a dungeon waiting for a guy to finish describing the color of his hat is pretty much the same as dying in a dungeon executed by an evil wizard.
posted by Copronymus at 7:20 AM on August 28, 2012 [3 favorites]
Are the mathematicians all immortal as well? Dying in a dungeon waiting for a guy to finish describing the color of his hat is pretty much the same as dying in a dungeon executed by an evil wizard.
posted by Copronymus at 7:20 AM on August 28, 2012 [3 favorites]
oh great he posted the answer and I do not understand a single word of it.
What is a "hattening"?
posted by ook at 7:24 AM on August 28, 2012 [1 favorite]
What is a "hattening"?
posted by ook at 7:24 AM on August 28, 2012 [1 favorite]
Added a parenthetical that might clarify things?
(a hattening is a possible assignment of hats to all the mathematicians. Meant to be a play on coloring)
posted by Elementary Penguin at 7:26 AM on August 28, 2012
(a hattening is a possible assignment of hats to all the mathematicians. Meant to be a play on coloring)
posted by Elementary Penguin at 7:26 AM on August 28, 2012
I thought the solution would be that since an infinitely long has no beginning or end it's impossible for someone to actually be the last in line.
posted by vuron at 7:26 AM on August 28, 2012
posted by vuron at 7:26 AM on August 28, 2012
Any set can be well-ordered. In other words, there is a way of defining "a < b" so that any subset of the set will have a least element.
posted by Elementary Penguin at 7:28 AM on August 28, 2012 [3 favorites]
posted by Elementary Penguin at 7:28 AM on August 28, 2012 [3 favorites]
The hats puzzle was given to me by one of my favourite supervisors in the Cambridge maths tripos -- it's hard, people =) It's intimately related to the existence of an non-measurable set, for those of you who know what that means.
If you want an easier one, how well can you do with ten mathematicians?
posted by katrielalex at 7:28 AM on August 28, 2012 [1 favorite]
If you want an easier one, how well can you do with ten mathematicians?
posted by katrielalex at 7:28 AM on August 28, 2012 [1 favorite]
Malor: you can certainly do much, much better than 50%, it's just a question of how many "infinite" operations you're permitted and if you're allowed to assume some agreed-upon mapping from the colors into some other algebraic structure.
Here's a simple, extremely suboptimal example. Suppose we can map the colors into Z. Mathematician #0 announces a hat color of #1's hat color + #2's hat color. Mathematician #0 dies. Mathematician #1 can see #2's hat color, and announces a hat color of #0's answer - #2's hat color. Mathematician #2 announces a hat color of #0's answer - #1's answer. #1 and #2 survive, then the cycle repeats with #s 3, 4, and 5. This gets you to 2/3rd.
Call that a 2-lookahead strategy. It works for 3-lookahead as well: #0 says #1+#2+#3, #1 says #0's answer - (#2+#3), #2 says #0's answer - (#1's answer + #3), #3 says #0's answer - (#1's answer + #2's answer)...and I think you can see that for any finite N an N-lookahead strategy will get you an (N-1)/N survival rate.
Whether you can extend N to infinity is trickier and brings into play other assumptions, like whether or not the mathematicians get to perform an infinite amount of calculations and whether or not they can communicate a number with an infinite number of digits; the latter is somewhat problematic for the puzzle in the event then it's trivial to save all but the first mathematician, since all the first mathematician has to do is read off everyone's color as that first hat color and the rest will go free.
The general principle here is to realize that with an infinite list of mathematicians facing "forward" and the list drained from the "back" the only thing that changes from one mathematician to the next is whatever information the previous mathematicians' answers supplied to the subsequent mathematicians, and that it's imperative to put as much information into those answers as possible.
posted by hoople at 7:31 AM on August 28, 2012 [6 favorites]
Here's a simple, extremely suboptimal example. Suppose we can map the colors into Z. Mathematician #0 announces a hat color of #1's hat color + #2's hat color. Mathematician #0 dies. Mathematician #1 can see #2's hat color, and announces a hat color of #0's answer - #2's hat color. Mathematician #2 announces a hat color of #0's answer - #1's answer. #1 and #2 survive, then the cycle repeats with #s 3, 4, and 5. This gets you to 2/3rd.
Call that a 2-lookahead strategy. It works for 3-lookahead as well: #0 says #1+#2+#3, #1 says #0's answer - (#2+#3), #2 says #0's answer - (#1's answer + #3), #3 says #0's answer - (#1's answer + #2's answer)...and I think you can see that for any finite N an N-lookahead strategy will get you an (N-1)/N survival rate.
Whether you can extend N to infinity is trickier and brings into play other assumptions, like whether or not the mathematicians get to perform an infinite amount of calculations and whether or not they can communicate a number with an infinite number of digits; the latter is somewhat problematic for the puzzle in the event then it's trivial to save all but the first mathematician, since all the first mathematician has to do is read off everyone's color as that first hat color and the rest will go free.
The general principle here is to realize that with an infinite list of mathematicians facing "forward" and the list drained from the "back" the only thing that changes from one mathematician to the next is whatever information the previous mathematicians' answers supplied to the subsequent mathematicians, and that it's imperative to put as much information into those answers as possible.
posted by hoople at 7:31 AM on August 28, 2012 [6 favorites]
Infinity is not a number. Paradoxes that treat it as though it is are not really paradoxes at all.
But language, it's a virus.
posted by chavenet at 7:36 AM on August 28, 2012
But language, it's a virus.
posted by chavenet at 7:36 AM on August 28, 2012
OK I'm pretty close to just writing this off as Dark Magic Beyond My Understanding, but two questions to maybe help me narrow it down:
Is the fact there are "infinitely many colors" relevant? Would this work just as well if there were a limited number of colors?
Are the mathematicians using the information they hear from those behind them at all? I assume they'd have to be, but I don't see where in your explanation that happens.
posted by ook at 7:38 AM on August 28, 2012
Is the fact there are "infinitely many colors" relevant? Would this work just as well if there were a limited number of colors?
Are the mathematicians using the information they hear from those behind them at all? I assume they'd have to be, but I don't see where in your explanation that happens.
posted by ook at 7:38 AM on August 28, 2012
Oh never mind, hoople's explanation answers both of those. Thanks, hoople.
posted by ook at 7:39 AM on August 28, 2012
posted by ook at 7:39 AM on August 28, 2012
It is also impossible to construct an infite rod or an infinte plane.
It's certainly a lot of work to get them infinitely long! I tried to construct those once, but I only got halfway. And if I had succeeded, I wouldn't have known where to put them.
posted by martinrebas at 7:43 AM on August 28, 2012
It's certainly a lot of work to get them infinitely long! I tried to construct those once, but I only got halfway. And if I had succeeded, I wouldn't have known where to put them.
posted by martinrebas at 7:43 AM on August 28, 2012
I like to imagine that when evil wizards set up challenges like this, they end up giving all the mathematicians except the first one identical white hats, just to see if that kind of degenerate case was accounted for in their survival strategy.
posted by ceribus peribus at 7:44 AM on August 28, 2012 [4 favorites]
posted by ceribus peribus at 7:44 AM on August 28, 2012 [4 favorites]
With no beginning and no end, the only "location" on an infinitely long line would be the exact middle, right?
No. Again, consider the integers from 0 up. That "line" is infinitely long but you are at a very well-specified "distance" from the beginning. Or all integers, negative and positive included. There are many places that aren't the "exact middle", assuming by that you mean 0.
All of this also goes from the volume remark, but in 3 dimensions instead of 1.
posted by DU at 7:45 AM on August 28, 2012
No. Again, consider the integers from 0 up. That "line" is infinitely long but you are at a very well-specified "distance" from the beginning. Or all integers, negative and positive included. There are many places that aren't the "exact middle", assuming by that you mean 0.
All of this also goes from the volume remark, but in 3 dimensions instead of 1.
posted by DU at 7:45 AM on August 28, 2012
Well ook you should look at the answer in Elementary Penguin's profile, it's quite cool, very sneaky, and based on an entirely different principle.
That said, in terms of fairness it does essentially imply an infinite amount of prior communication between the mathematicians, because it's critical that the mathematicians all use the same representative member of each equivalence class; without that guarantee of agreement -- with each mathematician choosing their own representative member -- it'd be possible for the mathematicians to make an *incredibly* pathological sequence of choices.
With that degree of prior communication *and* with knowledge that the cardinality of the set of hat colors is no greater than that of R *and* allowing each mathematician to compute an infinite sum *and* for the first mathematician to communicate their hat color with infinite precision you can get it down to only a single mathematician death, but at first blush that approach requires all of those extra provisions.
posted by hoople at 7:50 AM on August 28, 2012 [1 favorite]
That said, in terms of fairness it does essentially imply an infinite amount of prior communication between the mathematicians, because it's critical that the mathematicians all use the same representative member of each equivalence class; without that guarantee of agreement -- with each mathematician choosing their own representative member -- it'd be possible for the mathematicians to make an *incredibly* pathological sequence of choices.
With that degree of prior communication *and* with knowledge that the cardinality of the set of hat colors is no greater than that of R *and* allowing each mathematician to compute an infinite sum *and* for the first mathematician to communicate their hat color with infinite precision you can get it down to only a single mathematician death, but at first blush that approach requires all of those extra provisions.
posted by hoople at 7:50 AM on August 28, 2012 [1 favorite]
I was headed in the same direction as hoople. If colors can be mapped to real numbers, and mathematicians are allowed to give infinite answers, then the first mathematician can save everybody. E.g., the first mathematician can recite the numbers for the next mathematicians diagonally:
2nd: 0.ACFJ ...
3rd: 0.BEI ...
4th: 0.DH ...
5th: 0.G ...
1st says 0.ABCDE..., resulting in an infinite number that specifies all of the hat colors.
So to keep it fun, one rule of the game must be that any given hat color can be specified with a finite number, and mathematicians must give finite answers. Right?
Spoiler alert:
So if that's true, and Penguin says there's a solution where finitely many mathematicians die ... does that mean the mathematicians that die are able to specify an infinite number of hat colors using a finite number of finite numbers? Or have I built some confusion about infinity in here somewhere?
posted by jhc at 7:51 AM on August 28, 2012
2nd: 0.ACFJ ...
3rd: 0.BEI ...
4th: 0.DH ...
5th: 0.G ...
1st says 0.ABCDE..., resulting in an infinite number that specifies all of the hat colors.
So to keep it fun, one rule of the game must be that any given hat color can be specified with a finite number, and mathematicians must give finite answers. Right?
Spoiler alert:
So if that's true, and Penguin says there's a solution where finitely many mathematicians die ... does that mean the mathematicians that die are able to specify an infinite number of hat colors using a finite number of finite numbers? Or have I built some confusion about infinity in here somewhere?
posted by jhc at 7:51 AM on August 28, 2012
but is everything still exploding?
posted by philip-random at 7:56 AM on August 28, 2012
posted by philip-random at 7:56 AM on August 28, 2012
hoople: Malor: you can certainly do much, much better than 50%, it's just a question of how many "infinite" operations you're permitted and if you're allowed to assume some agreed-upon mapping from the colors into some other algebraic structure.
But the percentage doesn't matter, as the riddle is proposed. My solution saves an infinite number of mathematicians. So does yours, but even though you're saving 66% instead of 50%, I save just as many mathematicians as you do. So my suboptimal, non-complex solution is every bit as good, in the terms proposed by the original riddle.
Which leads me to this:
Elementary Penguin: there's a fundamental problem with the way you worded your riddle: you specify the measurement of the 'goodness' of a solution being the number of mathematicians who live, but the solution is based on minimizing the number of mathematicians who die.
posted by Malor at 8:05 AM on August 28, 2012 [5 favorites]
But the percentage doesn't matter, as the riddle is proposed. My solution saves an infinite number of mathematicians. So does yours, but even though you're saving 66% instead of 50%, I save just as many mathematicians as you do. So my suboptimal, non-complex solution is every bit as good, in the terms proposed by the original riddle.
Which leads me to this:
Elementary Penguin: there's a fundamental problem with the way you worded your riddle: you specify the measurement of the 'goodness' of a solution being the number of mathematicians who live, but the solution is based on minimizing the number of mathematicians who die.
posted by Malor at 8:05 AM on August 28, 2012 [5 favorites]
Yes Malor, but unlike the traditional formulation, this question allows for infinitely many hat colours, not a binary choice of hats.
Ack, please disregard. I somehow misread Malor's answer as being based on whether or not the same colour happened twice in a row. It's a perfectly good "every other person saves the person ahead of them" strategy. Sorry about that.
posted by ceribus peribus at 8:16 AM on August 28, 2012
Ack, please disregard. I somehow misread Malor's answer as being based on whether or not the same colour happened twice in a row. It's a perfectly good "every other person saves the person ahead of them" strategy. Sorry about that.
posted by ceribus peribus at 8:16 AM on August 28, 2012
Malor -- maybe the goal of minimizing the number of mathematicians who die is implicit in the fact that we are trying to thwart an evil wizard?
I mean, if there was a solution exactly like yours, except it also allowed the 3rd mathematician to live, the 3rd mathematician would obviously prefer that solution to yours, and none of the others would have reason to object. The only person who would prefer your solution is the evil wizard, who would take delight in the 3rd mathematician's suffering. I think it's clear from the wording of the puzzle that catering to the evil wizard's preferences is discouraged.
posted by jhc at 8:17 AM on August 28, 2012
I mean, if there was a solution exactly like yours, except it also allowed the 3rd mathematician to live, the 3rd mathematician would obviously prefer that solution to yours, and none of the others would have reason to object. The only person who would prefer your solution is the evil wizard, who would take delight in the 3rd mathematician's suffering. I think it's clear from the wording of the puzzle that catering to the evil wizard's preferences is discouraged.
posted by jhc at 8:17 AM on August 28, 2012
I just noticed that where the Wiki article on Buzz Lightyear documents his famous catchphrase, they hyperlink the word infinity to the Wiki article on these very notions of infinity.
posted by localroger at 8:22 AM on August 28, 2012
posted by localroger at 8:22 AM on August 28, 2012
quin: "Can one infinity be bigger than another?"
Bigger, or denser? Hmm.
posted by boo_radley at 8:25 AM on August 28, 2012
Bigger, or denser? Hmm.
posted by boo_radley at 8:25 AM on August 28, 2012
With infinity, it's all about girth.
posted by blue_beetle at 8:27 AM on August 28, 2012
posted by blue_beetle at 8:27 AM on August 28, 2012
Arrgh... hoople, I thought your answer was just a better explanation of his answer. You're saying you're each talking about completely different techniques? 'cause yours I can follow; his reads to me like that old "and then a miracle occurs" New Yorker cartoon -- I don't see how you get from the equivalence class to a color.
I'm tempted to just leave it there and rest secure in the knowledge that I will therefore never be given a hat by this particular wizard, but this is really niggling at me... if you don't mind wasting your time edumacating some random mathnoob on the internet, can you please show me where I go off the rails in trying to understand his answer?
So they divide all possible arrangements of hats into classes ("hattenings"), which are considered equivalent if only a finite subset of the arrangement differs.
They then arbitrarily pick one representative of each class and discard the rest.
Then each mathematician, seeing the infinite array of hats in front of him, knows which hattening that arrangement represents: The 'finite subset' ignored in the equivalence class are the hats behind (and on) the current mathematician; the infinite remainder is the hats that he can see in front of him. Since they've arbitrarily selected a representative of that class which contains a color for his hat, he guesses his own color based on what's in the representative set.
Which, that's where the miracle occurs as far as I can tell: how does that differ from an elaborate "guess your own color at random" process? The representative of each "hattening" was randomly selected, and I don't see how narrowing the choice down to a particular representative based on the hats in front of the current mathematician gives any information about the hat on the current mathematician.
EP says "Since the representative differs only finitely many times from any hattening in the equivalence class, only finitely many of the mathematicians will die" -- which suggests that we're going for a statistical survival approach rather than a passing-of-information approach... okay... but as far as I can tell even the first mathematician, who's working with a hattening that is the same for all but one mathematician (himself) still has an infinite number of wrong guesses he could make and only one right one. It only gets worse for mathematicians further down the line.
Even removing infinity from the problem (either in the number of colors or in the number of mathematicians) I don't see how that technique improves on "guess at random". Isn't it just moving the "guess" part from "guess my hat" to "pick a representative of the equivalence class"?
Obviously I'm totally misunderstanding something; can somebody help point out at what step I lost it?
posted by ook at 8:30 AM on August 28, 2012
I'm tempted to just leave it there and rest secure in the knowledge that I will therefore never be given a hat by this particular wizard, but this is really niggling at me... if you don't mind wasting your time edumacating some random mathnoob on the internet, can you please show me where I go off the rails in trying to understand his answer?
So they divide all possible arrangements of hats into classes ("hattenings"), which are considered equivalent if only a finite subset of the arrangement differs.
They then arbitrarily pick one representative of each class and discard the rest.
Then each mathematician, seeing the infinite array of hats in front of him, knows which hattening that arrangement represents: The 'finite subset' ignored in the equivalence class are the hats behind (and on) the current mathematician; the infinite remainder is the hats that he can see in front of him. Since they've arbitrarily selected a representative of that class which contains a color for his hat, he guesses his own color based on what's in the representative set.
Which, that's where the miracle occurs as far as I can tell: how does that differ from an elaborate "guess your own color at random" process? The representative of each "hattening" was randomly selected, and I don't see how narrowing the choice down to a particular representative based on the hats in front of the current mathematician gives any information about the hat on the current mathematician.
EP says "Since the representative differs only finitely many times from any hattening in the equivalence class, only finitely many of the mathematicians will die" -- which suggests that we're going for a statistical survival approach rather than a passing-of-information approach... okay... but as far as I can tell even the first mathematician, who's working with a hattening that is the same for all but one mathematician (himself) still has an infinite number of wrong guesses he could make and only one right one. It only gets worse for mathematicians further down the line.
Even removing infinity from the problem (either in the number of colors or in the number of mathematicians) I don't see how that technique improves on "guess at random". Isn't it just moving the "guess" part from "guess my hat" to "pick a representative of the equivalence class"?
Obviously I'm totally misunderstanding something; can somebody help point out at what step I lost it?
posted by ook at 8:30 AM on August 28, 2012
Do these pants make my ass look infinite?
posted by stupidsexyFlanders at 8:32 AM on August 28, 2012 [4 favorites]
posted by stupidsexyFlanders at 8:32 AM on August 28, 2012 [4 favorites]
martinrebas: happens? The infinite rod descends freely through the first 90 degrees, until it’s parallel to the tabletop. But it can’t go beyond this, because then at some point the solid rod would intersect the solid table.Since the surface area of the 2D rotational integral of 1/x is infinite, but the volume contained by it is finite, a bucket of this shape does not hold enough paint to paint it's own inside surface.
Thus it’s impossible to “rest” an infinite rod on an infinite plane. “And so, you have the curious phenomenon of the hinged rod being
posted by IAmBroom at 8:39 AM on August 28, 2012
The thing that always got me is that i is not so much "undefined" as "simultaneously both the largest and smallest possible number." When I pointed this out in my third (?) grade Catholic school math class, the teacher/nun was not happy.
1 / -5 = -.2
1 / -2 = -.5
1 / -1 = -1
1 / -.5 = -5
1 / -.1 = -10
1 / 0 = i, where that is the smallest of all numbers, negative infinity. -∞
1 / 0 = i, where that is the largest of all numbers, infinity. ∞
1 / .1 = 10
1 / .5 = 2
1 / 1 = 1
1 / 2 = .5
1 / 3 = .33
1 / 10 = .1
More from wikipedia about division by zero.
posted by andreaazure at 8:39 AM on August 28, 2012
1 / -5 = -.2
1 / -2 = -.5
1 / -1 = -1
1 / -.5 = -5
1 / -.1 = -10
1 / 0 = i, where that is the smallest of all numbers, negative infinity. -∞
1 / 0 = i, where that is the largest of all numbers, infinity. ∞
1 / .1 = 10
1 / .5 = 2
1 / 1 = 1
1 / 2 = .5
1 / 3 = .33
1 / 10 = .1
More from wikipedia about division by zero.
posted by andreaazure at 8:39 AM on August 28, 2012
I don't see how narrowing the choice down to a particular representative based on the hats in front of the current mathematician gives any information about the hat on the current mathematician.
You're right, it doesn't. What it does create is a "position of safety". There is some position, after which the (arbitrarily chosen) representative agrees with the actual configuration. The brilliance of the solution is that this position of safety actually exists. The sucky thing is that no-one knows when it starts, so any particularly chosen mathematician doesn't know if she's after the position of safety (and is guaranteed to survive), or before it (and may die).
To make it more concrete, suppose (and this is a big suppose, and isn't generally true, but we're supposing it to make the principal easier to understand, just like every factoring problem in your algebra homework involved whole number), suppose the representative picked happened to be "all green hats". This tells the mathematicians that, looking at the real hats, after some point they are solid green. There is some finite bunch at the beginning that aren't green, but eventually they are all green.
So, instead of having no idea, they now know that they are eventually all green. So each one is going to guess "green", hoping that they, individually, are after the point where they are all green. There is no individual guarantee; the guarantee is about the sequence.
posted by benito.strauss at 8:43 AM on August 28, 2012
You're right, it doesn't. What it does create is a "position of safety". There is some position, after which the (arbitrarily chosen) representative agrees with the actual configuration. The brilliance of the solution is that this position of safety actually exists. The sucky thing is that no-one knows when it starts, so any particularly chosen mathematician doesn't know if she's after the position of safety (and is guaranteed to survive), or before it (and may die).
To make it more concrete, suppose (and this is a big suppose, and isn't generally true, but we're supposing it to make the principal easier to understand, just like every factoring problem in your algebra homework involved whole number), suppose the representative picked happened to be "all green hats". This tells the mathematicians that, looking at the real hats, after some point they are solid green. There is some finite bunch at the beginning that aren't green, but eventually they are all green.
So, instead of having no idea, they now know that they are eventually all green. So each one is going to guess "green", hoping that they, individually, are after the point where they are all green. There is no individual guarantee; the guarantee is about the sequence.
posted by benito.strauss at 8:43 AM on August 28, 2012
Phyllis Harmonic: With no beginning and no end, the only "location" on an infinitely long line would be the exact middle, right? Same for infinite volume- we would be forever at the exact center. All of us at once (assuming we are occupying the same infinite volume.)No, it can have one end and an infinite length.
Mathematicians, double-check me here:
Any finite distance from that end is before the middle:
N(element of Reals) < Inf, therefore 2*N < Inf
posted by IAmBroom at 8:44 AM on August 28, 2012
Now that I've had some time to digest Elementary Penguin's solution, I think I have the traditional engineering critism of it: it presents a well formed proof that an approach exists that results in only a finite number of mathematician deaths, but stops short of detailing what the approach is.
posted by ceribus peribus at 8:49 AM on August 28, 2012
posted by ceribus peribus at 8:49 AM on August 28, 2012
Here's the thing about division by 0. Suppose you want to define a value for it. So a/0 = 0, say. This contradicts the rules for multiplication, where x*0 = 0, since now a/0 * 0 = ....what? 0? a? It looks like it should be both answers, but that isn't allowed - multiplying a number by another number gives a determinate answer.
You can't define multiplication in the way that we do and also have division by 0.
posted by thelonius at 8:54 AM on August 28, 2012 [1 favorite]
You can't define multiplication in the way that we do and also have division by 0.
posted by thelonius at 8:54 AM on August 28, 2012 [1 favorite]
Ah hah! So, more or less, each mathematician keeps in his mind a list of all the representatives that haven't been eliminated by the statements of the mathematicians behind him; at some point that'll converge on a a known order for all remaining mathematicians. (right?) Thank you benito.strauss, that's the detail I was missing.
posted by ook at 8:56 AM on August 28, 2012
posted by ook at 8:56 AM on August 28, 2012
andreaazure: The thing that always got me is that i is not so much "undefined" as "simultaneously both the largest and smallest possible number." When I pointed this out in my third (?) grade Catholic school math class, the teacher/nun was not happy.Well, more accurately the set of all infinite numbers includes both largest and smallest possible numbers.
The math problems you have worked out are true for real numbers, but not necessarily for infinite numbers. That is, the value Inf1 reached from
1 / -5 = -.2is not necessarily the same value as Inf2 reached by
1 / -2 = -.5
1 / -1 = -1
1 / -.5 = -5
1 / -.1 = -10
1 / 0 = Inf1, where Inf1is the smallest of all numbers, negative infinity. -∞
1 / 0 = Inf2, where Inf2 is the largest of all numbers, infinity. ∞posted by IAmBroom at 8:58 AM on August 28, 2012
1 / .1 = 10
1 / .5 = 2
1 / 1 = 1
1 / 2 = .5
1 / 3 = .33
1 / 10 = .1
I am sure the reason andreaazure's nun was unthrilled is that by calling n/0 "undefined" she was sweeping under the rug the idea that there is more than one infinity; the religious conception of infinity in its glorious naivete would be that there can be only one infinity, and that it is God.
Which is also why they get all het up about set theory, of course.
posted by localroger at 9:09 AM on August 28, 2012
Which is also why they get all het up about set theory, of course.
posted by localroger at 9:09 AM on August 28, 2012
ook, it's been a while for me, plus I'm attempting to make this easier to understand so I'm sure someone will find flaws in my explanation. I don't think benito has it correct, either.
The mathematicians break down all possible orderings into sets of similar orderings, where similar means that there is a finite number of differences across the infinite ordering.
The problem is about color, but imagine for a moment it's about characters. Here are two sets the mathematicians could create:
set 1:
ordering 1: {1,2,3,4,5,6,7,8,9,0}
ordering 2: {1,2,4,3,5,7,4,2,1,5}
ordering 3: {2,2,3,2,2,3,4,5,7,2}
ordering 4: {6,6,6,6,6,6,6,5,6,6}
ordering 5: {1,2,8,4,5,2,1,8,9,6}
set 2:
ordering 1: {a,s,d,f,g,h,j,k,l,m}
ordering 2: {t,e,f,b,u,r,a,s,s,v}
ordering 3: {q,w,e,r,t,y,u,i,o,p}
ordering 4: {o,n,g,c,d,e,r,f,t,g}
ordering 5: {n,n,n,n,n,n,n,n,n,n}
Granted, that is a finite number of sets with a finite number of orderings of a finite number of items. This is for ease of explanation, the principles hold for all of those being infinite.
The mathematicians agree ahead of time that (for instance), they will all guess from Set 1 Ordering 1 and Set 2 Ordering 4 (it doesing matter which ordering, so long as they all agree).
Now, each mathematician can only see the hats in front of him. But if all the guys behind you guess numbers, you know you're in set 1 so you do your job and guess from Set 1 Ordering 1. You might be wrong and die, but the point is that there are only a finite number of differences between any of the orderings in set 1, so only a finite number will die.
This is different from the solutions presented in the thread so far where an infinite number live, but an infinite number also die (this is the point Malor was making by saying that Penguin's solution solves a different problem than the one presented. Malor "saved" the same number of mathematicians as Penguin's solution, but killed more. If that makes no sense, go watch the first linked video again re: Malor saving all "even" mathematicians while Penguin saved all "real" mathematicians. Malor killed all "odd" mathematicians -infinite- while Penguin killed a finite number).
It's also not correct to believe, as benito suggested, that eventually you will get onto the correct sequence and all future guessers will be correct. Assume again that they're guessing along Set 1 Ordering 1. The actual order might be Set 1 Ordering 5. After the first two guys live, guy three might feel really safe, but die anyway. Similarly down the line, past correct guesses are no guarantee that you're in the correct Ordering. You know from seeing the hats ahead of you what Set you're in, and have agreed ahead of time that guessing within the correct Set and having finitely many of you be wrong is the best possible outcome.
It may sound crazy, because in my example orderings for set 1 orderings 2 and 4 differ completely, but still finitely. When going on infinitely it really doesn't matter if 1, 10, or a billion mathematicians die, so long as an infinite number of them live and a finite number of them die. Once you get to the point where an infinite number die it's all the same, but every finite number of dead mathematicians is fewer than any infinite number of dead mathematicians (in Penguin's solution anyway. The problem originally asked how many could live, at which point any infinite number living is equally good, regardless of how many died).
posted by jermsplan at 9:17 AM on August 28, 2012
The mathematicians break down all possible orderings into sets of similar orderings, where similar means that there is a finite number of differences across the infinite ordering.
The problem is about color, but imagine for a moment it's about characters. Here are two sets the mathematicians could create:
set 1:
ordering 1: {1,2,3,4,5,6,7,8,9,0}
ordering 2: {1,2,4,3,5,7,4,2,1,5}
ordering 3: {2,2,3,2,2,3,4,5,7,2}
ordering 4: {6,6,6,6,6,6,6,5,6,6}
ordering 5: {1,2,8,4,5,2,1,8,9,6}
set 2:
ordering 1: {a,s,d,f,g,h,j,k,l,m}
ordering 2: {t,e,f,b,u,r,a,s,s,v}
ordering 3: {q,w,e,r,t,y,u,i,o,p}
ordering 4: {o,n,g,c,d,e,r,f,t,g}
ordering 5: {n,n,n,n,n,n,n,n,n,n}
Granted, that is a finite number of sets with a finite number of orderings of a finite number of items. This is for ease of explanation, the principles hold for all of those being infinite.
The mathematicians agree ahead of time that (for instance), they will all guess from Set 1 Ordering 1 and Set 2 Ordering 4 (it doesing matter which ordering, so long as they all agree).
Now, each mathematician can only see the hats in front of him. But if all the guys behind you guess numbers, you know you're in set 1 so you do your job and guess from Set 1 Ordering 1. You might be wrong and die, but the point is that there are only a finite number of differences between any of the orderings in set 1, so only a finite number will die.
This is different from the solutions presented in the thread so far where an infinite number live, but an infinite number also die (this is the point Malor was making by saying that Penguin's solution solves a different problem than the one presented. Malor "saved" the same number of mathematicians as Penguin's solution, but killed more. If that makes no sense, go watch the first linked video again re: Malor saving all "even" mathematicians while Penguin saved all "real" mathematicians. Malor killed all "odd" mathematicians -infinite- while Penguin killed a finite number).
It's also not correct to believe, as benito suggested, that eventually you will get onto the correct sequence and all future guessers will be correct. Assume again that they're guessing along Set 1 Ordering 1. The actual order might be Set 1 Ordering 5. After the first two guys live, guy three might feel really safe, but die anyway. Similarly down the line, past correct guesses are no guarantee that you're in the correct Ordering. You know from seeing the hats ahead of you what Set you're in, and have agreed ahead of time that guessing within the correct Set and having finitely many of you be wrong is the best possible outcome.
It may sound crazy, because in my example orderings for set 1 orderings 2 and 4 differ completely, but still finitely. When going on infinitely it really doesn't matter if 1, 10, or a billion mathematicians die, so long as an infinite number of them live and a finite number of them die. Once you get to the point where an infinite number die it's all the same, but every finite number of dead mathematicians is fewer than any infinite number of dead mathematicians (in Penguin's solution anyway. The problem originally asked how many could live, at which point any infinite number living is equally good, regardless of how many died).
posted by jermsplan at 9:17 AM on August 28, 2012
Something maybe I should have pointed out:
My example finite sets meet the criteria to be "similar" in that they have finite differences, due to the fact that they are finite themselves, and would therefore technically be the same set. If each ordering in sets 1 and 2 were infinitely long but set 1 was all numerals and set 2 all letters, they would no longer be "similar" since they would have infinite differences. Hopefully it made sense anyway.
posted by jermsplan at 9:20 AM on August 28, 2012
My example finite sets meet the criteria to be "similar" in that they have finite differences, due to the fact that they are finite themselves, and would therefore technically be the same set. If each ordering in sets 1 and 2 were infinitely long but set 1 was all numerals and set 2 all letters, they would no longer be "similar" since they would have infinite differences. Hopefully it made sense anyway.
posted by jermsplan at 9:20 AM on August 28, 2012
stupidsexyFlanders: "Do these pants make my ass look infinite?"
Not in those Calvin Klein Bottle jeans, sweetie. You look fine.
posted by boo_radley at 9:27 AM on August 28, 2012 [3 favorites]
Not in those Calvin Klein Bottle jeans, sweetie. You look fine.
posted by boo_radley at 9:27 AM on August 28, 2012 [3 favorites]
jhc: Malor -- maybe the goal of minimizing the number of mathematicians who die is implicit in the fact that we are trying to thwart an evil wizard?
If there's one thing I've learned since I found the Internet, it's that in problems involving imaginary mathematicians, especially involving infinity of any sort, you have to solve the problem as it's presented. And, as this problem is given, you're trying to end up with as many living mathematicians as possible, so any result that gives an infinite number of survivors is equivalent.
The odd-numbered mathematicians would probably disagree with my solution. But, being dead, they don't get to vote. And even if they could, they'd tie with the even-numbered mathematicians.
posted by Malor at 9:38 AM on August 28, 2012 [1 favorite]
If there's one thing I've learned since I found the Internet, it's that in problems involving imaginary mathematicians, especially involving infinity of any sort, you have to solve the problem as it's presented. And, as this problem is given, you're trying to end up with as many living mathematicians as possible, so any result that gives an infinite number of survivors is equivalent.
The odd-numbered mathematicians would probably disagree with my solution. But, being dead, they don't get to vote. And even if they could, they'd tie with the even-numbered mathematicians.
posted by Malor at 9:38 AM on August 28, 2012 [1 favorite]
ook: well, not quite, there's not really any dynamic adjustment or narrowing-down of the representative in Elementary Penguin's solution.
Expanded a bit, the solution Elementary Penguin offers work like this.
A hattening is an assignment of hats-to-mathematicians-in-sequence, so, say {Red,Blue,Green,Red,Blue,Green,...} is one such hattening. To keep this compact I'll write stuff as (RGB...) means "RGB repeated infinitely", and (RBB,RGB..) means "RBB, then RGB repeated infinitely".
We are interested in moving from specific sequences to families of sequences, and do so like this: given sequences A and B, we say that A and B are equivalent if it would take only a finite number of edits to A to turn it into B. Thus (RBB,RGB...) and (RGB...) are equivalent, because they differ in one spot, but (R...) and (RGB...) are not equivalent, because they differ in an infinite number of locations.
To further abbreviate things we say (RGB...)-esque for "equivalent to (RGB...)".
We want to be talking about the family of (RGB...)-esque sequences or the family of (R...)-esque sequences, but there's some slipperiness: (RGB...) and (RBB,RGB...) are equivalent, and before going further we need to know if it makes a difference whether or not we talk about the (RGB...)-esque or the (RBB,RGB...)-esque family.
The answer is it doesn't: with a bit of work you can show that if sequence A is (RGB...)-esque than the family of the A-esque sequences is exactly the same as the family of (RGB...)-esque sequences. This is an exercise for the reader to verify, but assuming its truth and moving on, what did we just learn? We learned that any member of a family is enough to identify the entire family, and, relatedly, that family membership is, let's say, "crisp" (every sequence is in some family, and no sequence is in two families).
Given that terminology, the key step of the Elemental Penguin strategy is that the mathematicians must all manage to agree upon a canonical example for each family; that is, they all must somehow come agree that the (RGB...)-esque family is the "(RGB...)-family", and will never be referred to as the "(RBB,RGB...)-esque family".
With that agreement in mind, when they go into the room and get their hats, they do as follows: (1) look out head of them and see all the hats; (2) determine that the sequence of hat-assignments is a member of some specific family of sequences, call it the S-esque family; (3) remember the canonical example they agreed upon for the S-esque family, say they are officially agreed to be known as the "C-esque family"; (4) when mathematician n is called upon, mathematician n will give C(n) for a hat color.
Why does this guarantee that only finitely many mathematicians die? Because the mathematicians have been given hats in a C-esque sequence and collectively offer C as their sequence of hats. Any C-esque sequence is going to differ from C in only a finite number of places, and thus only a finite number of mathematicians will give a wrong answer.
That's why it's clever and why I said it uses a very different principle to the N-lookahead family of strategies.
But, note that it doesn't work without the mathematicians agreeing upon a canonical example from each family of sequences; if they don't have that agreement I don't think it is possible to make any a priori guarantees about the survival rate. If the same strategy is adopted except with each mathematician choosing their own canonical example for each family it's entirely possible for every mathematician to wind up dead.
The need for this agreement on canonical membership is why I said that despite its sneaky cleverness it seems to imply an infinite amount of prior communication amongst the mathematicians, as they must arrive at an agreed-upon canonical example for each sequence family, and there are infinitely-many such families requiring such an agreement; if you are allowed that communication it seems like it should open up other types of solution.
This doesn't mean the Elementary Penguin answer is wrong -- it works and is both very clever and very cool! -- but it does mean that perhaps the problem could benefit from better wording (e.g. it might also want to rephrase it as "fewest deaths", per Malor, or even better something like "highest percentage of survivors").
posted by hoople at 9:38 AM on August 28, 2012 [2 favorites]
Expanded a bit, the solution Elementary Penguin offers work like this.
A hattening is an assignment of hats-to-mathematicians-in-sequence, so, say {Red,Blue,Green,Red,Blue,Green,...} is one such hattening. To keep this compact I'll write stuff as (RGB...) means "RGB repeated infinitely", and (RBB,RGB..) means "RBB, then RGB repeated infinitely".
We are interested in moving from specific sequences to families of sequences, and do so like this: given sequences A and B, we say that A and B are equivalent if it would take only a finite number of edits to A to turn it into B. Thus (RBB,RGB...) and (RGB...) are equivalent, because they differ in one spot, but (R...) and (RGB...) are not equivalent, because they differ in an infinite number of locations.
To further abbreviate things we say (RGB...)-esque for "equivalent to (RGB...)".
We want to be talking about the family of (RGB...)-esque sequences or the family of (R...)-esque sequences, but there's some slipperiness: (RGB...) and (RBB,RGB...) are equivalent, and before going further we need to know if it makes a difference whether or not we talk about the (RGB...)-esque or the (RBB,RGB...)-esque family.
The answer is it doesn't: with a bit of work you can show that if sequence A is (RGB...)-esque than the family of the A-esque sequences is exactly the same as the family of (RGB...)-esque sequences. This is an exercise for the reader to verify, but assuming its truth and moving on, what did we just learn? We learned that any member of a family is enough to identify the entire family, and, relatedly, that family membership is, let's say, "crisp" (every sequence is in some family, and no sequence is in two families).
Given that terminology, the key step of the Elemental Penguin strategy is that the mathematicians must all manage to agree upon a canonical example for each family; that is, they all must somehow come agree that the (RGB...)-esque family is the "(RGB...)-family", and will never be referred to as the "(RBB,RGB...)-esque family".
With that agreement in mind, when they go into the room and get their hats, they do as follows: (1) look out head of them and see all the hats; (2) determine that the sequence of hat-assignments is a member of some specific family of sequences, call it the S-esque family; (3) remember the canonical example they agreed upon for the S-esque family, say they are officially agreed to be known as the "C-esque family"; (4) when mathematician n is called upon, mathematician n will give C(n) for a hat color.
Why does this guarantee that only finitely many mathematicians die? Because the mathematicians have been given hats in a C-esque sequence and collectively offer C as their sequence of hats. Any C-esque sequence is going to differ from C in only a finite number of places, and thus only a finite number of mathematicians will give a wrong answer.
That's why it's clever and why I said it uses a very different principle to the N-lookahead family of strategies.
But, note that it doesn't work without the mathematicians agreeing upon a canonical example from each family of sequences; if they don't have that agreement I don't think it is possible to make any a priori guarantees about the survival rate. If the same strategy is adopted except with each mathematician choosing their own canonical example for each family it's entirely possible for every mathematician to wind up dead.
The need for this agreement on canonical membership is why I said that despite its sneaky cleverness it seems to imply an infinite amount of prior communication amongst the mathematicians, as they must arrive at an agreed-upon canonical example for each sequence family, and there are infinitely-many such families requiring such an agreement; if you are allowed that communication it seems like it should open up other types of solution.
This doesn't mean the Elementary Penguin answer is wrong -- it works and is both very clever and very cool! -- but it does mean that perhaps the problem could benefit from better wording (e.g. it might also want to rephrase it as "fewest deaths", per Malor, or even better something like "highest percentage of survivors").
posted by hoople at 9:38 AM on August 28, 2012 [2 favorites]
Also, it's unclear that per that strategy you need to consider the responses from the mathematicians behind you: there are only ever finitely many mathematicians behind you and infinitely many in front of you, so if you plug your ears and assign arbitrary values to the hats of the mathematicians behind you it won't change which hattening you believe yourself to be in, as your guess can only differ from the actual assignment in finitely many places.
If I've overlooked something please let me know.
posted by hoople at 9:43 AM on August 28, 2012
If I've overlooked something please let me know.
posted by hoople at 9:43 AM on August 28, 2012
How does the infinite mathematicians line square with the uncomputability of the halting problem?
For example, suppose the wizard is able to compute the halting function (magic, remember?) and and some point (let's call this point 'Bob', preceded by 'Heather', the wizard starts assigning either black or white hats (0,1) depending on whether the mathematician representing the Turing machine n (Bob+n) halts (i.e., mathematician Bob+n = h(n), where h(.) is the halting function).
Then, if the sequence of mathematicians is:
[infinite people] Heather Bob Bob+1 Bob+2 ...
for Heather to save the line in front of her, she must be able to produce a finite utterance (a program) that computes the halting function, which is impossible, assuming the mathematicians are not capable of super-Turing computation. Furthermore, since the wizard can compute the halting function, he knows what answer (if any) a mathematician will give, so they can't stall by evaluating non-halting programs.
posted by Pyry at 9:47 AM on August 28, 2012
For example, suppose the wizard is able to compute the halting function (magic, remember?) and and some point (let's call this point 'Bob', preceded by 'Heather', the wizard starts assigning either black or white hats (0,1) depending on whether the mathematician representing the Turing machine n (Bob+n) halts (i.e., mathematician Bob+n = h(n), where h(.) is the halting function).
Then, if the sequence of mathematicians is:
[infinite people] Heather Bob Bob+1 Bob+2 ...
for Heather to save the line in front of her, she must be able to produce a finite utterance (a program) that computes the halting function, which is impossible, assuming the mathematicians are not capable of super-Turing computation. Furthermore, since the wizard can compute the halting function, he knows what answer (if any) a mathematician will give, so they can't stall by evaluating non-halting programs.
posted by Pyry at 9:47 AM on August 28, 2012
oh great he posted the answer and I do not understand a single word of it.
I still don’t understand the question.
posted by bongo_x at 9:49 AM on August 28, 2012 [2 favorites]
I still don’t understand the question.
posted by bongo_x at 9:49 AM on August 28, 2012 [2 favorites]
Oh, I read the answer, and it still violates the halting problem, because even if a mathematician somehow realized he was in the 'halting problem' hattening, he couldn't compute it (i.e., he would not be able to compute how the hats are arranged for the equivalence class representative, which would just be the halting problem + a finite number of errors).
posted by Pyry at 9:52 AM on August 28, 2012
posted by Pyry at 9:52 AM on August 28, 2012
Pyry, there are functions, and then there are computable functions, which form a strict subset of all functions. There are infinitely fewer computable functions that there are functions, and the computable functions are precisely the ones that can be produced by a Turing machine program.
Elementary Penguin's solution is very far from computable.
posted by benito.strauss at 9:58 AM on August 28, 2012 [1 favorite]
Elementary Penguin's solution is very far from computable.
posted by benito.strauss at 9:58 AM on August 28, 2012 [1 favorite]
Pyry: all proposed methods that save all but a finite number of people involve at least one infinite operation at some point, which moves them well outside the realm of the question you're raising.
posted by hoople at 9:59 AM on August 28, 2012
posted by hoople at 9:59 AM on August 28, 2012
Elementary Penguin's solution is very far from computable.
Yes, that's my point.
all proposed methods that save all but a finite number of people involve at least one infinite operation at some point, which moves them well outside the realm of the question you're raising.
Well, you could allow oracles to perform your infinite operations, but then Elementary Penguin's solution feels especially uncompelling, given the number of oracles you would need (one to tell you what equivalence class you're in [which itself couldn't be represented as a natural number], and another to evaluate that equivalence class for yourself; you might as well cut out the middleman and just have an oracle that tells you your hat color).
posted by Pyry at 10:11 AM on August 28, 2012 [2 favorites]
Yes, that's my point.
all proposed methods that save all but a finite number of people involve at least one infinite operation at some point, which moves them well outside the realm of the question you're raising.
Well, you could allow oracles to perform your infinite operations, but then Elementary Penguin's solution feels especially uncompelling, given the number of oracles you would need (one to tell you what equivalence class you're in [which itself couldn't be represented as a natural number], and another to evaluate that equivalence class for yourself; you might as well cut out the middleman and just have an oracle that tells you your hat color).
posted by Pyry at 10:11 AM on August 28, 2012 [2 favorites]
Has anyone read The Fault in Our Stars by John Green? It is a really great YA novel and interestingly enough, talks a bit about different infinities.
posted by morganannie at 10:12 AM on August 28, 2012
posted by morganannie at 10:12 AM on August 28, 2012
I think Pyry brings up a good point which is that Penguin's solution hinges on this assertion:
Now, once the mathematicians are lined up, each one can see all but finitely many of the hats.
Which suggests that the first mathematician to guess can see the infinity-1 hats ahead and correctly determine the Hattening he is in. I don't think this is actually possible, short of Pyry's oracle.
Can someone help me out there?
posted by jermsplan at 10:16 AM on August 28, 2012
Now, once the mathematicians are lined up, each one can see all but finitely many of the hats.
Which suggests that the first mathematician to guess can see the infinity-1 hats ahead and correctly determine the Hattening he is in. I don't think this is actually possible, short of Pyry's oracle.
Can someone help me out there?
posted by jermsplan at 10:16 AM on August 28, 2012
Pyry: Remember that every mathematician can see the hats in front of him or her. This means that in your scheme, one of the inputs to the system is an uncomputable sequence. Producing uncomputable output from uncomputable input is no big deal.
posted by baf at 10:18 AM on August 28, 2012 [1 favorite]
posted by baf at 10:18 AM on August 28, 2012 [1 favorite]
That's true, if it were actually the halting sequence then you could figure out your hat color (assuming you know your position) by just looking ahead to [your program]+[pointless operation], but in general the wizard could pick an uncomputable sequence in which the values don't have any computable relationship to one another (like a truly random sequence).
posted by Pyry at 10:22 AM on August 28, 2012
posted by Pyry at 10:22 AM on August 28, 2012
1) Malor is right. I should have said "fewest die", not "most live".
2) hoople's explanation is way better than mine, even if they are isomorphic.
3) The Axiom of Choice is totally non-constructive. An oracle is probably the best way to think about it. Sorry!
posted by Elementary Penguin at 10:23 AM on August 28, 2012
2) hoople's explanation is way better than mine, even if they are isomorphic.
3) The Axiom of Choice is totally non-constructive. An oracle is probably the best way to think about it. Sorry!
posted by Elementary Penguin at 10:23 AM on August 28, 2012
So, your mathematical nemesis is in a submarine. It just so happens that that submarine is in an ocean whose surface is an infinite plane (remember, this is your mathematical nemesis). Moreover, there's a square grid overlaying that plane (sort of like the game Battleship, I suppose).
In your efforts to destroy your nemesis, you've developed some ordinance that can destroy all submersibles underneath precisely one of the squares of the grid. (I really mean just one of the set squares -- you can't shift the grid and hit multiple squares from the old grid.) But the ordinance has some limitations: you can only use it once per day at noon.
Having studied the psychology of your nemesis quite carefully, you know that she has charted a course for her submarine (from which she will not stray) in which she will be in precisely one of the grid squares at noon each day.
Your nemesis has a great deal of patience and even greater lack of physical limitations like the need to resupply or die of natural causes. She is perfectly content to follow her charted course forever simply for the satisfaction of foiling your plans to destroy her. There are no intelligence-gathering means by which you can suss out her planned course.
Is there a foolproof strategy you can follow by which you are guaranteed to eventually destroy your nemesis's submarine?
posted by lllama at 10:28 AM on August 28, 2012 [1 favorite]
In your efforts to destroy your nemesis, you've developed some ordinance that can destroy all submersibles underneath precisely one of the squares of the grid. (I really mean just one of the set squares -- you can't shift the grid and hit multiple squares from the old grid.) But the ordinance has some limitations: you can only use it once per day at noon.
Having studied the psychology of your nemesis quite carefully, you know that she has charted a course for her submarine (from which she will not stray) in which she will be in precisely one of the grid squares at noon each day.
Your nemesis has a great deal of patience and even greater lack of physical limitations like the need to resupply or die of natural causes. She is perfectly content to follow her charted course forever simply for the satisfaction of foiling your plans to destroy her. There are no intelligence-gathering means by which you can suss out her planned course.
Is there a foolproof strategy you can follow by which you are guaranteed to eventually destroy your nemesis's submarine?
posted by lllama at 10:28 AM on August 28, 2012 [1 favorite]
If you're both restricted to computable functions, then yes, you can guarantee your Nemesis's destruction; if your Nemesis can compute or has access to uncomputable functions (e.g., true randomness), then no, you can't guarantee destruction.
posted by Pyry at 10:42 AM on August 28, 2012
posted by Pyry at 10:42 AM on August 28, 2012
I'm happy to think of the nemesis's course as an exceptionally long list of noon-time locations, in which case you're definitely right that you can guarantee destruction. It's an elementary problem (you don't need to know about computable functions) that I think has a very pretty solution (which I don't want to give away!).
You can also build up to this problem if you're discussing infinity and enumeration with friends. The easiest variant involves a nemesis on the integer number line who starts at 0 and always moves n to the right (but you don't know n). The next one is on the integer number line where the nemesis has no restrictions in plotting her course. If you solve that one, you're just a few technical tricks from getting the "integer lattice" version I posted above.
(I should credit a friend for this particular string of problems, but I don't know if he wants his name on the Internet...)
posted by lllama at 11:06 AM on August 28, 2012
You can also build up to this problem if you're discussing infinity and enumeration with friends. The easiest variant involves a nemesis on the integer number line who starts at 0 and always moves n to the right (but you don't know n). The next one is on the integer number line where the nemesis has no restrictions in plotting her course. If you solve that one, you're just a few technical tricks from getting the "integer lattice" version I posted above.
(I should credit a friend for this particular string of problems, but I don't know if he wants his name on the Internet...)
posted by lllama at 11:06 AM on August 28, 2012
If you want to take it up a notch you can let the nemesis go to rational, algebraic, or computable real coordinates, rather than being restricted to the lattice. I will also not spoil what the answers are for those cases.
posted by Pyry at 11:15 AM on August 28, 2012
posted by Pyry at 11:15 AM on August 28, 2012
Yeah, on my way to lunch I realized that my last stab at it was obviously wrong (because there's no information in the previous guesses that helps the next guy.)
So, if I'm following the followups correctly (and thanks, everyone, for patiently helping me sort this out; I feel like the slow kid in class today but this is fun):
- if I'm in line I don't need to listen to the guys behind me, they're not passing me any information;
- each sets contain lists which have a finite number of differences from each other, and an infinite number of correspondencies;
- each mathematician sees an infinite list (the hats in front of him), so knows which set to work with, and that there are only a finite number of possible variations on that list (proportional to the number of hats behind him plus his own);
- therefore by assuming the actual list is a specific representative sample from each set, only a finite number will be wrong;
- but they all have to agree on the same system for selecting that representative sample, otherwise you're introducing an element of randomness that blows away the above;
- meanwhile there's nothing in any of this about how to determine that representative (and there may be no finite-time way to do so?), but it's provable that one does exist.
...right? (he said tentatively.)
Here's a sanity check: if I understand this right, then EP's technique would not work with fewer than infinite mathematicians. It would work with fewer than infinite colors.
By contrast hoople's cyclical technique earlier would need infinite colors, or at least a large enough colorspace to give the sacrificial mathematicians enough informational "room" in their stated guesses to encode information to the next n who will survive, but would be usable with fewer-than-infinite mathematicians.
...riight? (he said even more tentatively)
posted by ook at 11:19 AM on August 28, 2012
So, if I'm following the followups correctly (and thanks, everyone, for patiently helping me sort this out; I feel like the slow kid in class today but this is fun):
- if I'm in line I don't need to listen to the guys behind me, they're not passing me any information;
- each sets contain lists which have a finite number of differences from each other, and an infinite number of correspondencies;
- each mathematician sees an infinite list (the hats in front of him), so knows which set to work with, and that there are only a finite number of possible variations on that list (proportional to the number of hats behind him plus his own);
- therefore by assuming the actual list is a specific representative sample from each set, only a finite number will be wrong;
- but they all have to agree on the same system for selecting that representative sample, otherwise you're introducing an element of randomness that blows away the above;
- meanwhile there's nothing in any of this about how to determine that representative (and there may be no finite-time way to do so?), but it's provable that one does exist.
...right? (he said tentatively.)
Here's a sanity check: if I understand this right, then EP's technique would not work with fewer than infinite mathematicians. It would work with fewer than infinite colors.
By contrast hoople's cyclical technique earlier would need infinite colors, or at least a large enough colorspace to give the sacrificial mathematicians enough informational "room" in their stated guesses to encode information to the next n who will survive, but would be usable with fewer-than-infinite mathematicians.
...riight? (he said even more tentatively)
posted by ook at 11:19 AM on August 28, 2012
Which is why to this day some fundamentalists are leary of set theory.
Previously.
posted by homunculus at 11:39 AM on August 28, 2012
Previously.
posted by homunculus at 11:39 AM on August 28, 2012
Ook: right. Of course, if you have finitely many mathematicians, saving all but finitely many of them is easy.
As was mentioned above, if you have finitely many colors and mathematicians, you can guarantee everyone but the first person lives. In fact, I think finite mathematicians and infinite colors still means you can save all but one.
Now to think about the submarine problem!
posted by Elementary Penguin at 11:48 AM on August 28, 2012
As was mentioned above, if you have finitely many colors and mathematicians, you can guarantee everyone but the first person lives. In fact, I think finite mathematicians and infinite colors still means you can save all but one.
Now to think about the submarine problem!
posted by Elementary Penguin at 11:48 AM on August 28, 2012
lllama, you haven't told us how much feedback you get. Do you get to find out exactly where your nemesis was after you shoot, or do you just find out whether or not it was a hit?
You also haven't imposed any limit to the distance between successive days squares, so she could be at position (Ackermann(n, n+1), Ackermann(n, n+1)) on day n from the way you've stated it. Is that intentional?
posted by benito.strauss at 1:01 PM on August 28, 2012
You also haven't imposed any limit to the distance between successive days squares, so she could be at position (Ackermann(n, n+1), Ackermann(n, n+1)) on day n from the way you've stated it. Is that intentional?
posted by benito.strauss at 1:01 PM on August 28, 2012
The next one is on the integer number line where the nemesis has no restrictions in plotting her course.
I am having a bear of a time with parsing this correctly.
It seems to me that the "plotted course" is a sequence of integers (the planned positions on the number line). There are uncountably many such sequences. How can I plan my destruction scheme in this case? Can I have a hint?
posted by King Bee at 1:10 PM on August 28, 2012 [2 favorites]
I am having a bear of a time with parsing this correctly.
It seems to me that the "plotted course" is a sequence of integers (the planned positions on the number line). There are uncountably many such sequences. How can I plan my destruction scheme in this case? Can I have a hint?
posted by King Bee at 1:10 PM on August 28, 2012 [2 favorites]
∞
posted by Fizz
∞ + 1
posted by three blind mice
three blind mice's comment flagged as a double.
posted by DevilsAdvocate at 1:10 PM on August 28, 2012 [2 favorites]
posted by Fizz
∞ + 1
posted by three blind mice
three blind mice's comment flagged as a double.
posted by DevilsAdvocate at 1:10 PM on August 28, 2012 [2 favorites]
Excellent questions, benito.strauss.
1. The only feedback you get is whether or not you scored a hit.
2. It was intentional. We may as well think of the submarine as teleporting to any grid square at noon each day.
posted by lllama at 1:11 PM on August 28, 2012
1. The only feedback you get is whether or not you scored a hit.
2. It was intentional. We may as well think of the submarine as teleporting to any grid square at noon each day.
posted by lllama at 1:11 PM on August 28, 2012
Here's my problem with the e. penguinic solution (as elucidated by hoople.) I look ahead and see the infinite hats in sequence and know the canonical member of its equivalence class and say the nth (where n is my position) color in that member's sequence. Indeed, we all do that, so in effect, we all are repeating that member. (Not only can we ignore what those behind us have said, we already know what they've said and what everyone else will say just by looking at the hats in front of us. There's nothing special about this canonical representative; it's just a pre-selected example member. The only reason we all need to choose the same one is because we need that fact in our proof that it differs in actuality in only a finite number of locations.
But that is kind of weird, isn't it? Before the wizard even put our hats on, this representative member was chosen and it doesn't matter which one it is. Had a different one been chosen, it would work out the same way. This means, if I decide that I'm a libertarian, and rather choose a different representative member than the other mathematicians chose, for my individual case, since it would have worked just as well, and since I can ignore what everyone else says, I'm in the same position using my representative member. The proof won't work but it looks as though my personal situation remains the same. Too bad for those other mathematicians, though! But how can it be that what I say (which they're not listening to at all since they need not) actually results in those infinite extra deaths?
posted by Obscure Reference at 1:12 PM on August 28, 2012
But that is kind of weird, isn't it? Before the wizard even put our hats on, this representative member was chosen and it doesn't matter which one it is. Had a different one been chosen, it would work out the same way. This means, if I decide that I'm a libertarian, and rather choose a different representative member than the other mathematicians chose, for my individual case, since it would have worked just as well, and since I can ignore what everyone else says, I'm in the same position using my representative member. The proof won't work but it looks as though my personal situation remains the same. Too bad for those other mathematicians, though! But how can it be that what I say (which they're not listening to at all since they need not) actually results in those infinite extra deaths?
posted by Obscure Reference at 1:12 PM on August 28, 2012
Oh man. OK. I think I finally got EP's solution, which I've been trying to get without knowing any set theory. In language free of set theory, here's how I think it goes:
For simplicity, imagine that each hat has a number between zero and nine, so any given arrangement will be a string of digits like "98374553...". The mathematicians have memorized an infinite list of "representative" strings. These are strings with the property that, for any given number you pick, it will eventually start to match up with exactly one of the representative strings. So maybe one of the representative strings is
121212...
and it represents
N21212...,
NN1212...,
NNN212...
etc.
Or maybe one of the representative strings is pi, and it represents
314159
N14159...
NN4159...
NNN159...
etc.
Now because the mathematicians have memorized an infinite list of carefully chosen representative strings, it's guaranteed that if they look far enough down the line, they'll see a point where from there on, exactly one of the representative strings will match up. So they'll look down the line and say "huh, in a million digits this starts lining up with pi, so I should say my digit of pi" and die knowing that while a million of them will die, an infinite number will live once it starts lining up. Or they'll look down the line and say "in 2 billion digits this starts lining up with a random number I memorized, so I should say my digit of that number," and die knowing that 2 billion of them will die, but an infinite number after that will live. We end up with a finite doomed group that doesn't match the representative string, followed by an infinite saved group that does.
So this has a couple of implications:
- If the evil wizard listens in on their scheme, he can kill an arbitrary finite number of them. Any string he picks will eventually start lining up with one the mathematicians memorized, but he can pick one that won't line up for a trillion trillion digits, or however many digits he cares to choose. That's too bad.
- Most of the finite group will know they're in the finite group, so can save some of their number using a Malor/hoople encoding! For example, if the actual string is 345345121212..., and 121212... is a representative string, then mathematicians 1 through 5 will all know that they are in the finite at-risk group, and mathematicians 6 and on won't be sure whether they're in the safe group or it starts right after them. So for example, everyone could agree: if the representative string starts after you, guess 0, and everyone from then on will guess the representative string. So mathematician 6 will guess zero and 7 on will be saved. Mathematicians 1-5 can then ignore the infinite group entirely, and use any encoding scheme that doesn't involve the number zero to save as many of their number as possible. So a really great answer to this problem will include an optimal solution for the finite group as well ...
posted by jhc at 1:15 PM on August 28, 2012
For simplicity, imagine that each hat has a number between zero and nine, so any given arrangement will be a string of digits like "98374553...". The mathematicians have memorized an infinite list of "representative" strings. These are strings with the property that, for any given number you pick, it will eventually start to match up with exactly one of the representative strings. So maybe one of the representative strings is
121212...
and it represents
N21212...,
NN1212...,
NNN212...
etc.
Or maybe one of the representative strings is pi, and it represents
314159
N14159...
NN4159...
NNN159...
etc.
Now because the mathematicians have memorized an infinite list of carefully chosen representative strings, it's guaranteed that if they look far enough down the line, they'll see a point where from there on, exactly one of the representative strings will match up. So they'll look down the line and say "huh, in a million digits this starts lining up with pi, so I should say my digit of pi" and die knowing that while a million of them will die, an infinite number will live once it starts lining up. Or they'll look down the line and say "in 2 billion digits this starts lining up with a random number I memorized, so I should say my digit of that number," and die knowing that 2 billion of them will die, but an infinite number after that will live. We end up with a finite doomed group that doesn't match the representative string, followed by an infinite saved group that does.
So this has a couple of implications:
- If the evil wizard listens in on their scheme, he can kill an arbitrary finite number of them. Any string he picks will eventually start lining up with one the mathematicians memorized, but he can pick one that won't line up for a trillion trillion digits, or however many digits he cares to choose. That's too bad.
- Most of the finite group will know they're in the finite group, so can save some of their number using a Malor/hoople encoding! For example, if the actual string is 345345121212..., and 121212... is a representative string, then mathematicians 1 through 5 will all know that they are in the finite at-risk group, and mathematicians 6 and on won't be sure whether they're in the safe group or it starts right after them. So for example, everyone could agree: if the representative string starts after you, guess 0, and everyone from then on will guess the representative string. So mathematician 6 will guess zero and 7 on will be saved. Mathematicians 1-5 can then ignore the infinite group entirely, and use any encoding scheme that doesn't involve the number zero to save as many of their number as possible. So a really great answer to this problem will include an optimal solution for the finite group as well ...
posted by jhc at 1:15 PM on August 28, 2012
Oh crud. Thanks, King Bee -- your comment makes me realize I completely botched my problem! (Apologies for my sill response to your questions, benito.strauss.)
The easy version is on the integer number line, starting at 0, moving an unknown but fixed n each day.
The next version is the same but with unknown initial position.
The final version is on the integer lattice, with unknown initial position but moving in a straight line at a fixed velocity. (The velocity is such that you always land on a lattice point.)
It really is a pretty problem with a nice solution -- it's a shame I messed up the original.
posted by lllama at 1:22 PM on August 28, 2012
The easy version is on the integer number line, starting at 0, moving an unknown but fixed n each day.
The next version is the same but with unknown initial position.
The final version is on the integer lattice, with unknown initial position but moving in a straight line at a fixed velocity. (The velocity is such that you always land on a lattice point.)
It really is a pretty problem with a nice solution -- it's a shame I messed up the original.
posted by lllama at 1:22 PM on August 28, 2012
UPDATE: ceribus peribus sent me a link to this much better solution that saves all but the first person (It is generalization 2).
Briefly, it works the same as what I posted, but then you have the first person count how many people's hats disagree with the representative, and then encode that information in the color he says. He'll probably die, but everyone else lives!
posted by Elementary Penguin at 1:28 PM on August 28, 2012
Briefly, it works the same as what I posted, but then you have the first person count how many people's hats disagree with the representative, and then encode that information in the color he says. He'll probably die, but everyone else lives!
posted by Elementary Penguin at 1:28 PM on August 28, 2012
On to the submarines: The nemesis's path is specifiable by a start position, a velocity, and a direction, each of which are countable, hence the triple is countable--the paths are thus countable. Choose an enumeration and on day n, hit the nth spot on the nth enumerated path.
posted by Obscure Reference at 1:30 PM on August 28, 2012 [1 favorite]
posted by Obscure Reference at 1:30 PM on August 28, 2012 [1 favorite]
Oh, well then here's Pyry's Extra Variant:
Your Nemesis is a spaceship with a warp drive, and can teleport each day to any (x,y,z) location in space with rational coordinates. Likewise, you have a very high precision weapon that hits a single point with rational coordinates, but which only destroys a spaceship if it exactly hits the singularity in the spaceship's warp drive (a single point). Your Nemesis has no sensors and picks a strategy on the first day which is then unfailingly followed by the ship's autopilot (a deterministic AI). You also have no sensors, but are free to use any strategy, including randomized ones, for picking the location you target each day.
posted by Pyry at 1:36 PM on August 28, 2012
Your Nemesis is a spaceship with a warp drive, and can teleport each day to any (x,y,z) location in space with rational coordinates. Likewise, you have a very high precision weapon that hits a single point with rational coordinates, but which only destroys a spaceship if it exactly hits the singularity in the spaceship's warp drive (a single point). Your Nemesis has no sensors and picks a strategy on the first day which is then unfailingly followed by the ship's autopilot (a deterministic AI). You also have no sensors, but are free to use any strategy, including randomized ones, for picking the location you target each day.
posted by Pyry at 1:36 PM on August 28, 2012
Was about to share that link, but EP best me to it.
I'm still trying to get a deep understanding of the use of the equivalence relation; not sure why it's a necessary step for obtaining a finite difference between the actual sequence and a chosen reference sequence.
For example, using an HSV or RGB approach would allow them to express an infinite number of colors using a triplet of three real numbers (a,b,c). We can simplify this to only one real number if we only consider greyscale colors; the full color solution would not be significantly different. The mathematicians could use 0.0 as their presumed reference color, calculate the difference between each hat's value and zero, add them, modulus by 1.0, and that provides the sum/color representation needed in O'Connor's solution.
posted by ceribus peribus at 1:46 PM on August 28, 2012
I'm still trying to get a deep understanding of the use of the equivalence relation; not sure why it's a necessary step for obtaining a finite difference between the actual sequence and a chosen reference sequence.
For example, using an HSV or RGB approach would allow them to express an infinite number of colors using a triplet of three real numbers (a,b,c). We can simplify this to only one real number if we only consider greyscale colors; the full color solution would not be significantly different. The mathematicians could use 0.0 as their presumed reference color, calculate the difference between each hat's value and zero, add them, modulus by 1.0, and that provides the sum/color representation needed in O'Connor's solution.
posted by ceribus peribus at 1:46 PM on August 28, 2012
express an infinite number of possible colors in a simple triplet
posted by ceribus peribus at 1:48 PM on August 28, 2012
posted by ceribus peribus at 1:48 PM on August 28, 2012
moving in a straight line at a fixed velocity
lllama, if this were the real-world I'd be shooting you the dirtiest of looks over the time I wasted in the shower thinking over the problem as you stated it, when I could have been alphabetizing my shampoos! </just_kidding>
So, on to think about the properly stated version. It does look like a pretty problem.
posted by benito.strauss at 1:51 PM on August 28, 2012
lllama, if this were the real-world I'd be shooting you the dirtiest of looks over the time I wasted in the shower thinking over the problem as you stated it, when I could have been alphabetizing my shampoos! </just_kidding>
So, on to think about the properly stated version. It does look like a pretty problem.
posted by benito.strauss at 1:51 PM on August 28, 2012
Dying in a dungeon waiting for a guy to finish describing the color of his hat is pretty much the same as dying in a dungeon executed by an evil wizard.
Except you get more time to do Mathematics.
posted by weston at 1:58 PM on August 28, 2012 [1 favorite]
Except you get more time to do Mathematics.
posted by weston at 1:58 PM on August 28, 2012 [1 favorite]
Oops, missed Obscure Reference's answer. It must have been obscured by all the references flying around.
posted by benito.strauss at 1:58 PM on August 28, 2012
posted by benito.strauss at 1:58 PM on August 28, 2012
Obscure Reference,
Once you have chosen a sequence and start guessing hat colors from it, the mathematicians can essentially be broken into two subsets. Let M be the set of all mathematicians and L be the subset of all which will live and D be the subset of all that will die such that M = L + D.
By following the agreed upon sequence you personally will end up in either L or D, but the sequence was chosen to that as the number of mathematicians in M approaches infinity, the number of mathematicians in L approaches infinity as well and the number of mathematicians in D approaches some finite number. Your chances of being in D approach 0 as the membership in M and L approach infinity. Why bother going rogue and messing with the already neglible chances that you'll die?
Also, what you say does not in any way condemn mathematicians who will guess after you, since as you point out no one is listening to the other guesses anyway. The only way it all goes wrong is if everyone decides to be a libertarian like you and guess personally prefered colors, at which point the entire line may end up in a different Hattening which diverges infinitely from the actual pattern, condemning an infinite number of libertarian mathematicians.
posted by jermsplan at 2:01 PM on August 28, 2012
Once you have chosen a sequence and start guessing hat colors from it, the mathematicians can essentially be broken into two subsets. Let M be the set of all mathematicians and L be the subset of all which will live and D be the subset of all that will die such that M = L + D.
By following the agreed upon sequence you personally will end up in either L or D, but the sequence was chosen to that as the number of mathematicians in M approaches infinity, the number of mathematicians in L approaches infinity as well and the number of mathematicians in D approaches some finite number. Your chances of being in D approach 0 as the membership in M and L approach infinity. Why bother going rogue and messing with the already neglible chances that you'll die?
Also, what you say does not in any way condemn mathematicians who will guess after you, since as you point out no one is listening to the other guesses anyway. The only way it all goes wrong is if everyone decides to be a libertarian like you and guess personally prefered colors, at which point the entire line may end up in a different Hattening which diverges infinitely from the actual pattern, condemning an infinite number of libertarian mathematicians.
posted by jermsplan at 2:01 PM on August 28, 2012
lllama: Whew! I thought I was going to have to return my PhD and live forever in disgrace! I believe I can solve your submarine problem, and yes, the solution I'm thinking of is nice.
posted by King Bee at 2:07 PM on August 28, 2012
posted by King Bee at 2:07 PM on August 28, 2012
ceribus peribus: the problem is that your first sum doesn't have to converge. Suppose everyone was color 0.5. The partial sums go 0.5, 0.0, 0.5, 0.0,... And never give you a starting place.
posted by Elementary Penguin at 2:12 PM on August 28, 2012
posted by Elementary Penguin at 2:12 PM on August 28, 2012
That's a very nice fix, nicely anticipated by jhc's solution, but note that that specific formulation requires there to be exactly 2 hat colors, whereas jhc's version should scale to any number of hat colors, provided you can devise a 0-avoiding encoding.
ceribus paribus: that's essentially the infinite sum approach I was alluding to, the potential problem with it is that for it to work you need to be able to communicate an infinite-precision real number, which may or may not be allowed (or good sport). To flesh it out a bit: it's not enough to merely compute an infinite sum of the colors in front of you (modulo 1.0) because that sum isn't guaranteed to converge; in your encoding you'd have to do something like summing (encoding(n)/2^n) to enforce convergence, but to communicate that result will require infinite precision, meaning an infinitely-long utterance...whence its debatable fairness, particularly when with such an infinite-length utterance you could just as easily have the first mathematician tell everyone their exact hat color ( it'd take forever, but it's doable in a single infinite sequence...)...
For a finite line of mathematicians convergence isn't an issue.
posted by hoople at 2:17 PM on August 28, 2012
ceribus paribus: that's essentially the infinite sum approach I was alluding to, the potential problem with it is that for it to work you need to be able to communicate an infinite-precision real number, which may or may not be allowed (or good sport). To flesh it out a bit: it's not enough to merely compute an infinite sum of the colors in front of you (modulo 1.0) because that sum isn't guaranteed to converge; in your encoding you'd have to do something like summing (encoding(n)/2^n) to enforce convergence, but to communicate that result will require infinite precision, meaning an infinitely-long utterance...whence its debatable fairness, particularly when with such an infinite-length utterance you could just as easily have the first mathematician tell everyone their exact hat color ( it'd take forever, but it's doable in a single infinite sequence...)...
For a finite line of mathematicians convergence isn't an issue.
posted by hoople at 2:17 PM on August 28, 2012
I'm still trying to get a deep understanding of the use of the equivalence relation; not sure why it's a necessary step for obtaining a finite difference between the actual sequence and a chosen reference sequence.
I think the problem is that for the first mathematician's answer to encode the sum of all following mathematicians, the answer would have to be infinitely long. If you assume the first mathematician has to give an answer of finite length, then he or she can only save a finite number of following mathematicians. The shared knowledge of an infinite number of equivalence relations creates a finite cap after which everyone is saved, so the first mathematician can focus on the finite group at the head of the line.
posted by jhc at 2:18 PM on August 28, 2012
I think the problem is that for the first mathematician's answer to encode the sum of all following mathematicians, the answer would have to be infinitely long. If you assume the first mathematician has to give an answer of finite length, then he or she can only save a finite number of following mathematicians. The shared knowledge of an infinite number of equivalence relations creates a finite cap after which everyone is saved, so the first mathematician can focus on the finite group at the head of the line.
posted by jhc at 2:18 PM on August 28, 2012
Since an infinite number of colors were possible for each hat, I would have demanded that the last person be required to say an infinite precision number anyway...
But the convergence requirement - aha, there's the problem! That makes sense. The last mathematician and the one standing in front of him would have had to work together and rearrange their terms in order to get the difference between their sums, ie. the hat color to guess next. But they can't do that.
Actually, that helps me understand the equivalence relation now, too - it's a function chosen such that the difference converges for all partial sums. Thanks everyone, now I'm on solid ground again.
posted by ceribus peribus at 2:29 PM on August 28, 2012
But the convergence requirement - aha, there's the problem! That makes sense. The last mathematician and the one standing in front of him would have had to work together and rearrange their terms in order to get the difference between their sums, ie. the hat color to guess next. But they can't do that.
Actually, that helps me understand the equivalence relation now, too - it's a function chosen such that the difference converges for all partial sums. Thanks everyone, now I'm on solid ground again.
posted by ceribus peribus at 2:29 PM on August 28, 2012
and functions can be ordered, allowing them to agree in advance to use the "first" one that works
posted by ceribus peribus at 2:31 PM on August 28, 2012
posted by ceribus peribus at 2:31 PM on August 28, 2012
To specify the "sum" of the colors is no harder than to specify a single one of the colors. We're assuming we can impose a group structure on the colors so they sum to: a color.
posted by Obscure Reference at 2:42 PM on August 28, 2012
posted by Obscure Reference at 2:42 PM on August 28, 2012
my favorite part about this very nice thread is that our common interlocutors name is ook. Good boy ook, good cave questions! ;)
posted by Potomac Avenue at 4:19 PM on August 28, 2012 [1 favorite]
posted by Potomac Avenue at 4:19 PM on August 28, 2012 [1 favorite]
Pyry: wouldn't the answer still be essentially the one given by Obscure Reference? That is, because each possible path taken by the nemesis is a countable sequence of rational triples (a, b, c), the set of all possible paths is itself countable. So you just construct an enumeration/ordering of the possible paths, and on the nth day, target the nth location on the nth path. You'd be guaranteed to hit, then, yes?
posted by dilettanti at 4:27 PM on August 28, 2012
posted by dilettanti at 4:27 PM on August 28, 2012
The set of all possible paths is uncountable, which is the tricky bit.
posted by Pyry at 4:48 PM on August 28, 2012 [1 favorite]
posted by Pyry at 4:48 PM on August 28, 2012 [1 favorite]
Its not, though. You can even ignore the velocity. From noon to noon the next day is sufficient to determine a (rational) slope. That plus a start point (e.g. the Y-intercept) gives a countable set of pairs.
posted by Obscure Reference at 5:12 PM on August 28, 2012
posted by Obscure Reference at 5:12 PM on August 28, 2012
But the ship simply teleports from location to location. There is no velocity or slope to speak of.
posted by King Bee at 5:16 PM on August 28, 2012
posted by King Bee at 5:16 PM on August 28, 2012
Good boy ook, good cave questions!
ook eat meat in cave also learn set theory in spare time
posted by ook at 5:19 PM on August 28, 2012 [2 favorites]
ook eat meat in cave also learn set theory in spare time
posted by ook at 5:19 PM on August 28, 2012 [2 favorites]
One subtle distinction is that while the set of all possible finite paths is countable, the set of all infinite paths is not. That is, if you imagine that the Nemesis's strategy is just a long (but finite) list of coordinates, then you could enumerate all such strategies. However, the strategy the Nemesis picks is not a finite list, but an infinite one: for every day in the future, it has to be able to produce a location to teleport to.
As a simplified case, imagine the universe only has two coordinates: A and B. You could enumerate all finite lists of A and B easily: [A, B, AA, AB, BA, BB, AAA, AAB, ABA, ...], but you couldn't enumerate all infinite lists of A and B. For example, Nemesis's strategy could be the infinite, non-repeating sequence ABAABBAAABBB...
posted by Pyry at 5:45 PM on August 28, 2012
As a simplified case, imagine the universe only has two coordinates: A and B. You could enumerate all finite lists of A and B easily: [A, B, AA, AB, BA, BB, AAA, AAB, ABA, ...], but you couldn't enumerate all infinite lists of A and B. For example, Nemesis's strategy could be the infinite, non-repeating sequence ABAABBAAABBB...
posted by Pyry at 5:45 PM on August 28, 2012
I really want to find a reason to use the phrase: "You may end up in a different hattening."
posted by But tomorrow is another day... at 5:54 PM on August 28, 2012
posted by But tomorrow is another day... at 5:54 PM on August 28, 2012
By the way, since you have to be able to guarantee destruction, you have to assume that Nemesis knows what strategy you will use (although if you use a randomized strategy, it won't know what random numbers you'll draw, and it's still restricted by the limitation that it has to choose its strategy on day one and stick to it; it can't change strategies 'mid stream').
posted by Pyry at 5:55 PM on August 28, 2012
posted by Pyry at 5:55 PM on August 28, 2012
Pyry: does your solution require some appeal to notions of computability?
posted by hoople at 5:58 PM on August 28, 2012
posted by hoople at 5:58 PM on August 28, 2012
Well, a deterministic AI is piloting Nemesis, so I'm going to go with 'yes'. If the AI gets stuck in an infinite loop while trying to calculate some day's coordinates, that counts as destruction.
posted by Pyry at 6:08 PM on August 28, 2012
posted by Pyry at 6:08 PM on August 28, 2012
I don't think some of these "all but one mathematician survives" solutions can be right. If there are an infinite amount of mathematicians in front of the first mathematician, it will take an infinite amount of time for the light from some of the other mathematicians to reach him. So if he's going to actually say an answer in his lifetime, he's going to have to say something before he has complete information.
So it's sort of necessarily true that an infinite number of the mathematicians die, at least if we obey physics.
And taking into account that at least some of the mathematicians will be color-blind, the wizard can probably skew the proportion of mathematicians who die in his favor.
Also, it seems to me that the problem requires an infinite number of colors, and I'm not sure that's actually true in reality. There are only a few ways that photons can get created, as far as we know: electrons going from high-energy orbits to low-energy orbits, particle/anti-particle collisions, and so forth. The color of those photons is equal to the energy that created them. Only finitely many of these ways to create photons will be in the right range to create visible light, so there are only finitely many colors. (I'm not entirely sure if this is true, but I've had thoughts along these lines for years, so I'd be happy to hear what's wrong with this argument if it is.)
That said, I guess we did posit a wizard set this situation up, so maybe he's using his magical powers to create photons of energy that can't otherwise physically be created.
But I still think the real problem of coming up with strategies in this problems is the limitations of physics, not mathematics. And based on my experience (at a pretty strong undergraduate math program) if you assume that all of the mathematicians will actually figure out the "correct" solution, you're fooling yourself.
But I suppose I don't have a problem with the wizard taking out this infinity of mathematicians: where do you get enough food to feed them? He's doing us a favor!
posted by grae at 7:29 PM on August 28, 2012
So it's sort of necessarily true that an infinite number of the mathematicians die, at least if we obey physics.
And taking into account that at least some of the mathematicians will be color-blind, the wizard can probably skew the proportion of mathematicians who die in his favor.
Also, it seems to me that the problem requires an infinite number of colors, and I'm not sure that's actually true in reality. There are only a few ways that photons can get created, as far as we know: electrons going from high-energy orbits to low-energy orbits, particle/anti-particle collisions, and so forth. The color of those photons is equal to the energy that created them. Only finitely many of these ways to create photons will be in the right range to create visible light, so there are only finitely many colors. (I'm not entirely sure if this is true, but I've had thoughts along these lines for years, so I'd be happy to hear what's wrong with this argument if it is.)
That said, I guess we did posit a wizard set this situation up, so maybe he's using his magical powers to create photons of energy that can't otherwise physically be created.
But I still think the real problem of coming up with strategies in this problems is the limitations of physics, not mathematics. And based on my experience (at a pretty strong undergraduate math program) if you assume that all of the mathematicians will actually figure out the "correct" solution, you're fooling yourself.
But I suppose I don't have a problem with the wizard taking out this infinity of mathematicians: where do you get enough food to feed them? He's doing us a favor!
posted by grae at 7:29 PM on August 28, 2012
Oh, well then: with that constraint it seems quite straightforward. Only thing I'm a bit unclear on is what the ground rules are vis-a-vis allowed running time for the daily computations. It's still easy if I can assume access to a real-time clock and a daily "drop-dead" cutoff time, otherwise I'd have to brush up on my computability theory to figure out the trick.
posted by hoople at 7:50 PM on August 28, 2012
posted by hoople at 7:50 PM on August 28, 2012
grae, your real objection should be that there aren't enough atoms in the universe to actually be the constituent parts of one person for every integer (much less one mathematician for every integer). If we analyze this situation too closely, then everything falls apart.
Or, if you're going to question an actor's signature on a plastic helmet from a movie based on a comic book, then all of our lives have no meaning!
posted by King Bee at 8:00 PM on August 28, 2012
Or, if you're going to question an actor's signature on a plastic helmet from a movie based on a comic book, then all of our lives have no meaning!
posted by King Bee at 8:00 PM on August 28, 2012
Well, King Bee, you seem to be assuming that the universe is finite. Maybe the universe is infinite, and has an infinite amount of matter in it. (Or am I betraying a lack of knowledge about the universe here? Do we know that the universe is finite? I only toyed with being a physics major; I didn't actually take any non-required physics classes in college.)
I really think the counterargument is the fact that a wizard is involved. I mean, then you get magic, and anything is possible, right?
posted by grae at 9:05 PM on August 28, 2012
I really think the counterargument is the fact that a wizard is involved. I mean, then you get magic, and anything is possible, right?
posted by grae at 9:05 PM on August 28, 2012
The universe may be indeed infinite (although I'm not quite sure what that means), but at least in the observable universe, there are only finitely many atoms.
My main point was that your objection is coloring way too far outside the lines. Forget infinitely many colors, just assume the mathematicians only get white and black hats. Forget that they stand in a line, assume every mathematician can see every other mathematician's hat simultaneously (and has the ability to process this information). Forget that there probably aren't enough atoms to actually be the constituents of one person for every integer. Forget that light travels at a certain speed. Forget that wizards (whatever those are) aren't actually things. Just play with your imagination; suspend the laws of physics for a moment.
The solution that was already presented that uses the axiom of choice still works.
All of these funny puzzles aren't about finding "outs" like you have. They're about solving problems in a realm that isn't really related to the physical realm in which we live. They're about playing with your imagination, which is really what mathematics is about anyway.
posted by King Bee at 10:00 PM on August 28, 2012
My main point was that your objection is coloring way too far outside the lines. Forget infinitely many colors, just assume the mathematicians only get white and black hats. Forget that they stand in a line, assume every mathematician can see every other mathematician's hat simultaneously (and has the ability to process this information). Forget that there probably aren't enough atoms to actually be the constituents of one person for every integer. Forget that light travels at a certain speed. Forget that wizards (whatever those are) aren't actually things. Just play with your imagination; suspend the laws of physics for a moment.
The solution that was already presented that uses the axiom of choice still works.
All of these funny puzzles aren't about finding "outs" like you have. They're about solving problems in a realm that isn't really related to the physical realm in which we live. They're about playing with your imagination, which is really what mathematics is about anyway.
posted by King Bee at 10:00 PM on August 28, 2012
Pyry: "The set of all possible paths is uncountable, which is the tricky bit."
Of course it is. I really should not try to solve math problems while working. But you've got me curious. Since Nemesis has no sensors, Nemesis' path is simply a sequence of rational triples predetermined at the beginning. Even if Nemesis can randomize, we can essentially treat all of his random draws as completed and realized at the beginning. But that doesn't help - because there are uncountably many such possible paths, there is no sequence of triples that hits them all, so I cannot simply select a sequence of my own and guarantee that I will cross Nemesis' path. But I don't see how randomizing helps - any density function over the possible paths Nemesis could take will either select the actual path with probability zero, or will place positive mass on his selected path by accident, because it places non-zero probability mass on only a countable number of paths.
Bottom line - I'm stuck and need help. Even better Googling terms would help.
posted by dilettanti at 10:09 PM on August 28, 2012 [1 favorite]
Of course it is. I really should not try to solve math problems while working. But you've got me curious. Since Nemesis has no sensors, Nemesis' path is simply a sequence of rational triples predetermined at the beginning. Even if Nemesis can randomize, we can essentially treat all of his random draws as completed and realized at the beginning. But that doesn't help - because there are uncountably many such possible paths, there is no sequence of triples that hits them all, so I cannot simply select a sequence of my own and guarantee that I will cross Nemesis' path. But I don't see how randomizing helps - any density function over the possible paths Nemesis could take will either select the actual path with probability zero, or will place positive mass on his selected path by accident, because it places non-zero probability mass on only a countable number of paths.
Bottom line - I'm stuck and need help. Even better Googling terms would help.
posted by dilettanti at 10:09 PM on August 28, 2012 [1 favorite]
If you like this sort of thing, check out Rudy Rucker's novel White Light which is ... sort of a novel about infinity. The main character is a mathematician who ends up traveling to a place which is the physical embodiment of of the different orders of infinity (including aleph-type infinity and c-type infinity). It's utterly bizarre, wonderful, and fascinating.
posted by duien at 10:41 PM on August 28, 2012
posted by duien at 10:41 PM on August 28, 2012
dilettanti: the way I made sense of Pyry's puzzle is to reformulate it like so: your "strategy" and your nemesis's "strategy" are meant to consist of some specific concrete, computable programs. Your nemesis is allowed to examine your strategy *prior* to writing choosing a strategy, but both your program and your nemesis's programs are required to be fixed once the game begins. Your advantage over the nemesis is that you're allowed to consult a source of randomness.
I'm not sure that that's actually the scenario Pyry had in mind but -- assuming a sufficient answer to vague question I had earlier about the bounding the running time -- it is just another "carefully choose an enumeration" problem.
Or, at least, that's what I made of the word problem and supplementary comments about it, but I don't know if that's what Pyry actually meant. I think the point of the randomness is that it's needed to deny your nemesis the ability to use a strategy like "examine your program, and choose a strategy that consults your strategy and then adds an offset, thereby ensuring you never catch the nemesis...".
posted by hoople at 11:58 PM on August 28, 2012
I'm not sure that that's actually the scenario Pyry had in mind but -- assuming a sufficient answer to vague question I had earlier about the bounding the running time -- it is just another "carefully choose an enumeration" problem.
Or, at least, that's what I made of the word problem and supplementary comments about it, but I don't know if that's what Pyry actually meant. I think the point of the randomness is that it's needed to deny your nemesis the ability to use a strategy like "examine your program, and choose a strategy that consults your strategy and then adds an offset, thereby ensuring you never catch the nemesis...".
posted by hoople at 11:58 PM on August 28, 2012
I think if I was a mathematician who had deduced that 2 billion of us would die before we got the right hat sequence, I'd start wondering how many mathematicians a wizard could take out before we went down if we just jumped him as he entered the dungeon. I mean he can't have infinite fireballs right?
posted by EndsOfInvention at 7:18 AM on August 29, 2012
posted by EndsOfInvention at 7:18 AM on August 29, 2012
On Pyry's variation: even though there are uncountable paths the Nemesis could take, there are only a countable number of coordinates he can land on each day. So I can pick a sequence of probability distributions that chooses each coordinate with positive probability every day, and I can randomize my selection of distributions such that Nemesis cannot know which sequence I actually select. With a little hand-waving, I'm willing to believe that the sequence of distributions can be adequately selected so that the chances of hitting Nemesis converges to one. But at best the convergence of any sequence of distributions I choose is almost sure convergence (I'm thinking it's more likely just convergence in probability), so there's a non-empty set of realizations (of measure zero) in which I never hit Nemesis. Can I guarantee I hit Nemesis? Seems it might depend on the definition of "guarantee" because I still can't see a way to get rid of that pesky zero-measure set of realizations where I never do hit him.
I take it it would be helpful if I knew something about computability. I have a vague notion of what a Turing machine is, but that's as far as I've ever gotten. I wish I had had more math in college (and logic, and comp sci, and...), but is there a solution to Pyry's problem that can be comprehended by someone like me who has some familiarity with only the basics of set theory, probability, and combinatorics, but not much else?
posted by dilettanti at 9:38 AM on August 29, 2012
I take it it would be helpful if I knew something about computability. I have a vague notion of what a Turing machine is, but that's as far as I've ever gotten. I wish I had had more math in college (and logic, and comp sci, and...), but is there a solution to Pyry's problem that can be comprehended by someone like me who has some familiarity with only the basics of set theory, probability, and combinatorics, but not much else?
posted by dilettanti at 9:38 AM on August 29, 2012
The randomness is kind of a red herring, actually; you can destroy the Nemesis with a completely deterministic strategy that Nemesis knows you're using. A hint: although there are an uncountably infinite number of infinite paths, could Nemesis actually produce all of them, or are there only a countably infinite number of paths the Nemesis could take? Consider that the Nemesis's strategy must take the form of a (finite) program that is fed into its computer on the first day. Hoople's right that it's basically the same as the submarine problem, but with a different enumeration.
posted by Pyry at 9:45 AM on August 29, 2012
posted by Pyry at 9:45 AM on August 29, 2012
Pyry: I was wondering about the randomness. Anyways, if the solution is what I think it is then the answer to the running time issue is that it's moot: the nemesis must be using a strategy it can compute in some fixed time interval (at pain of losing), but there's no harm for me or my strategy in the event I run out of time on some day (and, say, abstain from firing or use the previous day's calculation because hey, "you never know?"). Or do you need some more-sophisticated way to address the running time issue?
posted by hoople at 10:01 AM on August 29, 2012
posted by hoople at 10:01 AM on August 29, 2012
Since enough time has passed I'll post the aspect of Pyry's problem I'm still unclear on.
The solution I've been assuming Pyry had in mind is for you execute the strategy "on day n, enumerate the nth strategy and run it on input n". Ordinarily you can't get away with enumerating programs like this because most programs will fail to terminate -- and per the famous halting problem you can't identify the ones that won't non-terminating -- but in this specific scenario we can get away with it if I've understood the ground rules correctly: (1) your nemesis's strategy has to pick a strategy that always terminates and (2) there's some implicit upper bound on allowed calculations per round.
Taken together those imply that the days when your program-of-the-day doesn't terminate don't matter, because hitting that limit is proof that that isn't your nemesis's strategy, because your nemesis's strategy has to finish within that limit.
So far so good, however if you get stricter about this implicit upper bound on computation it seems as though you can't actually guarantee a win against the nemesis.
To illustrate this, we assume some arbitrary-but-known upper bound on daily computational steps -- call it L -- and that your strategy is: "on input n, enumerate and simulate the nth strategy on input n; if it fails to terminate by time L-S(P,n), run program P on input n", where P(n) is some fallback strategy with known running time S(P,n).
Now suppose that the nemesis knows that that's your plan, and adopts the strategy "on input n, enumerate and simulate the nth strategy on input n, then add some offset; if it fails to terminate by time L-S(P'(n)), run program P' on input n", where P' is "P(n) + some offset".
So you're running through all strategies one-by-one, and your nemesis is doing the same thing in the same order but adding an offset. Since your nemesis's strategy is a finite program it will eventually be enumerated, and we call that day D-day.
On days n != D, here's what happens by cases:
(1) you and your nemesis both finish within L. Result: miss, due to the offset.
(2) you and your nemesis both switch to your fallbacks. Result: miss, due to the offset.
On D-day itself, what will happen is scenario (2), resulting in a miss. To see this, recall that your strategy is "on input n enumerate the nth program and run it on input n"; it's easy to see that D-day this leads to an infinite recursion and so you will both wind using hitting your fallbacks.
Thus, if you grant both parties access to a clock-equivalent mechanism, you can't actually guarantee a hit in this fashion.
That is, unless you play extremely strict with the limit L *and* grant that there is a nonzero overhead involved in adding those offsets. If you do that, then you open up the possibility for a 3rd scenario on some days, namely:
(3) you finish on time but your nemesis switches to fallback (due to that overhead). Result: on any given day a hit is possible, albeit unlikely.
On the one hand, that overhead means that for any target T there are values of n for which your target will be T but your opponents will choose P'(n) (anything that basically idles until after your opponent would have switched to the fallback, then chooses T), but I don't think that's enough to allow you to guarantee an eventual hit.
That's why I was curious about whether or not there was some more-sophisticated way to address the runtime issue -- something beyond using the clock -- because if you also give the nemesis a clock it doesn't seem like you can actually guarantee a win (at least without further assumptions).
posted by hoople at 10:47 AM on September 2, 2012
The solution I've been assuming Pyry had in mind is for you execute the strategy "on day n, enumerate the nth strategy and run it on input n". Ordinarily you can't get away with enumerating programs like this because most programs will fail to terminate -- and per the famous halting problem you can't identify the ones that won't non-terminating -- but in this specific scenario we can get away with it if I've understood the ground rules correctly: (1) your nemesis's strategy has to pick a strategy that always terminates and (2) there's some implicit upper bound on allowed calculations per round.
Taken together those imply that the days when your program-of-the-day doesn't terminate don't matter, because hitting that limit is proof that that isn't your nemesis's strategy, because your nemesis's strategy has to finish within that limit.
So far so good, however if you get stricter about this implicit upper bound on computation it seems as though you can't actually guarantee a win against the nemesis.
To illustrate this, we assume some arbitrary-but-known upper bound on daily computational steps -- call it L -- and that your strategy is: "on input n, enumerate and simulate the nth strategy on input n; if it fails to terminate by time L-S(P,n), run program P on input n", where P(n) is some fallback strategy with known running time S(P,n).
Now suppose that the nemesis knows that that's your plan, and adopts the strategy "on input n, enumerate and simulate the nth strategy on input n, then add some offset; if it fails to terminate by time L-S(P'(n)), run program P' on input n", where P' is "P(n) + some offset".
So you're running through all strategies one-by-one, and your nemesis is doing the same thing in the same order but adding an offset. Since your nemesis's strategy is a finite program it will eventually be enumerated, and we call that day D-day.
On days n != D, here's what happens by cases:
(1) you and your nemesis both finish within L. Result: miss, due to the offset.
(2) you and your nemesis both switch to your fallbacks. Result: miss, due to the offset.
On D-day itself, what will happen is scenario (2), resulting in a miss. To see this, recall that your strategy is "on input n enumerate the nth program and run it on input n"; it's easy to see that D-day this leads to an infinite recursion and so you will both wind using hitting your fallbacks.
Thus, if you grant both parties access to a clock-equivalent mechanism, you can't actually guarantee a hit in this fashion.
That is, unless you play extremely strict with the limit L *and* grant that there is a nonzero overhead involved in adding those offsets. If you do that, then you open up the possibility for a 3rd scenario on some days, namely:
(3) you finish on time but your nemesis switches to fallback (due to that overhead). Result: on any given day a hit is possible, albeit unlikely.
On the one hand, that overhead means that for any target T there are values of n for which your target will be T but your opponents will choose P'(n) (anything that basically idles until after your opponent would have switched to the fallback, then chooses T), but I don't think that's enough to allow you to guarantee an eventual hit.
That's why I was curious about whether or not there was some more-sophisticated way to address the runtime issue -- something beyond using the clock -- because if you also give the nemesis a clock it doesn't seem like you can actually guarantee a win (at least without further assumptions).
posted by hoople at 10:47 AM on September 2, 2012
« Older "And beauty slandered with a bastard shame:" | Malcolm Browne, 1931-2012 Newer »
This thread has been archived and is closed to new comments
posted by Fizz at 5:30 AM on August 28, 2012