Q. (Apparently it's a lengthy description) N toys are to be distributed randomly among N children. There is an interesting way for the children to choose the toys so that no two of them will choose the same toy. A graph such as that shown in Fig is drawn where there are N vertical lines and an arbitrary number of random horizontal segments between adjacent vertical lines with the stipulation that no two horizontal segments meet at the same point. The N toys are assigned to the bottoms of the vertical lines, and each child chooses as a starting point the top of a vertical line. From this starting point, the child will trace a path downward. However, whenever the child runs into a horizontal segment, he or she must turn horizontally, and then turn downward again when the adjacent vertical line is reached. For example, Fig.(b) shows the path that John follows. It is claimed that no matter how many horizontal segments are drawn, in whatever possible way, no two children will reach the same toy. Prove this claim by induction on the number of horizontal segments drawn. Image:
What I have tried: Not much except I the obvious... Base case: For N vertical lines and horizontal segment h = 0, we have obvious result that every child will get different toy. Induction hypothesis: Assuming every child gets different toy for h = k segments. Induction: Proof for h = k + 1 What I thought is that we could divide the N lines by half then each part of graph will have less than k+1 segments. But this might not necessarily be true since the concentration of all k+1 can be on one side of the graph.
It's actually not a HW problem so I do not have any guide to help me through it. Any hint will be greatly appreciated!
Thank you for you valuable time!
According to JMoravitz in this comment: