Timeline for Induction: Prove that it is possible to seat people in a circle so that everyone sits beside a friend
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 14, 2020 at 12:09 | comment | added | tpb261 | if you remove one person, then "n" becomes 2k.. half of that would be k. Still valid, right? 2k people need only k friends. (to avoid any confusion, I am using complete induction) | |
| Apr 8, 2020 at 2:22 | comment | added | hoymkot | if n = 2k + 1, then all people only have k+1 friends, some of them are friends of Person (n+1). Taking Person (n+1) out of the group, then the number of friends that friends of Person(n +1) have is k, which is less than (2k +1) /2, n/2. The rest of the people cannot sit in a circle, per assumption of the statement. Your clause regarding n=2k+1 doesn't cover this case. | |
| May 25, 2014 at 13:15 | history | answered | tpb261 | CC BY-SA 3.0 |