АЛГЕБРАЇЧНІ ЗАДАЧІ НА ДОВЕДЕННЯ

АЛГЕБРАЇЧНІ ЗАДАЧІ НА ДОВЕДЕННЯ

1. Доказательство от обратного (противного).

Один из часто используемых методах в доказательстве. Его принцип состоит в том, что доказательство суждения (тезиса) осуществляется через опровержение противоречящего ему суждения (антитезиса). Опровержение антитезиса достигается установлением факта того, что он не совместим с каким-то уже заведомо истинным суждением.

Доказательство истинности утверждения A проводится следующим образом. Сначала принимают, что суждение A - ложно. Затем доказывают, что в таком случае, некоторое утверждение B было бы верно (хотя оно заведомо неверно). Полученное противоречие показывает, что исходное предположение было неверно (предположение, что А - ложно). А потому утверждение А - истинно по закону двойного отрицания (¬(¬А) равносильно А).

Пример:

Доказать, что - иррациональное число.

Доказательство: Докажем утверждение от обратного. Допустим число - рациональное. Тогда по определению рационального числа, его можно представить в виде несократимой дроби ^m/_n, где m ∈ Z, n ∈ N.

= ^m/_n. Поднесем в квадрат:

3 = ^m2/_n².

m² = 3n².

m² делится на 3, а значит и m делится на 3. Тогда m² делится на 9. Раз так, то и n² делится на 3, а потому и n делится на 3. Получается - что дробь ^m/_n сократима. Мы пришли к противоречию исходного суждения (что число рационально). Потому число - иррациональное.

2. Метод математической индукции.

Один из основных методов доказательства. Смысл его состоит в следующем. Допустим у нас есть последовательность утверждений A₁, A₂, ... , A_n, A_n+1, ..., где n ∈ N. Все утверждения будут истинными, если:

1) Будет доказана база индукции, т.е. истинность утверждения A₁;

2) Будет доказан переход, т.е. для любого n будет доказано, что если утверждение A_n - верно, то верно и утверждение A_n+1.

Пример:

Доказать, что если k ∈ N, то число k² - k - четное.

Решение: Решим задачу с помощью метода математической индукции.

Проверим базу индукции - при k = 1, k² - k = 0 - число четное.

Докажем переход. Допустим при некотором k = n, число n² - n - четное. Докажем, что k = n+1 число (n + 1)² - (n + 1) - тоже четное. Но (n + 1)² - (n + 1) = n² + 2n + 1 - n - 1 = n² + n = n² - n + 2n. Число n² - n - четное, согласно предположению и 2n - четное. Сумма четных чисел - четная. Переход доказан.

Потому при любом k ∈ N число k² - k - четное.

Существуют и другие вариации метода математической индукции. Например, есть последовательность утверждений B₁, B₂, ... , B_n, B_n+1, ..., где n ∈ N. Все утверждения будут истинными, если:

1) Будет доказана истинность утверждения B₁;

2) Для любого n будет доказано, что если утверждения B₁, ... , B_n - верны, то верно и утверждение B_n+1.

Это т.н. принцип полной математической индукции.

3. Принцип Дирихле.

Очевидный, простой в понимании, но в то же время, довольно мощный метод решения задач состоит в следующем: если A элементов разбиты на a групп, причем A > a, то хотя в одной группе будет находится более одного элемента (A, a ∈ N). Данный принцип, являющийся одной из форм метода от противного, был сформулирован известным немецким математиком Дирихле и зачастую формулируется так: Если в n клетках сидит m зайцев и m > n, то хотя бы в одной клетке сидят более одного зайца.

Главная цель в решении такого рода задач - определение "зайцев" и "клеток" в даной конкретной задаче. Чаще всего - это самый трудный этап в решении, так как выбор не всегда очевиден.

Очень ценным является то, что даный метод дает неконструктивное доказательство (ведь мы точно не можем указать, в какой именно клетке находятся более одного зайца); в отличие от конструктивного, когда нужно идти путем полного построения или явно указывать искомый объект, что зачастую приводит к значительным трудностям и затратам времени.

Пример:

Дано 7 различных натуральных чисел. Доказать, что из них можно выбрать два числа, чтобы их разность делилась на 6.

Доказательство: При делении на 6 существует шесть различных остатков: 0, 1, 2, 3, 4, 5. Применим принцип Дирихле. В даному случае "клетками" будут остатки, а "зайцами" - числа. Зайцев 7, а чисел 6. Потому как минимум два числа имеют одинаковые остатки.

Пусть эти числа x и y (x, y ∈ N)

Тогда x = 6p + r, а y = 6q + r. А значит x - y = 6(p - q).

Что и требовалось доказать.

4. Метод раскраски..

Суть данного метода состоит в следующем. Раскрасив некоторые ключевые элементы, которые фигурируют в задаче в несколько цветов, исследовать, что будет происходить, если выполнять условия задачи. Цвет позволяет значительно упростить понимание процесса, фигурируемого в условии, и зачастую приводит к решению. Этот метод позволяет эффективно решать ряд задач, в частности, игровые и шахматные задачи.

Пример:

Дан квадрат клетчатой бумаги размером 8 x 8, из которого вырезаны две крайние диагональные клетки (верхняя-правая и нижняя-левая). Можно ли полученную фигуру покрыть прямоугольниками размером 1 x 2?

Решение: Раскрасим наш обрезанный квадрат с помощью двух цветов в шахматную расцветку. Заметим, что отрезанные диагональные клетки будут одного цвета. Отметим также, что в нашем раскрашенном квадрате любые соседние две клетки (имеющие общую сторону) будут разного цвета. Это значит, что любой прямоугольник размером 1 x 2, которым мы будем пытаться покрыть обрезанный квадрат будет покрывать клетки обоих цветов. И если мы сможем покрыть обрезанный квадрат прямоугольниками 1 x 2, то будет покрыто одинаковое количество клеток с разными цветами; то есть фигура должна содержать одинаковое количество клеток обоих цветов. Но так как мы отрезали диагональные клетки одного цвета, то их количество в обрезанном квадрате на две меньше. Это означает, что мы не сможем польностью покрыть указанный обрезанный квадрат прямоугольниками 1 x 2.

Доказать, что при x > 0 и n є N выполняется неравенство:

Довести, що для довільних додатніх значень х і натуральних значень n виконується нерівність: 1 + хn^-1 >= (1 + x) ^1:n.

Доказательство:

Використаємо нерівність Коші для  n чисел, якщо вважатимемо x₁ = x₂ = ... = x_n-1 = 1, x_n = 1 + x.

Воспользуемся неравенством Коши для n чисел, взяв их следующим образом:

x₁ = x₂ = ... = x_n-1 = 1, x_n = 1 + x

Розв’язати рівняння:

Вказівка. Виділити повні квадрати під квадратними коренями і  розв’язати модульне рівняння.  Так як права частина рівняння дорівнює 1, тоді варто обмежити значення кожного із двох доданків лівої частини від нуля до одиниці. Тому х = 2. Відповідь х = 2.

Решить уравнение

Указание:  Выделите под корнями полніе квадраты разниц.

Доказать, что при всех x є [0; ^π/₂] выполняется неравенство xcosx < .

Доказательство: ля x ≥ 0 выполняется неравенство sinx ≤ x; потому для x є [0; ^π/₂] имеем:
    xcosx = xsin(^π/₂ - x) ≤ x(^π/₂ - x) ≤ ^π2/₁₆.
    А так как π < 3.2, > 1.4, то π² < 10.24, а 8 > 11.2 . Таким образом
    xcosx ≤ ^π2/₁₆ < ^10.24/₁₆ < ^11.2/₁₆ < Что и требовалось доказать.

Решить уравнение 2^[x] = 1 + 2x, где [x] - целая часть числа x.

Ответ: x = -¹/₄, x = 0, x = ⁷/₂
Решение: Преобразуем исходное уравнение в 2^{[x] - 1} = ¹/₂ + [x] + {x}, где {x} = x - [x].
При [x] ≤ -2, 2^{[x] - 1} > ¹/₂ + [x] + {x}^(*), так как правая часть отрицательная. Докажем при помощи метода мат.индукции по [x], что при [x] ≥ 4 неравенство ^(*) также выполняется.
База: [x] = 4, тогда 2^{4 - 1} = 8 > 5¹/₂ > ¹/₂ + 4 + {x}. База доказана.
Переход индукции: Пусть при неком [x] имеет место 2^{[x] - 1} = ¹/₂ + [x] + {x}.
Докажем верность 2^{[x] + 1 - 1} = ¹/₂ + [x] + 1 + {x}.
Согласно переходу: 2^[x] = 2(¹/₂ + [x] + {x}) = ¹/₂ + [x] + {x} + ¹/₂ + [x] + {x} > ¹/₂ + [x] + {x} + 4 > ¹/₂ + [x] + 1 + {x}. Что и требовалось доказать.
Осталось проверить случаи, когда [x] = -1, 0, 1, 2, 3. Перебирая их, находим ответы: x = -¹/₄, x = 0, x = ⁷/₂

Пусть a, b, c, d - целые числа. Доказать, что выражение
((a - c)² + (b - d)²)(a² + b²) - (ad - bc)² является квадратом целого числа.

Указание: Докажите, что ((a - c)² + (b - d)²)(a² + b²) - (ad - bc)² = (a² + b² - ac - bd)².

Для каких натуральных чисел k существуют такие натуральные числа m и n, что m^k + n и n^k + m одновременно являются k-ыми степенями некоторых натуральных чисел?

Ответ:

Решение: Если k = 1, то числа m и n могут быть любыми. Для k ≥ 2 таких натуральных чисел не существует. Докажем от противного.
Пусть это не так. Тогда существует такое натуральное число p ≥ 1, для которого
m^k + n = (m + p)^k. Отсюда получаем:
n = (m + p)^k - m^k = ((m + p) - m)((m + p)^{k - 1} + (m + p)^{k - 2}m + ... + (m + p)m^{k - 2} + m^{k - 1}) >
p(m^{k - 1} + m^{k - 1} + ... + m^{k - 1}) = pkm^{k - 1} > m. Т.е. n > m.
Аналогично, рассматривая другое число, доказывается, что m > n. Противоречие. Значит единственный ответ: k = 1

Каких значений может достигать ab + cd, если a² + b² = 1, c² + d² = 1 и ac + bd = 0?

Ответ:

Решение: Приведенные условия означают в совокупности, что векторы e = (a,b) и f = (c,d) единичные и взамно перпендикулярны.
Потому e = (cos φ, sin φ), f = (cos ψ, sin ψ), причем |φ - ψ| = ^π/₂. Пусть, например ψ = φ + ^π/₂. Тогда f = (-sin φ, cos φ). А потому ab + cd = 0

Вычислить сумму ¹/_1·3 + ¹/_3·5 + ... + ¹/_{(2n - 1)·(2n + 1)},  где n ∈ N.

Указание: Воспользуйтесь равенством ¹/_{k·(k + 2)} = ¹/₂(¹/_k - ¹/_{(k + 2)})

Ответ: ⁿ/_{(2n + 1)}.

Вычислить сумму ⁰/₁ + ¹/_2! + ²/_3! + ... + ^{(n - 1)}/_n!, где n ∈ N.

Указание: Воспользуйтесь равенством ^{(k - 1)}/_k ! = ¹/_{(k - 1)!} - ¹/_k !

Ответ: 1 - ¹/_n!

Вычислить сумму 1·1! + 2·2! + 3·3! + ... n·n!, где n ∈ N.

Указание:  Воспользуйтесь равенством k!k = (k + 1)! - k!

Ответ:  (n + 1)! - 1,

Доказать, что если p и q нечетные, то уравнение x¹⁰ + px⁷ + q = 0 не имеет целых решений.

Указание: Допустим, что x - четное, т.е. x = 2n (n ∈ Z). Тогда уравнение принимает вид:
(2n)¹⁰ + (2n)⁷p + q = 0. Первое слагаемое четное, второе - четное, третье - нечетное. Потому левая часть нечетная. А правая - четная. Имеем противоречие. Четным x не может быть.
Предположим, что x - нечетное, т.е. x = 2n + 1 (n ∈ Z). Тогда уравнение будет иметь вид:
(2n + 1)¹⁰ + (2n + 1)⁷p + q = 0. Первое слагаемое нечетное, второе - нечетное и третье, по условию, - нечетное. Потому и вся левая часть - нечетная. А правая - четная. Противоречие. x - не нечетное. Получается, что x не может быть ни четным, ни нечетным. А значит, x - не целое число

Определить a так, чтобы один из корней уравнения 4x² - 15x + 4a = 0 был квадратом другого.

Указание:

Ответ: