Точки в пространстве

[Rasool]

Вот следующая задачка из Кванта:

Цитата:

В пространстве даны 9 точек, никакие из них не лежат на одной плоскости. Все эти точки попарно соединены отрезками. Отрезок может быть закрашен в синий или красный цвет, или остаться незакрашеным. Найдите наименьшее значение n такое, что при любом закрашивании любых n отрезков найдется треугольник, все стороны которого будут закрашены в один цвет.

Меня интересует ход решения такой задачи. Могу подсказать, что n можно определить с помощью неравенств. А что делать дальше? Какие факты устанавливать, доказывать?

[caxap]

По-моему, это что-то на теорему Рамсея.

[Cash]

Пропущено никакие (4?) из них не лежат на одной плоскости.
Из чего должно следовать, что любые 3 из них не лежат на одной прямой.

Если можно выделить полный закрашенный граф с 6-ю вершинами, то
далее - известная задача о тройке попарно знакомых или попарно незнакомых.
У меня это для n=33 получилось. Но боюсь, что далековато от ответа

[Rasool]

Cash в сообщении #366084 писал(а):

Пропущено никакие (4?) из них не лежат на одной плоскости.
Из чего должно следовать, что любые 3 из них не лежат на одной прямой.

Прошу прощения.

Cash в сообщении #366084 писал(а):

Если можно выделить полный закрашенный граф с 6-ю вершинами, то
далее - известная задача о тройке попарно знакомых или попарно незнакомых.
У меня это для n=33 получилось. Но боюсь, что далековато от ответа

Отсюда имеем: n <= 33. Один шаг уже сделан.

-- Пн окт 25, 2010 22:12:39 --

caxap в сообщении #366076 писал(а):

По-моему, это что-то на теорему Рамсея.

Спасибо за статью. :)

[maxal]

Простенькая оценка снизу: $n>4\cdot 5 + 2\cdot 2 + 2\cdot 3=30$.
Дело в том, что если разделить точки на две группы из 5-ти и 4-х точек и покрасить синим 20 отрезков, соединяющие точки из разных групп, то одноцветного треугольника там не будет. Далее каждую группу делим на две подгруппы и аналогично красим отрезки с концами из разных подгрупп красным. Одноцветного треугольника там по-прежнему не будет.

[Edward_Tur]

http://kvant.mirror1.mccme.ru/1993/05/p37.htm
http://kvant.mirror1.mccme.ru/1993/05/p38.htm

[Rasool]

Edward_Tur в сообщении #366209 писал(а):

http://kvant.mirror1.mccme.ru/1993/05/p37.htm
http://kvant.mirror1.mccme.ru/1993/05/p38.htm

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

[Профессор Снэйп]

Пусть $A \subseteq \mathbb{R}^n$. Назовём $A$ хорошим, если для любых различных $a,b,c,d \in A$ отрезки $[a,b]$ и $[c,d]$ не пересекаются, и для любых различных $a,b,c \in A$ справедливо $[a,b] \cap [b,c] = \{ b \}$.

Какова максимальная мощность хорошего множества? Для $n=2$ она вроде бы равна $4$ (кстати, как это доказать?) А для $n=3$?

[maxal]

Профессор Снэйп в сообщении #367300 писал(а):

Какова максимальная мощность хорошего множества? Для $n=2$ она вроде бы равна $4$ (кстати, как это доказать?) А для $n=3$?

Для $n=2$ нужно взять выпуклую оболочку точек. Она может быть только треугольником (в $n$-угольнике для $n>3$ найдутся пересекающиеся диагонали), вершинами которого являются три точки из данных. Остальные точки лежат внутри этого треугольника. Легко видеть, однако, что больше одной точки внутри треугольника быть не может.
А для $n=3$ ответ - континуум. Досточно брать точки общего положения - чтобы никакие три не лежали на одной прямой, и никакие четыре -- в одной плоскости.

[Профессор Снэйп]

maxal в сообщении #367339 писал(а):

А для $n=3$ ответ - континуум. Досточно брать точки общего положения - чтобы никакие три не лежали на одной прямой, и никакие четыре -- в одной плоскости.

С ответом согласен. Осталось лишь доказать, что это самое "общее положение" существует для целого континуума точек.

Я знаю два таких доказательства. Одно --- трансфинитная индукция по ординалам, меньшим $c$, другое --- через определитель Вандермонда. Не назвал бы ни одно из них "очевидным"

Хотя, может, действительно чего-то очевидного не вижу?

[svv]

Кусок спирали $x=\cos t$, $y=\sin t$, $z=t$, $t \in [0, \pi/2]$.

[Профессор Снэйп]

svv в сообщении #367521 писал(а):

Кусок спирали $x=\cos t$, $y=\sin t$, $z=t$, $t \in [0, \pi/2]$.

Готов поверить, но... Доказательство?!

[svv]

1) Никакие три точки не лежат на одной прямой.
Если бы таковые нашлись, то на одной прямой лежали бы и их проекции на плоскость $Oxy$. А проекция моего куска спирали на $Oxy$ - это четверть окружности, имеющая с любой прямой максимум две точки пересечения.

2) Никакие четыре точки не лежат в одной плоскости.
(продолжение следует)

[Rasool]

Вот такая задачка:

Цитата:

Пусть сумма n чисел равна нулю, причем m - наименьшее из них, а M - наибольшее. Докажите, что сумма квадратов этих чисел не превосходит -mMn

Сразу могу сказать, что задача - на конструирование решения, путем использования факта "заметим, что". Но как получить этот факт? Я хотел бы узнать ход решения этой задачи. Мои попытки: 1) попытался возвести в квадрат сумму чисел; 2) попробовал использовать метод мат. индукции. Не получилось.

[maxal]

Rasool в сообщении #367550 писал(а):

Пусть сумма n чисел равна нулю, причем m - наименьшее из них, а M - наибольшее. Докажите, что сумма квадратов этих чисел не превосходит -mMn

Переформулирую задачу: даны два набора неотрицательных чисел с одинаковой суммой. В одном набор числа не превосходят числа $m$, в другом -- числа $M$. Доказать, что сумма квадратов всех чисел не превосходит $mMn$, где $n$ - общее количество чисел в обоих наборах.

Обозначим сумму чисел в каждом наборе через $S$. Тогда количество чисел в первом наборе не меньше $\frac{S}{m}$, а во втором - не меньше $\frac{S}{M}$, то есть

$$ \frac{S}{m} + \frac{S}{M} \leq n.$$

Вогнутость суммы квадратов при фиксированной сумме даёт также, что сумма квадратов в первом наборе не превосходит:

$$\frac{S-x}{m} \cdot m^2 + x^2 = (S-x)m + x^2 = Sm - x(m-x) \leq Sm,$$

где $x=S\bmod m$ и аналогично для второго набора:

$$\frac{S-y}{M} \cdot M^2 + y^2 = SM - y(m-y) \leq SM,$$

где $y=M\bmod S$.

Итак, сумма квадратов всех чисел не превосходит

$$Sm + SM = mM\left(\frac{S}{M} + \frac{S}{m}\right) \leq mMn.$$