задачка про экзамен
Dec. 26th, 2019 12:33 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaКрасивая задачка из последнего "Кванта". Не очень тяжелая.
На экзамен пришли 100 студентов. Преподаватель по очереди задает каждому студенту один вопрос: «Сколько из 100 студентов получат оценку “сдал” к концу экзамена?» В ответ студент называет целое число. Сразу после получения ответа преподаватель объявляет всем, какую оценку получил студент: “сдал” или “не сдал”.
После того, как все студенты получат оценку, придет инспектор и проверит, есть ли студенты, которые дали правильный ответ, но получили оценку “не сдал”. Если хотя бы один такой студент найдется, то преподаватель будет отстранен от работы, а оценки всех студентов заменят на “сдал”. В противном случае никаких изменений не произойдет. Могут ли студенты придумать стратегию, которая гарантирует им всем оценку “сдал”?
Комменты скрыты, открою вечером.
Update: открыл комментарии. Много правильных. Вот правильное решение, один из нескольких возможных способов описать одно и то же:
Каждый студент называет число, исходя из предположения, что он последний несдавший (т.е. он говорит число оценок "сдал" до него плюс число всех студентов после него). Тогда если этому студенту поставят оценку "не сдал", то либо его ответ был правильный, либо еще после него преподаватель обязан поставить кому-то еще один "не сдал". Если мы теперь посмотрим на последнего студента, получившего оценку "не сдал", выходит, что на нем преподаватель ошибся, и все оценки заменили на "сдал" - либо такого вообще не было, и он изначально всем дал оценки "сдал". В любом случае студенты победили.
На экзамен пришли 100 студентов. Преподаватель по очереди задает каждому студенту один вопрос: «Сколько из 100 студентов получат оценку “сдал” к концу экзамена?» В ответ студент называет целое число. Сразу после получения ответа преподаватель объявляет всем, какую оценку получил студент: “сдал” или “не сдал”.
После того, как все студенты получат оценку, придет инспектор и проверит, есть ли студенты, которые дали правильный ответ, но получили оценку “не сдал”. Если хотя бы один такой студент найдется, то преподаватель будет отстранен от работы, а оценки всех студентов заменят на “сдал”. В противном случае никаких изменений не произойдет. Могут ли студенты придумать стратегию, которая гарантирует им всем оценку “сдал”?
Комменты скрыты, открою вечером.
Update: открыл комментарии. Много правильных. Вот правильное решение, один из нескольких возможных способов описать одно и то же:
Каждый студент называет число, исходя из предположения, что он последний несдавший (т.е. он говорит число оценок "сдал" до него плюс число всех студентов после него). Тогда если этому студенту поставят оценку "не сдал", то либо его ответ был правильный, либо еще после него преподаватель обязан поставить кому-то еще один "не сдал". Если мы теперь посмотрим на последнего студента, получившего оценку "не сдал", выходит, что на нем преподаватель ошибся, и все оценки заменили на "сдал" - либо такого вообще не было, и он изначально всем дал оценки "сдал". В любом случае студенты победили.
