1

A English exam was taken by $50$ students, the teacher found out that $25$ students had cheated on the exam, if the teacher was to place all of them in a round table show that there is at least one student two neighbours (at the table) of whom have cheated on the exam.

-I'm not sure if this problem should have a solution using combinatorics or graph theory. I was thinking if we use graphs to make a bipartite graph and then using the color theorem show that these students can be placed in a manner similar to the Cyclic Graph, but am still not sure if that may be the right answer since there may be a simpler solution.

N. F. Taussig
  • 76,571
Danny_007
  • 33

1 Answers1

2

Assume the conclusion does not hold.

Number your students from $1$ to $50$ consistently with the circle.

Consider the smaller circle formed by the students numbered $1$, $3$, $\ldots$, $49$. It contains $25$ students, and no two neighbors cheated, so it contains at most $12$ cheaters.

Same for the circle $2,4, \ldots,50$. In total you have at most $12+12 =24$ cheaters, a contradiction.

Aphelli
  • 34,439
  • Thank you for your insight, i am thinking that the total answer would have to be 25, since if we were to make a Cyclic Graph since we would have an even number of vertecies then the entire graph can be colored using only two colors in our case cheated and not cheated, do you think there may be any error on this if so tell me. – Danny_007 Feb 09 '19 at 09:35