10
$\begingroup$

Professor Kafka tells proudly:

  • Today I gave a fascinating lecture.
  • There were five students sitting in the first row of the lecture room, and each of them was awake as I started my lecture.
  • Each of the five fell asleep exactly twice during my lecture.
  • Furthermore, every pair of these five students was simultaneously asleep at some point in time.
  • At any moment in time, at least three of these five students were awake and listening closely to my lecture.

Is it possible that professor Kafka remembers the situation correctly?

$\endgroup$
  • 4
    $\begingroup$ No, Kafka does not remember the situation correctly. Students would not have fallen asleep if his lecture were actually fascinating. $\endgroup$ – Kevin - Reinstate Monica Jan 21 '15 at 19:52
11
$\begingroup$

Professor Kafka is

probably wrong

Because

We have 10 pairs of students. Each of these pairs must be sleeping separately, or we would fail the 'at least 3 awake at once' condition. We require a student to fall asleep to change the sleeping pair, and 5x2 students allows us 10 state changes. Unfortunately, to get from our presumed (hence the 'probably' above) initial state of 'all students awake' to the first pair we require 2 students to fall asleep, meaning we can only fulfill 9 pairs in total. If a student may start the lecture asleep the solution is trivial.

$\endgroup$
  • 2
    $\begingroup$ NVM - you are right, it is trivial - AB, BC, CD, DE, EA, AC, CE, EB, BD, DA. All fall asleep twice, but A is asleep three times, starting the lecture asleep. $\endgroup$ – Trenin Jan 20 '15 at 15:21
2
$\begingroup$

Professor Kafka is probably wrong because "every pair of these five students was simultaneously asleep at some point in time" is impossible if "at any moment in time there were at least three of these students awake and listening to my lecture."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.