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