

ihor
Supreme Hero
Accidental Hero

posted April 13, 2011 02:30 PM 


Warmonger, LOL .
Happy birthday dimis!


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted April 13, 2011 03:00 PM 


Thank you, both of you guys! All my best to you too.
Regarding the twobox problem, and the equality of the amounts when we switch:
If x and 2x are the values in the two boxes, then their difference is 2xx = x. So we lose or gain the same amount when we switch. I really thought this was a classic.
By the way, those two propositions are not mine; they are taken from the excellent book by Smullyan "Satan, Cantor, and Infinity". More.
As of Corribus problem, I will come to that one too at some point.
____________
The empty set


ihor
Supreme Hero
Accidental Hero

posted April 14, 2011 08:46 PM 


Oh, if you mentioned about two boxes  check this out too.
There are some interesting and history facts about the problem.


Corribus
Hero of Order
The Abyss Staring Back at You

posted April 22, 2011 06:21 PM 


Anybody interested in another problem?
The Spider and the Ant
A spider and an ant are on opposite corners of a regular cube. The ant cannot move and the spider is hungry. If the spider is able to move only along an edge of the cube, and he choses his direction randomly, and it takes 1 minute to move from one corner to an adjacent corner, what is the expected (i.e., mean) amount of time it takes the spider to reach his meal?
What if the ant is moving as well, at the same speed, also in a random direction? (Actually, I don't know the answer to this part  I made it up. )


ihor
Supreme Hero
Accidental Hero

posted April 22, 2011 06:55 PM 


Is it possible that spider chooses his direction backward from where he came? I mean from vertice A to vertice B and then to vertice A again.
So if I understand correctly, whenever spider is in one of the vertices, he then moves to one of the 3 adjactent vertices with equal probability.


Corribus
Hero of Order
The Abyss Staring Back at You

posted April 22, 2011 07:37 PM 


Quote: So if I understand correctly, whenever spider is in one of the vertices, he then moves to one of the 3 adjactent vertices with equal probability.
Yes, we will assume the spider "has no memory".
Obviously, you could solve the problem for other limiting cases as well.
As always, a fundamentally more challenging problem would be to solve it for highorder regular polyhedrons. For instance, what is the amount of expected time for a regular polyhedron of nfaces? Well that's probably getting too complicated, so for the math thread let's stick to a cube.


ihor
Supreme Hero
Accidental Hero

posted April 22, 2011 09:05 PM 

Edited by ihor at 21:05, 22 Apr 2011.

Hmm, on one hand I have got the result of 3.5 minutes, but on the other hand it is obvious that the result should be more than
3*(2/9) + 5*(7/9) = 41/9 > 3.5
Definetely I need this weekend for rest. Don't know where's a flaw in my calculations for now.
Interesting, but by guessing the terms of the series, where kth term is a probability that the spider will get the meal in exactly (2k+1) minutes, and summation the series I've got 436/75, but this doesn't seem to be nice number .
I'll try to gather my thoughts alltogether and find out whats wrong when have time.


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted April 22, 2011 09:32 PM 


Regarding the spider and the ant problem, both questions have been answered earlier in the thread. They are just here in disguise, again.
For example, regarding the second question where the ant also moves, the answer is "never".
____________
The empty set


smithey
Promising
Supreme Hero
Yes im red, choke on it !!!

posted April 22, 2011 09:33 PM 


Quote: Anybody interested in another problem?
The Spider and the Ant
A spider and an ant are on opposite corners of a regular cube. The ant cannot move and the spider is hungry. If the spider is able to move only along an edge of the cube, and he choses his direction randomly, and it takes 1 minute to move from one corner to an adjacent corner, what is the expected (i.e., mean) amount of time it takes the spider to reach his meal?
What if the ant is moving as well, at the same speed, also in a random direction? (Actually, I don't know the answer to this part  I made it up. )
Either you haven't copied the question right or you have simply invented it, because it makes no sense. You cant ask for a solution of average time if the scenario of the loop is present, spider can go from a to b and back to a infinite number of times if he has no memory


Warmonger
Promising
Legendary Hero
fallen artist

posted April 22, 2011 09:43 PM 


Yes, but the chance of this happening is inifitely small
I'm afraid it involves Markov chain to solve it properly. Flow graph may come in handy as well, but doing it with trivial arthitmetic may be a pain.
____________
The future of Heroes 3 is here!


Corribus
Hero of Order
The Abyss Staring Back at You

posted April 22, 2011 09:49 PM 

Edited by Corribus at 21:54, 22 Apr 2011.

Quote: Either you haven't copied the question right or you have simply invented it, because it makes no sense. You cant ask for a solution of average time if the scenario of the loop is present, spider can go from a to b and back to a infinite number of times if he has no memory
It's certainly possible that I transcribed a detail wrong, but not for the reasons you have suggested. As warmonger said, this is a low probability outcome. In fact, if the points are accessed randomly, it is inevitable that eventually the spider will arrive at every corner at some point. (This is basically analogous to classical problems in statistical mechanics.) The question is: what is the average number of moves (or amount of time) it takes for the spider to arrive on the corner directly opposite?
Ihor's answer is not correct according the published answer I have.
EDIT: By the way, according to published solution this problem only requires fairly simple algebra and basic probability.


ihor
Supreme Hero
Accidental Hero

posted April 22, 2011 09:50 PM 


Quote: You cant ask for a solution of average time if the scenario of the loop is present
No, you are wrong. The probability of infinite loop will be 0 in this case. Actually the probability of the event that spider will return to the starting point after k moves tends to 0, as k tends to infinity.


Corribus
Hero of Order
The Abyss Staring Back at You

posted April 22, 2011 09:59 PM 


@@dimis
Quote: For example, regarding the second question where the ant also moves, the answer is "never".
Really? I can't believe that. There's only 8 possible positions. Surely they will eventually end up on the same space if they're both moving randomly!
____________
I'm sick of following my dreams. I'm just going to ask them where they're goin', and hook up with them later. Mitch Hedberg


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted April 22, 2011 10:01 PM 


I know Corribus. Sounds insane, but it is true. And you can prove it. Just like you can prove the 25/3 for the first part. You are just a minor click away ...
____________
The empty set


ihor
Supreme Hero
Accidental Hero

posted April 22, 2011 10:06 PM 


Corribus, paint your vertices in two colors, so 2 adjactent are of different colors. In this case at the end of every minute ant and spider will for sure be on the vertices of different color.
I think this is what dimis had in mind.
But the problem has to be clarified if its possible so spider and and will meet on the middle of an edge...


Corribus
Hero of Order
The Abyss Staring Back at You

posted April 22, 2011 10:08 PM 


Alright dimis, actually after a quick moment of thought, I see how you're right. Because they're always moving a single position each turn, they always have an even number of positions between them, so it's impossible for them to arrive at the same position on the same turn. (Although, they CAN cross paths  which you'd think would equate to the spider catching the ant! If we include that in our "condition" for spider victory, can we find a solution then?)
So let me ask, does it change things if, in addition to being able to move in a random direction, the spider (and the ant) have the possibility of waiting one turn without moving at all. Say the probability of waiting is 25% and of choosing each direction is also 25%. NOW they have a chance to land on the same position at the end of a turn, no?
By the way, what is 25/3?
____________
I'm sick of following my dreams. I'm just going to ask them where they're goin', and hook up with them later. Mitch Hedberg


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted April 22, 2011 10:10 PM 


25/3 is the answer to the first part of the problem.
And yes, if you allow them to stay put, now they will meet at a vertex. This variation has also been solved earlier on the thread! Amazing ???
As of meeting along the edge, I will leave that to smithey!
____________
The empty set


Corribus
Hero of Order
The Abyss Staring Back at You

posted April 22, 2011 10:12 PM 

Edited by Corribus at 22:13, 22 Apr 2011.

Quote: 25/3 is the answer to the first part of the problem.
That's not the answer that was published elsewhere.
EDIT: Maybe we should have a list of problems discussed posted in the master post. I don't remember having read this one, sorry.
____________
I'm sick of following my dreams. I'm just going to ask them where they're goin', and hook up with them later. Mitch Hedberg


dimis
Responsible
Supreme Hero
Digitally signed by FoG

posted April 22, 2011 10:15 PM 

Edited by dimis at 22:17, 22 Apr 2011.

That other thing is wrong then, or the calculations I made on a receipt were wrong.
I don't think that my calculations were wrong though, so there!
Anyway, later tonight.
Oh, yes, I have to make a post with the different problems that we have seen. Actually, it was you the one who suggested the same problem in the past (both ant and spider move or stay put on every "tick") ...
____________
The empty set


ihor
Supreme Hero
Accidental Hero

posted April 22, 2011 10:17 PM 


Quote: 25/3 is the answer to the first part of the problem.
Damn, it won't be interesting to investigate then . Though, if Corribus has another answer it will .
And I also don't remember this problem in this thread, maybe its somewhere before page 20...


