Author |
Topic: Infinite Quarter Sequence (Read 10365 times) |
|
tim
Junior Member
Posts: 81
|
 |
Infinite Quarter Sequence
« on: Jul 29th, 2002, 3:37am » |
 Quote  Modify
|
This one took me almost as long as the 100 prisoners and light bulb.
I first came up with a pseudo-solution that technically met the requirements of the problem, but was exceedingly inelegant and probably isn't what was wanted: first divide all the quarters into odd-numbered and even-numbered piles. Then flip them all over. That gives you exactly aleph-nought (infinite) tails in each pile. Unfortunately it requires that you be able to operate on infinite sets. All very well for mathematics, but not so useful in practice.
The true solution became apparent when I tried a more probabilistic approach: If you remove N coins from the sequence, what is the probability that you get T tails? Then if you flip F of your N coins, what is the probability that you end up with equal numbers of tails in your small pile as in the remainder?
Once I asked myself that question, the true answer became obvious very quickly. 
|
| « Last Edit: Sep 1st, 2003, 7:07pm by Icarus » |
 IP Logged |
|
|
|
bartleby
Guest
|
|
Re: Infinite Quarter Sequence (Strong Hint)
« Reply #1 on: Jul 29th, 2002, 10:19am » |
Quote Modify
 Remove
|
Are you just saying that 20 Tails quarters "evenly distributed" across an infinite number of Heads quarters yields a probability of 0 of getting those 20 Tails if you chose a finite subset of them?
In which case....
Just willy-nilly make two piles of quarters as large as you can possibly make them, because probability says that you're sure to have 0 Tails quarters in either of them!
|
|
IP Logged |
|
|
|
Alex Harris
Guest
|
|
Re: Infinite Quarter Sequence (Strong Hint)
« Reply #2 on: Jul 29th, 2002, 12:26pm » |
Quote Modify
Remove
|
My solution for the problem was the same as your initial solution and then I moved on since it seemed like an uninteresting problem. Maybe there is more here but I'm confused by your hints.
What is the probability that we get T tails if we remove N coins? Unknown unless we know the distribution of tails which we don't. We can't pick uniformly random quarters from the list in any finite way, and if we're messing about with doing infinite things we're back to the first solution. Maybe I need to think more but the "hints" here don't make sense to me.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Re: Infinite Quarter Sequence (Strong Hint)
« Reply #3 on: Jul 29th, 2002, 1:46pm » |
Quote Modify
|
Here are some of my hints. First, the correct algorithm should run in a finite amount of time -- in fact, if I gave you an infinite sequence of quarters laid on some table of infinite area, you should be able to pull off the trick in less than 30 seconds.
Further, if the notion of infinite quarters confuses you, try replacing infinity with 100. So there are 100 quarters, 20 of which are tails.
happy hacking
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Alex Harris
Guest
|
|
Re: Infinite Quarter Sequence (Strong Hint)
« Reply #4 on: Jul 29th, 2002, 2:06pm » |
Quote Modify
Remove
|
I see. Highlight for solution:
I wasn't letting myself count the remaining infinite set of quarters as one of my piles in looking for a "finite" solution. If thats legal then just take 20 as one pile, flip them, and call the remainder the second pile
|
|
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: Infinite Quarter Sequence (Strong Hint)
« Reply #5 on: Jul 29th, 2002, 5:34pm » |
Quote Modify
|
Alex: You are correct that the first question P(T tails in N selected) has no answer. That's what led me to the solution. I concentrated on the second part -- for about 10 seconds, arriving at the same answer you got.
I'm not sure why you weren't letting yourself count the remaining infinite set as one of your piles -- the problem statement doesn't let you do anything else. If you were allowed to make two finite piles, you could just put zero coins in each 
|
|
IP Logged |
|
|
|
Alex Harris
Guest
|
|
Re: Infinite Quarter Sequence (Strong Hint)
« Reply #6 on: Jul 29th, 2002, 8:31pm » |
Quote Modify
Remove
|
Clearly I shouldn't have excluded that possiblity, but the both piles 0 thing doesn't follow. Its a stretch to call 0 quarters a "pile" and since thats obviously not what was intended I wasn't going to go there.
Hrm. In the preview that black text was invisible, but in the post itself the background isn't black anymore. Oh well.
|
|
IP Logged |
|
|
|
GrapeShasta
Newbie
Posts: 1
|
|
Re: Infinite Quarter Sequence (Strong Hint)
« Reply #7 on: Sep 5th, 2002, 3:31pm » |
Quote Modify
|
on Jul 29th, 2002, 1:46pm, william wu wrote:Here are some of my hints. First, the correct algorithm should run in a finite amount of time -- in fact, if I gave you an infinite sequence of quarters laid on some table of infinite area, you should be able to pull off the trick in less than 30 seconds.
Further, if the notion of infinite quarters confuses you, try replacing infinity with 100. So there are 100 quarters, 20 of which are tails.
|
|
Replace infinity with 100? Doesn't that make the problem impossible? Is that a hint to throw people off?
With infinite quarters, though, the problem is a cinch, because if you take any 20 quarters from the pile, what are the odds of getting tails on any of them? So, then, if you flip that set of 20 over, what do you have?
I'll tell you what you have: You're not going to have anyplace to keep infinite quarters, so they'll be rolling out into the streets. There will be a period of chaos as people fight for them. Eventually, they become worthless, and the US economy collapses. Soon, though, people aren't concerned about this, because the quarters are starting to overtake the landscape and destroy the planet. Soon everyone is dead, which is actually a good thing, since they don't have to watch the continuing destruction of our planet, solar system, and eventually the cosmos as it becomes a series of black holes of massive quarter groups collapsing in on themselves.
So the solution is to take one quarter, call it a pile, and lose, thus saving the universe!
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Infinite Quarter Sequence (Strong Hint)
« Reply #8 on: Sep 6th, 2002, 10:06am » |
Quote Modify
|
True, mathematically speaking the probability of getting any of the twenty tails floating in an infinite sea of heads is zero. But you might be missing the point -- even if some of the coins in your chosen set of 20 ARE tails, once you flip them over it doesn't even matter. The number of tails in the chosen set, and the remainder set, will be the same. And this trick works for any set of coins with cardinality greater than 20. My hint helps if someone is having trouble wrapping his or her head around this concept of infinity.
Example:
Without loss of generality, let's say you have 7 coins, 5 of which are tails. I claim you can choose any 5 of these 7 coins, flip your chosen coins, and the number of tails in the chosen set and the remainder set will be identical.
7 coins, 5 of which are tails.
Chosen Remainder
HTTHT TT
Flipped chosen
THHTH
Tails in inverted chosen = 2 = Tails in Remainder
It should be easy to prove you can do this for any set of coins with size > N, where N = number of tails.
Perhaps I should replace the word infinity with 100,000,000,000 or something.
|
| « Last Edit: Sep 6th, 2002, 10:07am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Jeremiah Smith
Full Member
Beep!
Posts: 172
|
|
Re: Infinite Quarter Sequence (Strong Hint)
« Reply #9 on: Sep 6th, 2002, 10:06am » |
Quote Modify
|
on Sep 5th, 2002, 3:31pm, GrapeShasta wrote:
You're not going to have anyplace to keep infinite quarters, so they'll be rolling out into the streets. .... So the solution is to take one quarter, call it a pile, and lose, thus saving the universe!
|
|
This is totally off the topic of the actual problem...but wouldn't that happen anyway? I mean, where are all these quarters before you start? 
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: Infinite Quarter Sequence (Strong Hint)
« Reply #10 on: Sep 14th, 2002, 11:37pm » |
Quote Modify
|
After thinking really hard for a good quarter of an hour, I came up with the extremely elegant solution. This rewarding feeling is priceless. I love this site. Thank you so much for NOT putting the answers up, Will.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
t-bone
Guest
|
|
Re: Infinite Quarter Sequence (Strong Hint)
« Reply #11 on: Oct 18th, 2002, 3:34am » |
Quote Modify
Remove
|
aren't you all making a big assumption...it never said anything about a quarter
|
|
IP Logged |
|
|
|
Rujith de Silva
Newbie
Gender:
Posts: 22
|
|
Re: Infinite Quarter Sequence (Strong Hint)
« Reply #12 on: Apr 25th, 2003, 11:40am » |
Quote Modify
|
Here's the answer:
Put 20 coins at random into one pile. Assume you got k tails in this
pile, where 0 <= k <= 20. Then the remaining coins, constituting the
second pile, have (20-k) tails. Flip all 20 coins in the first pile.
As it previously had k tails, now it'll have (20-k) tails, the same as
the number of tails in the second pile.
I found this puzzle easy, because, perversely, it appeared so
impossible to do that I knew the solution had to be something very
simple!
|
|
IP Logged |
|
|
|
Aneon
Newbie
Gender:
Posts: 2
|
|
Re: Infinite Quarter Sequence
« Reply #13 on: Jul 4th, 2007, 1:34am » |
Quote Modify
|
I came up with the same answer, It took me quite some time though.
It is a good riddle because it is completely logical and it still works no matter how many coins you use.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Infinite Quarter Sequence (Strong Hint)
« Reply #14 on: Jul 4th, 2007, 3:10am » |
Quote Modify
|
on Jul 29th, 2002, 8:31pm, Alex Harris wrote:| Hrm. In the preview that black text was invisible, but in the post itself the background isn't black anymore. Oh well. |
|
| hidden: | | Use HIDE BLOCK icon to hide some text instead. ... You can edit your messages (may be only if you are not guest?) ... |
Or you can use HIDE ICON
P.S.: I like this puzzle ... (I had known finite version, what may be psychologically harder, infinite one is cleaner )
towr (next post): OK, so good job that this feature is available now 
|
| « Last Edit: Jul 4th, 2007, 5:40am by Hippo » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Infinite Quarter Sequence
« Reply #15 on: Jul 4th, 2007, 3:47am » |
Quote Modify
|
When he posted that 5 years ago, the forum didn't have hide tags yet 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print