Олимпиадная задача по теории чисел: троики натуральных чисел и их максимальное разбиение
Задача
Дано натуральное число n. Рассматриваются такие тройки различных натуральных чисел (a, b, c), что a + b + c = n. Возьмём наибольшую возможную такую систему троек, что никакие две тройки системы не имеют общих элементов. Число троек в этой системе обозначим через K(n). Докажите, что
а) K(n) > n/6 – 1;
б) K(n) < 2n/9.
Решение
а) Пусть m = [n/6]. В разбиении {1, 2, n – 3}, {3, 4, n – 7}, ..., {2m – 1, 2m, n – 4m +1} количество троек равно [n/6] > n/6 – 1. б) Пусть имеется k троек различных натуральных чисел, в сумме дающих n. Обозначим через s сумму всех 3k чисел, входящих в эти тройки. Тогда, с одной стороны, s = nk, а с другой, s ≥ 1 + 2 + ... + 3k = 3k(3k + 1) : 2. Поэтому n ≥ 3/2 (3k + 1), откуда k ≤ 1/9 (2n – 3). Таким образом,
k(n) ≤ 1/9 (2n – 3) < 2n/9.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь