Задачка про рабов и бочки - Public forum of MSU united student networks

Печаль. Прочитал задачку перед уходом на четырехчасовой аспирантский английский, пока дошел до него, успел решить для произвольного изначального количества рабов и дней, пока вернулся - уже практически все расписали.

Ну, на всякий случай распишу простой метод для произвольного числа дней и рабов (скорее всего Zruty его и имеет в виду).
Пусть у нас k рабов, n дней, (n+1)^k бочек. Нумеруем их в (n+1)-ричной системе счисления, получаются числа из k цифр. В i-й день j-й раб бьет из тех бочек, в которых на j-й позиции стоит цифра i (т.е. каждый раб соответствует собственному разряду, а значение разряда --- дню, в который раб попробует эту бочку).
Если в какой-то день раб должен что-то пить, но уже умер, то мы на него забиваем (это нестрашно, т.к. множества бочек, из которых раб пьет в разные дни, попарно не пересекаются, т.е. если он отравился в один день, то ни в какой другой уже не может отравиться).
Дальше отравленная бочка элементарно восстанавливается --- в ее номере на j-й позиции стоит день смерти j-го раба (или 0, если рабу повезло и он выжил).
Очевидно, что большее число бочек различить нельзя (в смысле если их будет больше, то мы не сможем заведомо найти отравленную) --- для каждого раба у нас есть ровно n+1 вариант (умер в первый день, умер во второй день, ..., умер в н-ный день, выжил), итого (n+1)^k расклад всего.

P.S. Разумеется, можно для n дней доказать и по индукции, использовав схему Light_Kitten для перехода и воспользовавшись равенством $[math]$(n+1)^k = 1 + C_n^1 n + C_n^2 n^2 + \ldots + n^k$ [/math]$ (собственно, у него оно магическим образом и появилось для n = 2, k = 5)