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
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| 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. | |
| Sep 29, 2017 at 5:34 | comment | added | meiji163 | @TomCollinge In the alternating case P must be friends with at least $(k+1)/2$, so this configuration is impossible | |
| May 25, 2014 at 13:25 | comment | added | Tom Collinge | Agreed. See my comment on other answer: differentiate between even and odd already present. | |
| May 25, 2014 at 13:24 | comment | added | fretty | Oh I see what you mean, yeah this isn't as simple as I thought. | |
| May 25, 2014 at 13:23 | comment | added | Tom Collinge | No, I'm seating P anywhere - in particular between A and B. | |
| May 25, 2014 at 13:22 | comment | added | fretty | Won't A still be sat next to B? This is a circular table. | |
| May 25, 2014 at 13:21 | comment | added | Tom Collinge | Yes you have. Suppose A sits next to B being friends and P is friends with B but not A: then in a sequence A, P, B poor A will be lonely . (Assuming that A is not friends with his other neighbour) | |
| May 25, 2014 at 13:19 | history | answered | fretty | CC BY-SA 3.0 |