Among all friendships, being classmates has a special part. Inside every classroom, each student has a friend who would cause trouble if they sit adjacent (side to side, front-back and diagonal) to each other. This is why teachers change the sitting-order to find the optimal situation for each classroom.
Steve the teacher and his problem
Teacher Steve realizes in one of his classes that in total 8 students cause trouble during lessons whenever they sit adjacent (from now on I will refer to being adjacent as “being neighbor”).
- Neighbor students are the students who sit either side to side, front and back or diagonal to each other.
- If two students cause trouble whenever they are neighbors, there is a <–> sign between their names.
- Deniz <–> Ali <–> Kirk <–> Jane <–> Poseidon <–> Rebecca <–> Lucreita <–> Bran
- Sitting plan for these 8 students is shown in the following:
Steve the teacher doesn’t want to change other students’ sitting plan. Hence his problem becomes as follows:
“How can I find an order for these 8 students so that there won’t be neighbor students who will become naughty?”
Hint: Assign numbers to the students.
I will explain the answer in the next post.
M. Serkan Kalaycıoğlu