3.5: Ще більше прямих доказів - за випадками та виснаженням
- Page ID
- 64807
Доказ виснаження є найменш привабливим методом доказів з естетичної точки зору. Вичерпний доказ складається з буквально (і вичерпно) перевірки кожного елемента Всесвіту, щоб побачити, чи вірно дане твердження для нього. Зазвичай, звичайно, це неможливо, оскільки всесвіт дискурсу нескінченний; але коли всесвіт дискурсу кінцевий, звичайно, не можна аргументувати обґрунтованість вичерпного доказу.
В останні кілька десятиліть впровадження потужної обчислювальної допомоги математикам призвело до кумедної ситуації. Зростає список важливих результатів, які були «доведені» виснаженням за допомогою комп'ютера. Важливими прикладами цього явища є неіснування проективної площини порядку\(10\) [10] і єдине відоме значення числа Ремсі для гіперграфів [13].
Доказ випадками тонко відрізняється від вичерпного доказу - для одного дійсне доказ випадків може бути використаний у нескінченному Всесвіті. У доказі випадків потрібно розділити всесвіт дискурсу на кінцеву кількість множин 1, а потім надати окремий доказ для кожного з випадків. Дуже багато тверджень про цілі числа можна довести за допомогою ділення цілих чисел на парні і непарні. Інший набір випадків, який часто використовується, - це кінцева кількість можливих залишків, отриманих при діленні на ціле число\(d\). (Зверніть увагу, що парні і непарні відповідають залишкам\(0\) і\(1\) отримані після ділення на\(2\).)
Дуже відомим прикладом доказів випадками є комп'ютерне доказ чотириколірної теореми. Теорема про чотири кольори - це результат, відомий розробникам карт протягом досить тривалого часу, який говорить про те, що\(4\) кольорів завжди достатньо, щоб розфарбувати нації на карті таким чином, що країни, що поділяють кордон, завжди забарвлюються по-різному. \(3.5.1\)На малюнку показаний один екземпляр розташування націй, який вимагає принаймні чотирьох різних кольорів, теорема говорить, що чотирьох кольорів завжди достатньо. Слід зазначити, що справжні картографи зазвичай залишають п'ятий колір для океанів (та іншої води) і що можна уявити карту, що вимагає п'яти кольорів, якщо дозволяє народам бути несуміжними. В\(1977\), Кеннет Аппель і Вольфганг Хакен довели чотириколірну теорему, зменшивши нескінченність можливостей\(1,936\) відокремлювати випадки і проаналізувавши кожен з них за допомогою комп'ютера. Неелегантність доказу випадками, ймовірно, пропорційна деякій потужності кількості випадків, але в будь-якому випадку цей доказ, як правило, вважається дещо неелегантним. З тих пір, як було оголошено доказ, тривають зусилля, щоб зменшити кількість випадків (в даний час запис - це\(633\) випадки - все ще занадто багато, щоб бути перевірені без комп'ютера) або знайти докази, які не покладаються на випадки. Хорошу вступну статтю про чотириколірну теорему див. [6].
Більшість вичерпних доказів тверджень, які не є тривіальними, як правило, або є (буквально) занадто виснажливими, або здаються досить надуманими. Одним із прикладів ситуації, в якій існує вичерпний доказ якогось твердження, є те, що твердження вважається загальним істинним, але загальних доказів не відомо - але твердження перевірено для великої кількості випадків. Припущення Гольдбаха - одне з таких тверджень. Крістіан Гольдбах [4] був математиком, який народився в Кенігсберзькій Пруссії, який, що цікаво, не зробив здогадки 2. яка носить його ім'я. У листі Леонарду Ейлеру Гольдбах припустив, що кожне непарне число більше, ніж\(5\) може бути виражено як сума трьох простих чисел (в даний час це відоме як слабка гіпотеза Гольдбаха). Ейлеру, мабуть, сподобалася проблема, і він відповів Голдбаху, заявивши, що зараз відомо як здогадка Гольдбаха: кожне парне число більше, ніж\(2\) може бути виражено як сума двох простих чисел. Це твердження валяється з тих пір\(1742\), і багато хто з кращих математиків світу зробили свої спроби довести це - безрезультатно! (Ну, насправді багато прогресу було досягнуто, але результат досі не був доведений.) Це легко перевірити гіпотезу Гольдбаха для відносно невеликих парних чисел, так що те, що було зроблено є/є доказом вичерпання гіпотези Гольдбаха обмежується скінченними всесвітами. На момент написання цієї статті, здогадки було перевірено, щоб бути вірним для всіх парних чисел менше, ніж\(2 × 10^{17}\).
Всякий раз, коли для якогось твердження існує вичерпний доказ або доказ випадків, зазвичай вважається, що прямий доказ буде більш естетично приємним. Якщо ви перебуваєте в ситуації, яка не допускає такого прямого доказу, вам слід принаймні шукати докази у випадках, використовуючи мінімально можливу кількість випадків. Для прикладу розглянемо наступну теорему і доказ.
\(∀n ∈ \mathbb{Z} n^2\)має форму\(4k\) або\(4k + 1\) для деяких\(k ∈ \mathbb{Z}\).
- Доказ
-
Ми розглянемо чотири випадки, визначені чотирма можливими залишками\(\text{mod } 4\).
випадок i) Якщо\(n ≡ 0\)\((\text{mod } 4)\) тоді існує ціле число\(m\) таке, що\(n = 4m\). Звідси\(n^2 = (4m)^2 = 16m^2\) випливає, що має форму\(4k\), де\(k\) знаходиться\(4m^2\).
випадок ii) Якщо\(n ≡ 1\)\((\text{mod } 4)\) тоді існує ціле число\(m\) таке, що\(n = 4m + 1\). Звідси\(n^2 = (4m + 1)^2 = 16m^2 + 8m + 1\) випливає, що має вигляд\(4k + 1\), де k є\(4m^2 + 2m\).
випадок iii) Якщо\(n ≡ 2\)\((\text{mod } 4)\) тоді існує ціле число\(m\) таке, що\(n = 4m + 2\). Звідси\(n^2 = (4m + 2)^2 = 16m^2 + 16m + 4\) випливає, що має форму\(4k\), де\(k\) знаходиться\(4m^2 + 4m + 1\).
випадок iv) Якщо\(n ≡ 3\)\((\text{mod } 4)\) тоді існує ціле число\(m\) таке, що\(n = 4m + 3\). Звідси\(n^2 = (4m + 3)^2 = 16m^2 + 24m + 9\) випливає, що має форму\(4k + 1\), де\(k\) знаходиться\(4m^2 + 6m + 2\).
Оскільки ці чотири випадки вичерпують можливості, і оскільки бажаний результат тримається в кожному конкретному випадку, наше доказ є повним.
Q.E.D.
Хоча щойно заявлений доказ, безумовно, є дійсним, аргумент є неелегантним, оскільки достатня менша кількість випадків.
Попередня теорема може бути доведена за допомогою всього двох випадків. Зробіть так.
Ми закриємо цей розділ, попросивши вас визначити вичерпний доказ, де складність аргументу є складною, але не надто неможливою.
Граф-галька - цікава концепція, зародилася відомим комбінаториалістом Фаном Чунгом. «Графік» (як цей термін використовується тут) - це сукупність місць або місць, які відомі як «вузли», деякі з яких з'єднані шляхами або зв'язками, які відомі як «ребра». Графіки вивчаються математиками близько\(400\) років, і в цій обстановці можна поставити багато цікавих проблем. Графова галька є грубою версією більш широкої проблеми в управлінні ресурсами — часто ресурс фактично використовується в процесі його транспортування. Подумайте про великі автоцистерни, які використовуються для перевезення бензину. На чому вони бігають? Ну, насправді вони, ймовірно, спалюють дизель - але справа в тому, що для того, щоб перемістити паливо навколо, ми повинні споживати частину його. Граф-галька доводить це до крайності: для того, щоб перемістити один камінчик, ми повинні споживати один камінчик.
Уявіть, що купа камінчиків випадковим чином розподілена на вузлах графіка, і що нам дозволено робити графські галькові ходи — ми видаляємо два камінчики з якогось вузла і поміщаємо один камінчик на вузол, який з'єднаний з ним. Див\(3.5.3\). Малюнок.
Для будь-якого конкретного графіка ми можемо попросити його гальковий номер,\(ρ\). Це найменша кількість, так що якщо ρ камінчики розподілені будь-яким чином на вузлах графа, можна буде використовувати галькові ходи так, щоб отримати камінчик до будь-якого вузла.
Наприклад, розглянемо графік трикутника — три вузли, які взаємопов'язані між собою. Цифрове число цього графіка є\(3\). Якщо ми почнемо з одного камінчика на кожному вузлі, який ми вже зробили; якщо є вузол, який має дві гальки на ньому, ми можемо використовувати гальковий хід, щоб досягти будь-якого з двох інших вузлів.
Існує графік,\(C_5\) який складається з\(5\) вузлів, з'єднаних круговим способом. Визначте її гальковий номер. Доведіть свою відповідь вичерпно.
Підказка: число гальки повинно бути більшим, ніж\(4\) тому, що якщо один камінчик розміщений на кожному з\(4\) вузлів, конфігурація є нерухомою (нам потрібно мати дві гальки на вузлі, щоб мати можливість взагалі зробити гальку), і тому\(5^{\text{th}}\) вузол ніколи не може бути досягнутий.
Вправи:
Доведіть, що якщо\(n\) непарне число, то\(n^4 (\text{mod } 16) = 1\).
Доведіть, що кожне просте число, крім\(2\) і\(3\) має форму\(6q + 1\) або\(6q + 5\) для деякого цілого числа\(q\).
- Підказка
-
Ця проблема передбачає роздуми про випадки, а також про контрапозитиви.
Показати, що сума будь-яких трьох послідовних цілих чисел ділиться на\(3\).
Існує графік, відомий як\(K_4\) який має\(4\) вузли, і є ребро між кожною парою вузлів. Кількість гальки\(K_4\) має бути принаймні,\(4\) оскільки можна було б покласти по одному камінчику на кожен з\(3\) вузлів і не мати можливості дістатися до решти вузла за допомогою галькових ходів. Покажіть, що кількість гальки\(K_4\) насправді\(4\).
Знайдіть гальковий номер графіка, вузлами якого є кути, а ребра якого - ребра куба.
Число вампіра - це\(2n\) цифрове число\(v\), яке фактори, як\(v = xy\) де\(x\) і\(y\) є\(n\) цифрами, а цифри\(v\) - це саме цифри в\(x\) і\(y\) в певному порядку. Цифри\(x\) і\(y\) відомі як «ікла»\(v\). Щоб усунути банальні випадки, обидва ікла не можуть закінчитися\(0\).
Покажіть, що немає\(2\) -значних чисел вампірів.
Покажіть, що є\(4\) семизначні числа вампірів
Теорема Лагранжа про подання цілих чисел у вигляді сум квадратів говорить про те, що кожне натуральне число може бути виражено як сума не більше\(4\) квадратів. Наприклад,\(79 = 7^2 + 5^2 + 2^2 + 1^2\). Показати (вичерпно), що не\(15\) можна представити, використовуючи менше\(4\) квадратів.
Показати, що\(x\) в діапазоні є саме\(15\) числа\(1 ≤ x ≤ 100\), які не можна представити, використовуючи менше\(4\) квадратів.
Властивість трихотомії дійсних чисел просто стверджує, що кожне дійсне число або позитивне або негативне, або нуль. Трихотомія може бути використана для доведення багатьох тверджень, розглядаючи три випадки, які вона гарантує. Розробити доказ (за випадками) того, що квадрат будь-якого дійсного числа є невід'ємним.
Розглянемо гру під назвою «двійковий детермінант хрестики-нулики» 3, в яку грають два гравці, які по черзі заповнюють записи\(3 × 3\) масиву. Перший гравець йде першим, розміщуючи\(1\) в масиві, а гравець Нуль йде другим,\(0\) розміщення. мета гравця 1 полягає в тому, що остаточний масив має детермінант\(1\), і мета гравця Нуль полягає в тому, що визначник бути\(0\). Проводяться детермінантні розрахунки\(\text{mod } 2\).
Покажіть, що гравець Нуль завжди може виграти гру бінарних детермінантних хрестики-нулики методом виснаження.