Размещение с повторениями?

Question

[avion]

Какое максимальное количество двоичных слов длины 10 (последовательностей из десяти нулей и единиц) можно выбрать, чтобы любые два выбранных слова отличались бы по крайней мере в двух местах?

Всего комбинаций 2^10, но каким образом выбрать слова, отличающиеся по крайней мере в двух местах?

Answer 1

[Alexandroppolus]

половина из всех, то есть 2^9 = 512

выбираем нуль, все числа с 2 единицами, все с 4 единицами и т.д., вплоть до 1111111111. Легко посчитать, что их количество равно 2^9
1 + C(10, 2) + C(10, 4) + C(10, 6) + C(10, 8) + 1 = 512

Почему нельзя больше? При каждом выборе одного слова вычеркиваем 10 соседних (отличающихся от выбранного одним битом). По такому алгоритму каждое слово можно вычеркнуть не более 10 раз. Если выберем более 512, то будет более 5120 отдельных вычерков, а вычеркнутых слов менее 512 (всего 1024), то есть кого-то вычеркнули более 10 раз, противоречие.