Author |
Topic: The robot and the coins (Read 775 times) |
|
BNC
Uberpuzzler
Gender: 
Posts: 1732
|
 |
The robot and the coins
« on: Oct 21st, 2003, 9:17am » |
 Quote  Modify
|
In a room there are many coins on the floor (assume a very large number). They display either "heads" or "tails" randomally.
A robot enters the room. It walks around randomaly, and is programed as follows:
- If it sees a coin diplaying "heads" it will turn it over to display "tails".
- If it sees a coin displaying "tails", it will flip the coin (all coins are fair).
After a long enough time, will the ratio of heads to tails converge? If no, why? And if yes, to what value?
|
|
 IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: The robot and the coins
« Reply #1 on: Oct 21st, 2003, 9:36am » |
Quote Modify
|
If we take an simplified version of the riddle and say there are C coins with t0=.5*C where t is the number of tails and the subscript is a pass through all of the coins. Lets make this simplified version say that the robot goes through all coins once and then repeats himself.
thus, tn=C-tn-1+.5*tn-1
or
tn=C-.5*tn-1
Now to check to see the convergence of series.. man has that been a long time.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: The robot and the coins
« Reply #2 on: Oct 21st, 2003, 9:43am » |
Quote Modify
|
Sounds like the robot will just get stuck on the first coin it finds ...
"A head, eh? Better turn 'er over ... okay, now it's a tail. Time to flip it ... still a tail; flip it again ..."
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: The robot and the coins
« Reply #3 on: Oct 21st, 2003, 9:46am » |
Quote Modify
|
Well, it will converge.. But I don't know whereto.. something like 0.5 +-0.1
on Oct 21st, 2003, 9:43am, James Fingas wrote:A canadian robot ? 
|
| « Last Edit: Oct 21st, 2003, 9:48am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: The robot and the coins
« Reply #4 on: Oct 21st, 2003, 9:48am » |
Quote Modify
|
With the idea of passing over all coins in series I finally figured out how to find the limit... and of course feel stupid I forgot how.
So, the series method converges to 2/3 tails. I am not sure how confiident we can be that this expands to the general solution.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: The robot and the coins
« Reply #5 on: Oct 21st, 2003, 10:15am » |
Quote Modify
|
on Oct 21st, 2003, 9:43am, James Fingas wrote:
"A head, eh? Better turn 'er over ... okay, now it's a tail. Time to flip it ... still a tail; flip it again ..." |
|
Yeah right, assuming multiple operations on the same coin. However, the other interpretation is more interesting and must surely be the intended one. That is, we move from coin to coin.
:
We can model it as a differential equation:
Let the initial number of heads in the room be H
Let the initial number of tails in the room be T
Then
dH/dt = (T/2)/(T+H)
dT/dt = (T/2 + H)/(T+H)
Giving dT/dH = 2(H/T) + 1
I can't remember offhand how to solve this.  Integrating factor perhaps?
Or am I using a sledgehammer to crack a nut?
on Oct 21st, 2003, 9:46am, towr wrote:
A canadian robot ? |
|
|
| « Last Edit: Oct 21st, 2003, 11:30am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: The robot and the coins
« Reply #6 on: Oct 21st, 2003, 10:16am » |
Quote Modify
|
::If the series converges, then both processes that cause change will have to be in equilibrium, so
ph (chance of loosing a head) must equal (1-ph)/2 (chance of gaining a head)
so ph = 1/3, and the ratio ph/pt =1/2
::
|
| « Last Edit: Oct 21st, 2003, 10:20am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: The robot and the coins
« Reply #7 on: Oct 21st, 2003, 10:28am » |
Quote Modify
|
Quote:
All you have to do now is prove that it does converge.
|
| « Last Edit: Oct 21st, 2003, 11:31am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: The robot and the coins
« Reply #8 on: Oct 21st, 2003, 10:58am » |
Quote Modify
|
That's easy enough to show, since there are two processes that work against each other, and they get stronger as the result of the other grows..
More notably, for ph < 1/3 the probability we gain a head (and loose a tail) is greater than the reverse
and for ph > 1/3 vice versa.
Or you could just run a simulation and see that it converges 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: The robot and the coins
« Reply #9 on: Oct 21st, 2003, 11:21am » |
Quote Modify
|
Excellent, then the series method is indicitave of the larger problem. I guess it would be the discritized version.
It actually converges pretty quickly too.
|
| « Last Edit: Oct 21st, 2003, 11:22am by aero_guy » |
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: The robot and the coins
« Reply #10 on: Oct 23rd, 2003, 10:37pm » |
Quote Modify
|
I did this one by looking at the flipping of each coin as a Markov process, with transition matrix:
1/2 1
1/2 0
We then want the steady-state vector. The answer will be an eigenvector of this matrix with eigenvalue 1, normalized to have components summing to 1, i.e.:
1/3 //heads
2/3 //tails
The coins don't interact with each other at all, so the probability of any coin being a head in the long run is the same as the expected proportion of heads among all the coins. The number of coins doesn't matter.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print