6.7: Індукція в геометрії, комбінаториці та теорії чисел

Last updated
Save as PDF

Page ID: 65942

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Переходимо поруч із змішаною колекцією проблем, покликаних виділити цілий спектр застосувань.

Проблема 256 Нехай $f_{1} = 2$ , $f_{к + 1} = f_{к} (f_{к} + 1)$ . Доведіть індукцією, що $f_{к}$ має щонайменше k різних простих множників.

Проблема 257

(а) Доведіть шляхом індукції, що n точок на прямій лінії ділять лінію на $п + 1$ частини.

(b) (i) Експериментуючи з малими значеннями n, вгадайте формулу $Р_{п}$ для максимальної кількості областей, які можуть бути створені на площині масивом з n прямих ліній.

(ii) Доведіть шляхом індукції, що n прямих ліній в площині ділять площину на щонайбільше $Р_{п}$ регіони.

(c) (i) Експериментуючи з малими значеннями n, вгадайте формулу $S_{п}$ для максимальної кількості областей, які можуть бути створені у 3-х вимірах масивом з n площин.

(ii) Доведіть шляхом індукції, що n площин у 3-х вимірах ділять простір на щонайбільше $S_{п}$ регіони.

Завдання 258 Дано квадрат, довести, що, для кожного $п \geq 6$ , початковий квадрат можна розрізати на n квадратів (можливо різних розмірів).

Задача 259 Дерево - це зв'язаний граф, або мережа, що складається з вершин і ребер, але без циклів (або ланцюгів). Доведіть, що дерево з n вершин має точно $п - 1$ краю.

Наступна проблема стосується сферичних багатогранників. Сферичний багатогранник - це багатогранна поверхня в 3-х вимірах, яку можна надути, щоб сформувати сферу (де ми припускаємо, що грані та ребра можуть розтягуватися за потребою). Наприклад, куб - це сферичний багатогранник; але поверхня фоторамки - це не так. Сферичний багатогранник має

грані (плоскі 2-вимірні багатокутники, які можна розтягнути, щоб прийняти форму диска),
ребра (1-мірні відрізки лінії, де зустрічаються рівно дві грані), і
вершини (0-мірні точки, де зустрічаються кілька граней і ребер, таким чином, що вони утворюють єдиний цикл навколо вершини).

Кожна грань повинна чітко мати принаймні 3 ребра; і на кожній вершині має бути не менше трьох ребер і трьох граней.

Якщо сферичний багатогранник має V вершин, E ребер і F граней, то числа V, E, F задовольняють формулу Ейлера

$V - Е + F = 2.$

Наприклад, куб має $V = 8$ вершини, $Е = 12$ краю, і $F = 6$ облич, і $8 - 12 + 6 = 2$ .

Проблема 260

(a) (i) Опишіть сферичний багатогранник з рівно 6 ребрами.

(ii) Опишіть сферичний багатогранник з рівно 8 краями.

(б) Доведіть, що жоден сферичний багатогранник не може мати рівно 7 ребер.

Задача 261 Карта - це (скінченна) сукупність областей на площині, кожна з яких має межу або межу, тобто «багатокутну» в тому сенсі, що вона складається з єдиної послідовності різних вершин і, можливо, вигнутих - ребер, що розділяє площину на дві частини, одна з яких є багатокутною сам регіон. Карта може бути належним чином забарвлена, якщо кожній області можна призначити колір, щоб кожна пара сусідніх областей (з загальним краєм) завжди отримувала різні кольори. Доведіть, що області такої карти можуть бути правильно пофарбовані лише двома кольорами, якщо і тільки тоді, коли парна кількість ребер зустрічається у кожній вершині.

Проблема 262 (Сірі коди) Є $2^{п}$ послідовності довжини n, що складаються з 0 і 1s. Доведіть, що для кожного $п \geq 2$ , ці послідовності можуть бути розташовані у циклічному списку таким чином, що будь-які дві сусідні послідовності (включаючи останню та першу) відрізнялися рівно однією координатною позицією.

Задача 263 (дерево Калкіна-Вільфа) Бінарне дерево в площині має відмінну вершину як `корінь 'і побудовано індуктивно. Корінь з'єднується з двома новими вершинами; і кожна нова вершина потім з'єднується з двома новими вершинами - при цьому процес побудови триває назавжди (рис. 11). Позначте вершини двійкового дерева додатними дробами наступним чином:

кореню дається мітка $\frac{1}{1}$
всякий раз, коли ми знаємо етикетку $\frac{я}{j}$ «батьківської» вершини, ми позначаємо її `лівий нащадк' як $\frac{я}{я + j}$ , і його `правий нащадка' $\frac{я + j}{j}$ .

(а) Доведіть, що кожен позитивний раціональний $\frac{р}{s}$ відбувається один раз і лише один раз як мітка, і що це відбувається в найнижчі терміни.

(b) Доведіть, що мітки є симетричними вліво-праворуч у тому сенсі, що мітки у відповідних лівих і правих положеннях є взаємними один одному.

Задача 264 Колекція n інтервалів на осі x така, що кожна пара інтервалів має спільну точку. Доведіть, що всі п інтервали повинні потім мати принаймні одну спільну точку.