Известно что n натуральное число каким числом четным или нечетным является

Простая математическая задача, которую мы все еще не в состоянии решить

А мы традиционно делимся с вами переводом интересного материала.

Несмотря на недавние сподвижки с небезызвестной гипотезой Коллатца, мы до сих пор не можем понять, может ли число выйти из бесконечного цикла.

Эта статья идет вместе с предупреждением: не пытайтесь решить эту математическую задачу.

Вы будете испытывать соблазн попробовать сделать это. Эта проблема достаточно просто сформулирована, понятна и слишком заманчива. Просто выберите число, любое число: если число четное, разделите его пополам; если оно нечетные, умножьте его на 3 и прибавьте 1. Возьмите получившееся новое число и повторяйте этот процесс снова и снова. Если вы будете продолжать выполнять эти итерации достаточное количество раз, в конечном итоге вы застрянете в бесконечном цикле. По крайней мере, мы так думаем.

Или давайте попробуем 11: это нечетное число, поэтому мы утроим его и прибавим 1. Теперь мы получили 34, что является четным числом, поэтому мы делим его пополам и получаем 17, утраиваем и прибавляем 1, чтобы получить 52, уменьшаем вдвое, чтобы получить 26, и снова, чтобы получить 13, устраиваем его и добавляем 1, чтобы получить 40, уменьшите его вдвое, чтобы получить 20, затем 10, затем 5, утраиваем и добавляем 1, чтобы получить 16, делим пополам, чтобы получить 8, затем 4, 2 и 1. И мы снова застряли в бесконечном цикле.

Печально известная гипотеза Коллатца гласит, что если вы начнете с любого положительного целого числа, вы всегда окажетесь в этом бесконечном цикле. И вы, вероятно, проигнорируете мое предупреждение о попытке решить эту проблему: она кажется слишком простой и слишком складной, чтобы сопротивляться пониманию. На самом деле, было бы трудно найти математика, который бы не пытался найти подход к этой проблеме.

И я не смог проигнорировать ее, когда впервые узнал о ней в школе. Мы с друзьями целыми днями обменивались захватывающими идеями, которые в итоге никак не приближали нас к ответу. Но гипотеза Коллатца печально известна не просто так: даже если каждое число, которое когда-либо было опробовано, в конечном итоге попадает в этот цикл, мы все еще не можем быть уверены, что это утверждение справедливо всегда. Несмотря на все внимание, это до сих пор всего лишь предположение.

Тем не менее некоторый прогресс все же был достигнут. Один из величайших математиков в мире проигнорировал все предупреждения и взялся за дело, в итоге достигнув крупнейшего за последние десятилетия успеха в решении этой проблемы. Давайте посмотрим, что делает эту простую проблему такой сложной.

Чтобы понять гипотезу Коллатца, мы начнем со следующей функции:

Удобно представлять орбиту в виде последовательности со стрелками. Вот орбита 10 для f:

10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 → …

В конце мы видим, что застряли в бесконечном цикле 1 → 4 → 2 → 1 →….

Аналогично, орбита 11 для f может быть представлена ​​как

11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → ….

Мы снова попадаем в тот же цикл. Попробуйте еще несколько примеров, и вы увидите, что орбита всегда стабилизируется в этом цикле 4 → 2 → 1 →…. Начальные значения 9 и 19 забавны, а если у вас есть несколько свободных минут, попробуйте 27. Если ваша арифметика будет верна, вы окажетесь в цикле после 111 шагов.

Гипотеза Коллатца утверждает, что орбита каждого числа для f в конечном итоге достигает 1. И хотя никто не доказал эту гипотезу, она была проверена для каждого числа меньше 26⁸. Так что, если вы ищете контрпример, вы можете начать с 300 квинтиллионов. (Вы были предупреждены!)

Легко проверить, что гипотеза Коллатца верна для любого конкретного числа: просто вычисляйте орбиту, пока не дойдете до 1. Но чтобы понять, почему так трудно доказать ее для каждого числа, давайте исследуем немного более простую функцию ℊ.

Функция ℊ похожа на f, но для нечетных чисел она просто добавляет 1 вместо того, чтобы сначала утроить их. Так ℊ и f разные функции, числа имеют разные орбиты. Например, вот орбиты 10 и 11 для ℊ:

10 → 5 → 6 → 3 → 4 → 2 → 1 → 2 → 1 → 2 → …

11 → 12 → 6 → 3 → 4 → 2 → 1 → 2 → 1→ 2 → …

Обратите внимание, что орбита числа 11 достигает 1 быстрее для ℊ, чем для f. Орбита 27 также достигает 1 намного быстрее для ℊ.

27 → 28 → 14 → 7 → 8 → 4 → 2 → 1 → 2 → …

В этих примерах орбиты ℊ тоже выглядят стабилизирующимися, так же как орбиты f, но в немного более простой цикл:

Во-первых, мы знаем, что половина положительного целого числа всегда меньше самого целого числа. Итак, если n четное и положительное, то ℊ(n) = n/ 2 . Другими словами, когда орбита достигает четного числа, следующее число всегда будет меньше.

Обратите внимание, что

вероятно, тоже меньше n. И в самом деле, несложно доказать, что покуда n> 1, то всегда выполняется

Может ли аналогичное доказательство сработать с гипотезой Коллатца? Вернемся к исходной функции.

Как и в случае с ℊ, подстановка в f четного числа уменьшает его. Как и в случае с ℊ, подстановка в f нечетного числа возвращает нам четное число, что означает, что мы знаем, что произойдет дальше: f сократит новое число вдвое. Вот как выглядит орбита f, когда n нечетное:

Но здесь наше доказательство начинает разваливаться. В отличие от примера выше, это число больше n:

, что всегда больше n. Ключом к доказательству гипотезы Ноллатца было то, что нечетное число через два шага должно стать меньше, но это неверно в случае Коллатца. Наше доказательство не работает.

Если у вас есть что-то общее со мной и моими школьными друзьями, вы, возможно, захотите попробовать доказать, что гипотеза Коллатца ложна: в конце концов, если орбита продолжает увеличиваться, то как она может опуститься до 1? Но это доказательство требует понимания того, что происходит дальше, а что происходит дальше, проливает свет на то, почему гипотеза Коллатца настолько скользкая: мы не можем быть уверены, четное ли

Мы знаем, что 3n + 1 четное. Если 3n + 1 также делится на 4, то

тоже четное, и орбита будет уменьшаться. Но если 3n + 1 не делится на 4, то

нечетное, и орбита увеличивается. Как правило, мы не можем предсказать, что из этого окажется правдой, поэтому наше доказательство несостоятельно.

Но этот подход не совсем бесполезен. Поскольку половина всех положительных целых чисел четные, с вероятностью в 50%

четное, что делает следующий шаг по орбите равным

. Для n > 1 это уже меньше, чем n, поэтому в половине случаев нечетное число должно уменьшаться после двух шагов. Также существует 50%-ная вероятность, что

это четное число, что означает, что существует 25%-ная вероятность того, что нечетное число станет меньше более чем в два раза после трех шагов. И так далее. Конечный результат состоит в том, что в некотором среднестатистическом случае орбиты Коллатца уменьшаются, когда они сталкиваются с нечетным числом. А поскольку орбиты Коллатца всегда уменьшаются для четных чисел, это наталкивает на вывод, что все последовательности Коллатца в долгосрочной перспективе должны уменьшаться. Это доказательство на основе вероятностей широко известно, но еще никому не удалось довести его до полного доказательства гипотезы.

А в 2019 году Теренс Тао, один из величайших математиков мира, улучшил этот результат. Если Террас доказал, что почти для всех чисел последовательность Коллатца для n в итоге приходит к числу меньшему, чем n, Тао доказал, что почти для всех чисел последовательность Коллатца для n заканчивается намного ниже: ниже

Даже в этом случае гипотеза будет продолжать привлекать математиков и энтузиастов. Так что выберите число, любое число и вперед. Просто помните, вас предупреждали: не зацикливайтесь бесконечно.

Упражнения

1. Покажите, что существует бесконечно много чисел, чьи орбиты Коллатца проходят через 1.

3. В недавнем разговоре о гипотезе Коллатца Терренс Тао упомянул следующую функцию Коллатца:

Тао указывает, что в дополнение к петле 1 → 2 → 1 → 2 → 1… появляются еще две петли. Вы можете их найти?

Ответы

Нажмите, чтобы раскрыть ответ 1:

Обратите внимание, что каждая степень двойки имеет простой орбитальный путь к 1. Например,

Поскольку существует бесконечно много степеней двойки, существует бесконечно много чисел, чьи орбиты Коллатца проходят через 1.

Обратите внимание что 2^5 имеет время остановки 5, так как

…. А поскольку 2^4 имеет время остановки 4, любое число, которое на один шаг отстает от 2^4, имеет время остановки 5. Например, 5 → 16 → 8 → 4 → 2 → 1. Могут ли быть и другие?

5 → 14 → 7 → 20 → 10 → 5 → …

17 → 50 → 25 → 74 → 37 → 110 → 55 → 164 → 82 → 41 → 122 → 61 → 182 → 91 → 272 → 136 → 68 → 34 → 17 → …

Источник

Методическая разработка «Готовимся к олимпиаде по математике. ЧЁТНОСТЬ»

Онлайн-конференция

«Современная профориентация педагогов
и родителей, перспективы рынка труда
и особенности личности подростка»

Свидетельство и скидка на обучение каждому участнику

ГОТОВИМСЯ К ОЛИМПИАДЕ ПО МАТЕМАТИКЕ

I. Чётность суммы и произведения двух чисел

Значит, числа 10, ( − 6) и 0 являются чётными, а число 15 – нечётным.

Как формально можно записать, что заданное число является чётным (или нечётным)? Иными словами, как можно записать тот факт, что число является чётным (или нечётным), с помощью математических символов?

1) Если число n – чётное, то его можно записать в виде

2) Если число n – нечётное, то его можно записать в виде

Можно заметить, что чётные и нечётные числа на координатной прямой чередуются. Поэтому, сдвинувшись на один шаг от чётного числа, мы попадём в нечётное.

Как понятия чётного и нечётного числа взаимодействуют с арифметическими операциями (а именно, с операциями сложения, вычитания и умножения)?

Нетрудно убедиться, что при сложении чётного числа с нечётным мы получаем нечётную сумму. Например, 8 + 9 = 17.

Докажем это утверждение для произвольных целых чисел.

Пусть n ₁ – чётное число, а n ₂ – нечётное.

Тогда эти числа можно записать так:

Сложив эти два числа, мы получим следующую запись:

Чётное число + нечётное число = 2 ∙ k ₁ + ( 2 ∙ k ₂ + 1) = 2 ∙ k ₁ + 2 ∙ k ₂ + 1 =

= 2 ∙ ( k ₁ + k ₂ ) + 1 = чётное число + 1 = нечётное число

Аналогично можно доказать, что при сложении двух чётных чисел получается чётная сумма:

Чётное число + чётное число = 2 ∙ k ₁ + 2 ∙ k ₂ = 2 ∙ k ₁ + 2 ∙ k ₂ =

= 2 ∙ ( k ₁ + k ₂ ) = чётное число.

Также легко убедиться, что при сложении двух нечётных чисел также получается чётное число:

Нечётное число + нечётное число = ( 2 ∙ k ₁ +1) + ( 2 ∙ k ₂ + 1) = 2 ∙ k ₁ + 2 ∙ k ₂ + 1 + 1 =

= 2 ∙ ( k ₁ + k ₂ ) + 2 = чётное число + чётное число = чётное число.

При вычитании двух нечётных чисел чётность разности определяется так же, как и при их сложении.

Полученные результаты можно оформить в виде таблицы сложения чётных и нечётных чисел:

Заполним такую же таблицу для операции умножения:

1) чётное число ∙ чётное число = ( 2 ∙ k ₁ ) ∙ ( 2 ∙ k ₂ ) = 2 ∙ (2 k ₁ ∙ k ₂ ) = чётное число;

2) чётн. число ∙ нечётн. число = ( 2 ∙ k ₁ ) ∙ ( 2 ∙ k ₂ + 1) = 2 ∙ ( k ₁ ∙ (2 k ₂ + 1)) = чётное число;

3) нечётн. число ∙ нечётн. число = ( 2 ∙ k ₁ + 1) ∙ ( 2 ∙ k ₂ + 1) = 2 k ₁ ∙ 2 k ₂ + 2 k ₁ + 2 k ₂ + 1 ) =

= чётное число + чётное число + чётное число + нечётное число = нечётное число.

II. Чётность суммы и произведения нескольких чисел

Произведение нескольких целых чисел нечётно, если и только если все сомножители нечётны.

Сумма нескольких чисел нечётна, если и только если в неё входит нечётное число нечётных слагаемых.

III. Решение задач. Задачи для самостоятельного решения

1. Будем обозначать через Ч произвольное чётное число, а через Н — произвольное нечётное число. Выберите все выражения, значения которых являются чётными.

2. Не вычисляя значений выражений, выберите все, значения которых являются чётными.

2) (5 + 6) ⋅ (7 + 8) + (9 + 11) ⋅ (10 + 12),

3) (3 + 4) ⋅ (5 + 6) ⋅ (7 + 8) ⋅ (9 + 10),

4) (1 + 2) ⋅ (3 + 5) − (8 + 9) ⋅ (10 + 12).

3. Значения каких выражений будут чётны при любом целом n?

4. Значения каких выражений будут чётны при любых целых m и n?

5. Выберите все верные утверждения.

1) Сумма 11 нечётных чисел всегда чётна.

2) Сумма 11 нечётных чисел может быть чётна, а может быть нечётна.

3) Сумма 11 нечётных чисел всегда нечётна.

4) Сумма 10 нечётных чисел всегда чётна.

5) Сумма 10 нечётных чисел может быть чётна, а может быть нечётна.

6) Сумма 10 нечётных чисел всегда нечётна.

6. Не вычисляя значений выражений, выберите все, значения которых являются чётными.

7. Известно, что произведение abc нечетно. Какие из следующих чисел заведомо являются четными?

6) (а + 1) ∙ (b + 1) ∙ (c + 1).

8. Целые числа n1, n2, …, n10 таковы, что n1 ⋅ n2 ⋅ … ⋅ n10=1. Выберите все значения из списка, которые может принимать сумма n1+n2+…+n10.

9. Известно, что сумма 20 целых чисел n1, n2, …, n20 нечётна. Какие из следующих чисел заведомо чётные?

IV. Решение более сложных задач.

Каждая из этих сумм, по условию, чётна. Сложим все четыре записанные суммы:

Поскольку мы сложили изначально чётные суммы, то и данная сумма будет чётна. Но произведение нечётного числа 3 на сумму ( a + b + c + d ) будет чётна в том и только в том случае, когда выражение в скобках представляет собой чётное число.

Задача 2. Существуют ли решения у ребуса АБ ⋅ Б = ЕВГ, если гласные буквы обозначают чётные цифры, а согласные — нечётные (одинаковые буквы обозначают одинаковые числа, а разные буквы — разные)?

По условию задачи, буквы А и Е соответствуют чётным цифрам, а буквы Б, В и Г – нечётным цифрам.

Заметим, что цифра В получается при умножении цифр А и Б. Но А число чётное, значит, это произведение – чётно.

Чтобы цифра В стала нечётной, необходимо, чтобы при умножении Б на Б получилось число, большее 10. Это достигается только при Б = <5, 7, 9>. Но если Б = 5, то Б ∙ Б = 25, и тогда цифра Г также равна 5, что невозможно.

Если Б = 7, то Б ∙ Б = 49, и цифра 4 прибавляется к результату умножения цифр А и Б, равному чётному числу, и В опять будет чётной цифрой.

Аналогично, при Б = 9 получаем, что Б ∙ Б = 81, и цифра 8 прибавляется к результату умножения цифр А и Б, равному чётному числу, и В опять будет чётной цифрой.

Получается, что при любом нечётном значении цифры Б цифра В будет чётной, что противоречит условию задачи.

Следовательно, задача не имеет решения.

Задача 3. Можно ли 25 рублей разменять 10 монетами номиналом 1, 3 и 5 рублей?

Заметим, что каждая монета номиналом 1, 3 и 5 рублей представляет собой нечётное число рублей. Если сложить 10 нечётных чисел по 1, 3 и 5, то независимо от того, какие именно числа мы сложили, их сумма будет чётной (поскольку 10 нечётных чисел можно разбить на пять пар нечётных чисел, и в каждой из этих пар сумма будет чётной). А число 25 – число нечётное.

Следовательно, 25 рублей невозможно разменять 10 монетами номиналом 1, 3 и 5 рублей.

Задача 4. На доске написано следующее равенство:

Можно ли заменить каждую ∗ на один из знаков «+» или «−» так, чтобы получилось верное равенство?

Нам нужно сложить десять целых чисел, среди которых имеется ровно пять чётных и ровно пять – нечётных.

Заметим, что после сложения данных десяти чисел мы должны получить число 0, которое является чётным.

Но сумма пяти чётных чисел равна чётному числу, а сумма пяти нечётных чисел – нечётному числу. Таким образом, сумма всех десяти данных чисел должна равняться нечётному числу, и следовательно, равняться нулю она не может.

Задача 5. Можно ли представить число 1 в виде суммы десяти дробей вида , где n — нечётное натуральное число?

Предположим, что 1 можно представить в виде суммы десяти таких дробей.

Тогда сумма данных дробей равна:

+ + + + + + + + + =

= .

Заметим, что каждое слагаемое в числителе – это произведение 9-ти нечётных множителей (а если в произведении нет ни одного чётного числа, то оно равно нечётному числу), и таких слагаемых там содержится ровно 10. Таким образом, сумма десяти нечётных чисел в числителе – это число чётное.

А вот знаменатель представляет собой произведение, составленное десятью множителями, среди которых также нет ни одного чётного числа, и поэтому этот знаменатель равен нечётному числу.

Мы получили дробь, в которой числитель – число чётное, а знаменатель – число нечётное, то есть числитель не равен знаменателю. Но дробь может быть равна 1 тогда и только тогда, когда числитель равен знаменателю.

= ≠ 1.

Значит, 1 нельзя представить в виде суммы дробей вида с нечётными знаменателями.

Задача 6. Незнайка выписал по кругу 11 натуральных чисел. Для каждых двух соседних чисел он посчитал их разность (из большего вычел меньшее). В результате среди найденных разностей оказалось четыре единицы, четыре двойки и три тройки. Докажите, что Незнайка где-то допустил ошибку.

Источник