Задачка

Докажите, что на плоскости существует множество, состоящее из девяти точек, и обладающее следующим свойством: при любом разбиении этого множества на два подмножества, хотя бы в одном из подмножеств найдутся три точки, являющиеся вершинами правильного треугольника.

Цитата
marijaconstantinovna
поскольку множество из девяти точек мы можем разбить на два подмножества в том числе и такими способами, при которых в одном из подмножеств окажется не более двух точек. Поэтому условие задачи следует формулировать следующим образом:

Докажите, что на плоскости существует множество, состоящее из девяти точек, и обладающее следующим свойством: при любом разбиении этого множества на два подмножества таким образом, что в каждом из подмножеств содержится не менее трех точек, хотя бы в одном из подмножеств найдутся три точки, являющиеся вершинами правильного треугольника.

Приказ холопам был сформулирован верно, я уже выполнил этот приказ и рад выполнить новые приказы.

Я, например, принципиально не отвечаю на вопросы, отданные в форме приказа холопам, поскольку не знаю, "чьих я холоп".

Цитата
marijaconstantinovna
При любом разбиении множества вершин звезды (а стало быть, и совпадающего с ним множества вершин правильного девятиугольника) на два подмножества как минимум в одном из них будут содержаться вершины правильного треугольника.

Простейшее разбиение 9-угольника прямой, проходящей через центр и не проходящей через вершину, делит множество его вершин на два подмножества, такие что никакие его три вершины, содержащиеся в одном множестве, не являются вершинами правильного треугольника.
Может быть, marijaconstantinovna имела в виду что-нибудь другое (?) – желательно пояснить.

Цитата
kitonum
Множество вершин правильного девятиугольника не подходит, что очень легко проверяется. Зато подходит следующее множество {[-2,0], [-1,sqrt(3)], [1,sqrt(3)], [2,0], [1,-sqrt(3)], [-1,-sqrt(3)], [0,0], [3,sqrt(3)], [3,-sqrt(3)]} (проверил с помощью компа)
Конечно, более интересно было бы доказать, что никакое множество из меньшего числа точек подобным свойством не обладает.

Как всегда, от kitonum’а красивый результат и, кроме того, задача, от поиска решения которой трудно удержаться. Как будто, удалось найти доказательство. Если не вскроются погрешности, то постараюсь оформить с небольшой задержкой. Несколько озадачивает то, что оно проходит и для конструкций из 8 точек с равнобедренными треугольниками. Но не найдется ли здесь контрпримера?

Точки будем обозначать их номерами, так что исходное множество точек – это $ S=\{1, 2,..., 8\} . $ Конфигурацию точек будем задавать $ (N,8) $-матрицей, столбцы которой соответствуют точкам, а строки – правильным треугольникам, причем в каждой из $ N $ строк единицы стоят в тех столбцах, номера которых соответствуют вершинам некоторого правильного треугольника (остальные нули). Каждое разбиение множества $ S $ на 2 подмножества $ A $ и $ B $ будем задавать последовательностью $ x=(x_1,...,x_8) $ над $ J = \{-1,1\}: i \in A \Leftrightarrow x_i =1 $ и: $ i \in B \Leftrightarrow x_i =-1. $ Последовательность $ x $ является подходящей (соответствующее разбиение удовлетворяет условию задачи), если $ \max_s |[s,x]| =1, $ где $ [ \cdot ] $ – скалярное произведение. Нужно показать, что для любой допустимой матрицы (т. е. соответствующей некоторой конфигурации) найдется подходящая последовательность.

Пронумеруем для начала точки из $ S $ таким образом, чтобы первые 4 точки были с одной стороны некоторой рассекающей конфигурацию прямой, а последние 4 – с другой: $ S_1=\{1,2,3,4\}, S_2=\{5,6,7,8\}. $ При этом из множества всех разбиений будем рассматривать лишь те, для которых $ x_1=1, x_1+x_2+x_3+x_4=0 $ и $ x_5+x_6+x_7+x_8=0. $ Множество таких последовательностей $ x $ обозначим $ \Omega; $ очевидно, $ |\Omega |=18. $

Учитывая, что каждая последовательность из $ \Omega $ разбивает множества $ S_1, S_2 $ на подмножества с двумя элементами, из исходной матрицы можно исключить строки, в которых все три единицы находятся либо в первых четырех, либо в последних четырех столбцах матрицы. При этом в матрице останется не более 12 строк. Максимальная матрица с учетом возможности дополнительной перенумерации строк и столбцов может быть приведена к виду
$M=\left(\begin{array}{rr} M_{11}& M_{12} \\ M_{21}& M_{22} \end{array}\right),$
где строки в (6,4)-подматрицах $ M_{11} = M_{22} $ представляют собой различные 4-элементные последовательности, содержащие 2 единицы, а строки в $ M12, M21 $ содержат по 1 единице.

Затем простым перебором был установлен факт существования подходящего разбиения из $ \Omega $ для всех вариантов таких матриц (с сокращением числа переборов за счет симметрии области). Попытка сократить число переборов для представления доказательства в аналитическом варианте не удалась.



Редактировалось 3 раз(а). Последний 07.03.2015 20:38.