6 точек это ситуация центра 6 угольника. Там расстояние между соседними точками на 6 угольнике равны расстоянию от центра и до соседа. Но по условию равны они быть не могут и какой-то из сателлитов надо отдалить от центра. Но он тогда соседние сателлиты станет ближе центра, и из центра 6 линий не будет идти.
Доказательство второй, видимо, основывается на том что в правильном шестиугольнике все шесть вершин равноудалены от центра и от пары соседних и, поскольку расстояния между точками не равны, получается максимум 5.
Можно без теоремы Холла, тем более что числа у нас тут вещественные. Известно: матрица n×n имеет только неотрицательные элементы, сумма которых в любой строке и любом столбце равна 1. Все такие матрицы образуют многогранник в евклидовом пространстве, так как это множество решений системы линейных уравнений и неравенств, и оно, очевидно, ограничено. Нетрудно показать, что вершины полученного многогранника - это матрицы перестановок и только они. А все остальные точки - всевозможные линейные комбинации вершин с положительными коэффициентами, сумма которых равна 1. Собственно, занавес.
Посчитаем размерность. Наложили 2n уравнений, но они зависимы - любое одно можно выкинуть. Так что многогранник имеет размерность (n-1)2. В вершине должно сойтись не меньшее число граней. Значит, в матрице, отвечающей вершине, не меньше такого числа нулей (как минимум столько неравенств должны обратиться в равенство). Отсюда найдется строка, в которой все нули, кроме одного элемента. Этот оставшийся элемент равен 1. Дальше по индукции.
1. Aij - площадь пересечения i-й части первого разбиения и j-й части второго. Сумма элементов любой строки/любого столбца матрицы А равна сотой части площади исходного квадрата S, причём все элементы неотрицательны. Заметим, что т.к. перестановка строк или столбцов матрицы A отвечает перенумерованию частей первого или второго разбиения, указанное свойство матрицы A сохраняется при таких перестановках.
Назовём молнией набор элементов матрицы, которые получаются из главной диагонали перестановкой столбцов. Тогда задача сводится к доказательству того, что у матрицы A существует молния, все элементы которой отличны от нуля.
Предположим обратное.
Выберем какую-нибудь молнию, она содержит 0. Перестановками добьёмся A100,100=0. Выберем другую молнию. Добьёмся A99,100=0. Перебрав 100 молний, получим последнюю строку из нулей. Но сумма элементов этой строки должна быть равна S/100. "Полученное проиворечие доказывает теорему".
Comments 30
6 точек это ситуация центра 6 угольника. Там расстояние между соседними точками на 6 угольнике равны расстоянию от центра и до соседа. Но по условию равны они быть не могут и какой-то из сателлитов надо отдалить от центра. Но он тогда соседние сателлиты станет ближе центра, и из центра 6 линий не будет идти.
Reply
Говорить о сложности первой задачи, думаю, бессмысленно.
Reply
Reply
Во второй попроще, напротив угла в 60 градусов или меньше не может быть самая длинная сторона в треугольнике.
Reply
Известно: матрица n×n имеет только неотрицательные элементы, сумма которых в любой строке и любом столбце равна 1. Все такие матрицы образуют многогранник в евклидовом пространстве, так как это множество решений системы линейных уравнений и неравенств, и оно, очевидно, ограничено. Нетрудно показать, что вершины полученного многогранника - это матрицы перестановок и только они. А все остальные точки - всевозможные линейные комбинации вершин с положительными коэффициентами, сумма которых равна 1. Собственно, занавес.
Reply
Reply
Reply
Назовём молнией набор элементов матрицы, которые получаются из главной диагонали перестановкой столбцов. Тогда задача сводится к доказательству того, что у матрицы A существует молния, все элементы которой отличны от нуля.
Предположим обратное.
Выберем какую-нибудь молнию, она содержит 0. Перестановками добьёмся A100,100=0. Выберем другую молнию. Добьёмся A99,100=0. Перебрав 100 молний, получим последнюю строку из нулей. Но сумма элементов этой строки должна быть равна S/100. "Полученное проиворечие доказывает теорему".
Reply
Reply
Leave a comment