Задача
Докажите, что из набора 0, 1, 2, ..., 3k – 1 можно выбрать 2k чисел так, чтобы никакое из них не являлось средним арифметическим двух других выбранных чисел.
Решение
Будем считать, что троичная запись каждого из данных чисел состоит ровно из k цифр (при необходимости заполним пустующие старшие разряды нулями). Выберем те числа, троичная запись которых содержит только цифры 0 и 1. Их ровно 2k. Покажем, что это и есть искомый набор. Предположим противное: среди выбранных чисел есть три различных числа x, y, z, удовлетворяющих равенству x + y = 2z. Так как числа x и y различаются хотя бы в одном разряде, то в троичной записи их суммы x + y в этом разряде стоит цифра 1. Однако в записи числа 2z встречаются только 0 и 2.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь