Коминаторика Дискрет. математика. Натуральные числа а1,а2,...аn+1 (1,2,n+1 в индексе) не превосходят 2n. Доказать, что одно из этих чисел делится на другое.
Коминаторика Дискрет. математика. Натуральные числа а1,а2,...аn+1 (1,2,n+1 в индексе) не превосходят 2n. Доказать, что одно из этих чисел делится на другое.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для начала заметим, что у нас есть n пар чисел (a1, a2), (a2, a3), ..., (an, an+1) и все числа из каждой пары не превосходят 2n.
Рассмотрим каждую пару (ai, ai+1). По условию, оба числа не превосходят 2n. Таким образом, возможные значения для ai и ai+1 - это натуральные числа от 1 до 2n.
Поскольку у нас всего 2n возможных значений для ai и ai+1, а у нас n+1 чисель в последовательности, по принципу Дирихле должны существовать два различных числа ai и aj (где i < j) соответствующих одним и тем же числам ai и ai+1, то есть ai = aj и ai+1 = aj+1.
Это означает, что одно из чисел ai и ai+1 делится на другое.
Таким образом, мы доказали, что одно из чисел из последовательности делится на другое.