Math Olympiad problem - Applying induction and the pigeon hole principle

Ok, so this problem looks like an induction problem to me, so I used that, but I only got as far as the induction hypothesis. The hint says to use the pigeon hole principle. I'm not sure how to use that for this problem.