Ten students stand on a circle. No two adjacent students have brown hair. What is the Maximum number of these students these students that could have brown hair.
-
Number the students 1 through 10, so that 1 is next to 10 and 2, 2 is next to 1 and 3, 3 is next to 2 and 3, etc.
Suppose that 1 has brown hair. That means that 10 and 2 DON'T. We want to maximize the number of students with brown hair, so suppose that 3 and 9 DO have brown hair. Therefore, 4 and 8 DON'T. Suppose 5 and 7 DO. Then 6 can't.
Brown hair: 1, 3, 9, 5, 7
Not Brown hair: 2, 10, 4, 8, 6
This is the maximum number. To prove that, let's think about what would happen if there were more. What if there were 6 people with brown hair? There is no way to distribute those 6 among the 10 without having two of them next to each other, which isn't allowed.
Suppose that 1 has brown hair. That means that 10 and 2 DON'T. We want to maximize the number of students with brown hair, so suppose that 3 and 9 DO have brown hair. Therefore, 4 and 8 DON'T. Suppose 5 and 7 DO. Then 6 can't.
Brown hair: 1, 3, 9, 5, 7
Not Brown hair: 2, 10, 4, 8, 6
This is the maximum number. To prove that, let's think about what would happen if there were more. What if there were 6 people with brown hair? There is no way to distribute those 6 among the 10 without having two of them next to each other, which isn't allowed.