avva | доказательства и решения: математика

Вот решения математических задач в моём дневнике за позавчера (условия здесь).

Первую задачу проще всего решить так. Положим фигуру на плоскость произвольным способом. Выберем один какой-то фиксированный квадрат координатной сетки и "наложим" на него все квадраты, которые содержат в себе часть фигуры, копируя точки фигуры из каждого такого квадрата, сохраняя их относительные координаты внутри квадрата. Площадь получившейся фигуры внутри нашего фиксированного квадрата меньше или равна первоначальной площади, т.е. меньше единицы. Поэтому есть точка внутри квадрата, к-я не принадлежит "скопированной" фигуре. Если x - вектор, перемещающий эту точку в ближайший узел сетки, то сдвиг первоначальной фигуры на минус x даёт искомое размещение.

Более строгую формулировку решения можно найти вместе с дискуссией в комментах к записи с условиями.

Вторую задачу никто в комментах правильно не решил. Напрашивающийся подход с индукцией по кол-ву точек не работает. Задача решается с помощью метрического подхода, т.е. необходимо использовать расстояния между точками, а не просто бинарные взаимоотношения типа "лежит на одной прямой с". Подозреваю, что эту необходимость использовать расстояния можно строго доказать (построив пространство, в к-м утверждение неверно), но мне лень ;) Вот одно возможное простое доказательство утверждения:

Предположим, что не все точки лежат на одной прямой. Значит, существуют тройки точек типа (A,B,X) где A,B и X не лежат на одной прямой. Из всех возможных таких троек (к-х конечное число) выберем такую, для которой длина перпендикуляра из точки X на прямую AB минимальна. Пусть XO - перпендикуляр из X на прямую AB, O - точка на прямой. Удобно для дальнейшего представить себе эту картину так: АB - горизонтальная прямая, А левее B, а X - где-то над ними сверху.

Ясно, что углы XAB и XBA - острые, а не тупые. Почему? Потому что если например XAB - тупой угол, то перпендикуляр из A на XB меньше по длине, чем перпендикуляр из X на AB, в противоречие нашему выбору (A,B,X). Значит, X находится "между" A и B, внутри полосы, ограниченной перпендикулярами к AB из A и B.

Согласно условию на прямой AB есть ещё одна точка C из нашего набора. Теперь замечаем, что где бы не находилась C, она обязательно образует вместе с X и одной из точек {A,B} треугольник с углом >=90 градусов вдоль прямой AB. Например, если C "левее" A, то CAX - тупой угол; если С между А и О, то ACX - тупой угол; если C совпадает с O, то ACX - прямой угол, и т.д. В любом случае мы получаем, что в треугольнике с углом >=90 градусов, будь то ACX или BCX, перпендикуляр из вершины с этим большим углом (будь то A,B, или C) на противоположную сторону меньше по длине, чем XO (перпендикуляр из вершины X этого же треугольника). Получаем опять-таки противоречие нашему выбору XO как минимального перпендикуляра. Что и требовалось доказать.

(несколько раз использовалось следующее тривиальное утверждение: в произвольном треугольнике с углом >=90 градусов высота, выходящая из этого угла - наменьшая по длине из всех трёх высот. Док-во напр. такое: по теореме косинусов противолежащая этому углу сторона длиннее всех остальных; площадь треугольника равна половине произведения этой стороны и высоты, поэтому высота меньше всех остальных).

Другой способ сформулировать то же доказательство: начать с любой тройки (A,B,X), построить новую тройку (A",B",X") и заметить, что в ней длина перпендикуляра из X" меньше, чем в первой тройке длина перпендикуляра из X. Значит, продолжая этот процесс, мы никогда не пройдём одну и ту же тройку точек дважды, что противоречит конечности набора точек.

Интересны в этой задаче два аспекта.

1. Хитрая проблема с "тривиальным" индуктивным док-вом. Как правило, при попытке решить задачу оно приходит на ум первым; все, кому я её предлагал, находили его и не видели в нём ошибки, пока им не объясняли (это включает и меня, когда мне впервые показали эту задачу).
Т.е. эта задача замечательно вскрывает шаблон в индуктивном мышлении, которым мы привыкли пользоваться, но который не всегда верен.

2. Совершенно непонятная, по крайней мере на первый взгляд, необходимость использовать метрические свойства пространства (т.е. расстояния между точками).

Пока всё.