CSE 215 Lecture 17: Induction Practice Problems
31 Mar 2017
School
Department
Course
Professor
Document Summary
The results of this tournament can be represented by a directed graph. So if we have a sequence d,c,a,b,e where they are ordered as t1, t2,t3,t4, t5, that means d beats c, c beats. The claim is this problem is that no matter what graph we have, we can always write that it is always possible to have one team beat the team that follows it after. We are given k+1 teams, we want to show that we can remove one of the teams. It doesn"t matter what team we remove, but now we have a smaller set of teams which gives us a smaller tournament with only k teams. By inductive hypothesis, we can label the teams (since now we have k teams which is assumed to be true if we have k teams) The remaining task is now that we need to fit the team that we removed somewhere.
