Задачи

Найдите ошибку в следующем доказательстве того, что $2=1$. Рассмотрим уравнение $a=b$. Умножим обе части на $a$, получим $a^{2}=a b$. Вычтем $b^{2}$ из обеих частей и получим $a^{2}-b^{2}=a b-b^{2}$. Теперь разложим на множители обе части, $(a+b)(a-b)=b(a-b)$, и разделим каждую часть на $(a-b)$, получим $a+b=b$. Наконец, положим $a$ и $b$ равными 1, откуда следует, что $2=1$.

Пусть $S(n)=1+2+\cdots +n$ — сумма первых $n$ натуральных чисел, а $C(n)=1^{3}+2^{3}+\cdots +n^{3}$ — сумма первых $n$ кубов. Докажите следующие равенства индукцией по $n$, чтобы прийти к любопытному выводу, что $C(n)=S^{2}(n)$ для каждого $n$.

Найдите ошибку в следующем доказательстве того, что все лошади одного цвета. Утверждение: В любом множестве из $h$ лошадей все лошади одного цвета. Доказательство: Индукцией по $h$. База: При $h=1$. В любом множестве, содержащем ровно одну лошадь, все лошади, очевидно, одного цвета. Индукционный переход: Для $k \geq 1$ предположим, что утверждение верно при $h=k$, и докажем, что оно верно при $h=k+1$. Возьмём произвольное множество $H$ из $k+1$ лошадей. Покажем, что все лошади в этом множестве одного цвета. Уберём одну лошадь из этого множества, получив множество $H_{1}$ ровно из $k$ лошадей. По индукционному предположению все лошади в $H_{1}$ одного цвета. Теперь вернём убранную лошадь обратно и уберём другую, получив множество $H_{2}$. По тому же рассуждению все лошади в $H_{2}$ одного цвета. Следовательно, все лошади в $H$ должны быть одного цвета, и доказательство завершено.

Покажите, что любой граф с двумя или более вершинами содержит две вершины одинаковой степени.

• Теорема Рамсея. Пусть $G$ — граф. Кликой в $G$ называется подграф, в котором каждые две вершины соединены ребром. Антиклика, также называемая независимым множеством, — это подграф, в котором никакие две вершины не соединены ребром. Покажите, что любой граф с $n$ вершинами содержит либо клику, либо антиклику, имеющую как минимум $\frac{1}{2} \log_{2} n$ вершин.

Используя теорему 0.25, выведите формулу для вычисления размера ежемесячного платежа по ипотеке через основную сумму долга $P$, процентную ставку $I$ и число платежей $t$. Считайте, что после $t$ платежей сумма долга уменьшается до 0. С помощью этой формулы вычислите сумму в долларах каждого ежемесячного платежа для 30-летней ипотеки с 360 ежемесячными платежами при начальной сумме долга $100,000 и годовой процентной ставке 5.