I'm struggling hard to prove the following statement/riddle by induction, it is given in the current assignement as a challenge. I really want to understand how to exactly approach such excersises. The riddle is on german so I will try to translate:
In a Zoo there are$\ k$ monkeys and$\ k$ monkey bars (or climbing poles), where as at the top of each bar/pole there hangs a banana. Between adjacent bars there are a total of $\ n $ cross-connections, in which at a bar there are no two connections that begin at the same height. The monkeys now choose all different bars and start climbing. Everytime a monkey encounters a cross-connection he switches the bar and climps on there. As soon as he reaches the top of the bar, he takes (if available) the banana.
Show that for any valid arrangement of the $\ n $ cross-connections that every ape gets a banana.
I know how to proof by Induction, but more like proving $\ 1^3+ 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$ instead of riddles like the one above.
Thanks for your help and time!
The base case is when there is only 1 connenction between say bars $k_1\ and\ k_2$ .The monkeys climbing other poles go straight up and the monkeys at $k_1\ and\ k_2$ switch positions.
Now,assume it is true for n connections.When ${n+1}^{th}$ connection is added look at the connection at lowest height.
First,the monkeys there swap positions , and the rest just move up. Now , it is reduced to a problem with n connection which is true by induction.