Problem of the day

[jay_shark]

There are five ladders. There are also some ropes. Each rope attaches a rung of one ladder to a rung of another ladder. No ladder has two ropes attached to the same rung. A monkey starts at the bottom of each ladder and climbs. Each time it reaches a rope, it traverses the rope to the other ladder and continues climbing up the other ladder. Show that each monkey eventually reaches the top of a different ladder.

[djames]

Since no rung has two ropes attached to it, there can be no cycles. That is, there is no way a monkey can leave a rung on a particular ladder and return to that same rung on that ladder. I'm not typing out all of the cases as there's likely a slick all-encompassing argument. The idea is that if the cycle is on the kth rung, then the monkey needs to return to this ladder on the kth rung or lower. The lower property can be used in one case with induction to squeeze down to the 1st rung getting a contradiction.

Now, since the rungs in total are finite, there are a finite number of ropes. Since there are no cycles, there are a finite number of monkey movements (i.e. either up or across a rope). Thus, eventually, each monkey must be atop a ladder.

Assume two monkeys are atop the same ladder. If this ladder has no ropes attached to it, then two monkeys started on this ladder, which is a contradiction. There is at least one rope attached to this ladder. Consider the last such rope. Reversing both monkeys steps, it must be true that both monkeys crossed to this ladder along this last single rope. There is only one such rope since no two ropes both attach to the same rung on this ladder. Now the monkeys are on some other ladder. Again, there are either no ropes (contradiction) or is a next lower rope at least one rung lower. Continue and we see that these two monkeys must have started on the same ladder .. contradiction. So no two monkeys are atop the same ladder.

Good enough?

[djames]

Wait, I see the obvious mistake in the first paragraph. I'll try to reformulate that part.

[jay_shark]

Very nice Djames !!

[theweatherman]

Can it be this simple or am I missing something?

a R R R R R
b R_R R R R
c R R_R R R
d R R R_R R
e R R R R_R
f R R R R R
. M M M M M
. 1 2 3 4 5

R=rung
M=monkey
_=rope

M1 ends on ladder 2
M2 ends on ladder 3
M3 ends on ladder 4
M4 ends on ladder 5
M5 ends on ladder 1

[djames]

[ QUOTE ]
Can it be this simple or am I missing something?

[/ QUOTE ]

I believe the question states there are 5 ladders and 5 monkeys, but the number of rungs and ropes are unlimited. Your case is one possibility, but the question was to prove that the fact that each rung has at most one rope tied to it is all that is needed to show the result holds for any number of rungs & ropes.

[lifes3ps]

is there no reason why the ladders cant be in a circle so the end ladders also are connected?

[holmansf]

I don't see where you use the fact that there are five ladders. Seems like this should work for any number, or am I missing something.

[jay_shark]

It doesn't matter . The most important part about this question is to realize that that every monkey started off on a different ladder and that there are a finite number of rungs .If there are a finite number of rungs , then eventually the monkey must reach the top of some ladder . Since there are no cycles and no monkey can be in the same spot twice .

You can pose this question with n ladders and n monkeys and you'll get the same result in the end . Occasionally , many competition problems pose questions involving numbers that don't have anything to do with the problem . They may be present to confuse the problem solver into thinking that 5 monkeys and 5 ladders plays an important role in the question when in fact it doesn't .

[Silent A]

Why can't I stop thinking about Amidar (http://en.wikipedia.org/wiki/Amidar)?