В школе 1000 учеников,которым присвоены номера от 000 до 999, и 100 учителей с номерами...

Question

В школе 1000 учеников,которым присвоены номера от 000 до 999, и 100 учителей с номерами от 00 до 99. Учителя следят за учениками, чтобы те не списывали. При этом они договорились следовать такому правилу: за учеником следят те учителя, номера которых можно получить из номера ученика вычеркиванием ровно одной цифры. Учителя математики утверждают, что можно ровно половину учителей освободить от этой обязанности так, что все равно за каждым учеником будет следить хотя бы один учитель. Не ошибаются ли они?

Answer 1

Они правы.
Только за учениками с номерами 000, 111, 222, ..., 999 следит по одному учителю с номерами соответственно 00, 11, 22, ..., 99.
За всеми остальными следят как минимум двое за каждым.
Например, за учеником номер 001 следят и учитель 00, и 01. А за учеником номер 123 следят трое: 12, 13 и 23.
Так что действительно, половину учителей можно уволить, но номера за оставшимися нужно сохранить.