ГЛАВНАЯ » РЕШЕБНИК

2015-02-14   
Из #2n# чисел #1,2m \cdots, 2n# произвольно выбрали #n - 1# число. Доказать, что среди выбранных чисел найдутся хотя бы два числа, из которых одно делится на другое.



Решение:


1. Для двух чисел 1, 2 утверждение справедливо.
2. Допустим, что из #2n# чисел #1,2m \cdots, 2n# где #n \geq 2,# удалось выбрать так #n-1# число, что ни одно из них не делится на другое.
Совокупность всех этих чисел обозначим для краткости #M_{n-1},# Докажем, что тогда из #2n-2# чисел #1,2m \cdots, 2n-2# можно выбрать #n# чисел таких, что опять
ни одно из них не будет делиться на другое. Возможны четыре случая:
1) #M_{n-1}# не содержит ни #2n-1,# ни #2n.#
2) #M_{n-1}# содержит #2n-1# и не содержит #2n.#
3) #M_{n-1}# содержит #2n# и не содержит #2n-1.#
4) #M_{n-1}# содержит и #2n-1,# и #2n.#
Случай 1. Исключим из #M_{n-1}# какое-нибудь число. Останется #n# чисел, каждое из которых не больше, чем #2n-2.# Ни одно из этих чисел не делится на другое.
Случай 2. Исключим из #M_{n-1}# число #2n-1.# Останется #n# чисел, каждое из которых не больше, чем #2n-2.# Ни одно из этих #n# чисел не делится на другое.
Случай 3. Исключим из #M_{n-1}# число #2n# и опять получим тот же результат.
Случай 4. Прежде всего заметим, что в #M_{n-1}# не содержится число #n,# так как иначе в #M_{n-1}# нашлось бы два числа (#2n# и #n#), из которых одно делится
на другое. Исключим из #M_{n-1}# числа #2n-1# и #2n.# Совокупность оставшихся #n-1# чисел обозначим #M_{n-1}.#
Присоединим к число #M_{n-1}#. Получим #n.# чисел, каждое из которых не превосходит #n#.
Остается показать, что среди этих #2n-2# чисел ни одно не делится на другое. В #n# не было двух чисел, из которых одно делится на другое.
Значит, таких чисел не было и в #M_{n-1}# Остается только убедиться в том, что таких чисел не появилось и тогда, когда мы к #M_{n-1}.#
присоединили число #M_{n-1}# Для этого достаточно убедиться в том, что; 1) ни одно число, входящее в #n.# не делится на #M_{n-1},# и
2) число #n# не делится ни на одно из чисел, входящих в #n# Первое вытекает из того, что все числа, входящие в #M_{n-1}# #M_{n-1},# не превосходит #2n-2.#
Второе вытекает из того, что число #2n# не делится ни на одно из чисел, входящих в #M_{n-1}.# Итак, если допустить, что утверждение неверно для #2n# чисел
#1,2, \cdots, 2n,# то оно неверно и для #2(n-1)# чисел #1,2, \cdots, 2n-2.# Значит, если утверждение верно для #2(n-1)# чисел #1,2, \cdots, 2n-2,#
то оно верно и для #2n# чисел #1,2, \cdots, 2n.# Отсюда и из пункта 1 следует, что наше утверждение справедливо для #2n# чисел #1,2, \cdots, 2n,#
где #n# — любое натуральное число. Заметим, что эта задача имеет следующее простое решение. Выберем из #2n# чисел #1,2, \cdots, 2n# произвольное #n-1# число.
Совокупность этих чисел обозначим #M_{n-1}.# Каждое четное число, входящее в #M_{n-1},# разделим на такую степень двойки, чтобы частное было нечетным.
Совокупность этих частных и всех нечетных чисел, входящих в #M_{n-1},# обозначим через #M^{\prime}_{n-1}.# В #M^{\prime}_{n-1}# Содержится #n-1# нечетное число,
каждое из которых меньше #2n.# Так как всех положительных нечетных чисел, меньших #2n,# имеется всего #n,# то в #M^{\prime}_{n-1}# найдутся хотя бы два равных числа.
Каждое из этих чисел пусть равно #k.# Полученный результат означает, что в #M_{n-1}.# было два числа #2^{s}k# и #2^{t}k# (где одно из чисел #s# и #t# может равняться
нулю). Но одно из чисел #2^{s}k# и #2^{t}k# делитcz на другое.
гипотеза верна.
2. Допуcтим, что гипотеза верна для #n = k,# т. е.#S_{k} = k^{2}.# Докажем, что тогда гипотеза должна быть верной и для #n = k+1,# т. е. #S_{k+1} = (k+1)^{2}.#
Действительно, #S_{k+1} = S_{k} + (2k+1).# Но #S_{k} = k^{2}# и потому. #S_{k+1} = k^{2} + (2k+1) = (k+1)^{2},# что и требовалось доказать