Задачки

Sergei Nickolaev написал(а) к All в Jul 17 02:20:17 по местному времени:

Привет!

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

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

Сергей

---
Это сообщение проверено на вирусы антивирусом Avast.
https://www.avast.com/antivirus

--- FIDOGATE 5.1.7ds

Alexander Hohryakov написал(а) к Sergei Nickolaev в Jul 17 13:24:22 по местному времени:

Здpавствуй, Sergei!

Среда 12 Июля 2017 02:20, ты писал(а) All, в сообщении по ссылке area://starper.limited?msgid=2:5020/2140.2+595ae0f1:

SN> Последняя из интересных была про "пьяных кроликов". Действительно
SN> хорошая задачка и, что забавно, мой подход (длинным путем) должен был
SN> привести к правильному решению :-) А именно, попытка доказать, что
SN> пересекающиеся пробы не дают кардинального преимущества, обязана была
SN> дать ключ к решению. Но, неважно, времени не было, не успел.
SN> В качестве мести предлагаю две (удивительно простые - когда решишь)
SN> задачи.
SN> Итак:
SN> Плоскость раскрашена в два цвета (к примеру, в черный и белый цвета)
SN> совершенно произвольным образом, но оба цвета присутствуют. То есть,
SN> на плоскости есть хотя бы одна белая точка и хотя бы одна черная.
SN> Нужно доказать, что для любого (вещественного числа) А найдутся:
SN> 1.
SN> Две точки одного цвета, находящиеся на расстоянии А.

Окружность с центром в точке одного цвета радиуса А. Если на ней есть хоть одна точка того же цвета, задача решена, если все точки на ней другого цвета - две из них, находящиеся на расстоянии А друг от друга. Или я что-то упустил, или это действительно простая задача.

SN> 2. Две точки
SN> разного цвета, находящиеся на расстоянии А.

Две пересекающиеся окружности.

Не помню, я уже рассказывал тут про коэффициент трения бруска о стол?


С уважением - Alexander
--- -

Sergei Nickolaev написал(а) к Alexander Hohryakov в Jul 17 23:08:49 по местному времени:

Привет!

12.07.2017 12:16, Alexander Нohryakov пишет:
> SN> 1.
> SN> Две точки одного цвета, находящиеся на расстоянии А.
>
> Окружность с центром в точке одного цвета радиуса А. Если на ней есть хоть одна точка того же цвета, задача решена, если все точки на ней другого цвета - две из них, находящиеся на расстоянии А друг
> от друга. Или я что-то упустил, или это действительно простая задача.

Это - простая задача :-). Есть более изящное решение (по сути - такое
же, но формулировка красивее): равносторонний треугольник. Его вершины -
решение.

Но обобщение этой задачи на N цветов - задача серьезная и, насколько мне
известно, до сих пор полностью не решенная. Для 9 цветов (а,
следовательно и для большего количества) довольно нетрудно доказать (у
меня когда-то быстро получилось), что утверждение неверно. Для трех
цветов я когда-то нашел решение (сложное) сам. Я могу ошибаться (давно
читал, мог забыть), но осталось в памяти, что доказательство для 4-х
цветов существует и существует опровержение для 8-ми. Оставшиеся случаи:
5, 6 и 7 цветов остаются нерешенной математической проблемой.

>
> SN> 2. Две точки
> SN> разного цвета, находящиеся на расстоянии А.
>
> Две пересекающиеся окружности.

Здесь я не понял. У меня такое построение ничего не доказало.
Стандартное решение - простое. Эта задача и не рассматривалась
организаторами, как что-то особо трудное и, как мне рассказывал М. И.
Башмаков, проводивший у нас эту олимпиаду, считалось существенным, что
некоторый факт, кажущийся очевидным, требовалось доказать (по индукции).
Доказавшие получали максимальное количество баллов за решенную задачу,
не посчитавшие нужным - теряли баллы. Никто не ожидал, что кто-то
построит доказательство совсем иначе, что и дало мне столь нужное мне
преимущество :-)

> Не помню, я уже рассказывал тут про коэффициент трения бруска о стол?

Рассказывал. Очень хорошая задача. Требуется оптимальное сочетание
экспериментатора и теоретика. Экспериментатор непременно попробовал бы
(среди всего прочего) потолкать брусок на разной высоте, а теоретик
потом быстренько нарисовал бы нужные формулы :-)

Сергей


---
Это сообщение проверено на вирусы антивирусом Avast.
https://www.avast.com/antivirus

--- FIDOGATE 5.1.7ds

Alexander Hohryakov написал(а) к Sergei Nickolaev в Jul 17 09:31:34 по местному времени:

Здpавствуй, Sergei!

Среда 12 Июля 2017 23:08, ты писал(а) мне, в сообщении по ссылке area://starper.limited?msgid=2:5020/2140.2+64118bcf:

>> SN> 1.
>> SN> Две точки одного цвета, находящиеся на расстоянии А.
>>
>> Окружность с центром в точке одного цвета радиуса А. Если на ней
>> есть хоть одна точка того же цвета, задача решена, если все точки на
>> ней другого цвета - две из них, находящиеся на расстоянии А друг от
>> друга. Или я что-то упустил, или это действительно простая задача.

SN> Это - простая задача :-). Есть более изящное решение (по сути - такое
SN> же, но формулировка красивее): равносторонний треугольник. Его вершины
SN> - решение.

Мне окружность показалась более красивой, но о вкусах не спорят.

SN> Но обобщение этой задачи на N цветов - задача серьезная и, насколько
SN> мне известно, до сих пор полностью не решенная. Для 9 цветов
SN> (а, следовательно и для большего количества) довольно нетрудно
SN> доказать (у меня когда-то быстро получилось), что утверждение неверно.
SN> Для трех цветов я когда-то нашел решение (сложное) сам. Я могу
SN> ошибаться (давно читал, мог забыть), но осталось в памяти, что
SN> доказательство для 4-х цветов существует и существует опровержение для
SN> 8-ми. Оставшиеся случаи: 5, 6 и 7 цветов остаются нерешенной
SN> математической проблемой.

Это интереснее. Надо обдумать, а у нас настала ясная погода :-)
>>
>> SN> 2. Две точки
>> SN> разного цвета, находящиеся на расстоянии А.
>>
>> Две пересекающиеся окружности.

SN> Здесь я не понял.

Две пересекающиеся окружности с центрами по разные стороны границы цветов. Первое, что приходит в голову после одной окружности из задачи 1.

SN> У меня такое построение ничего не доказало.
SN> Стандартное решение - простое. Эта задача и не рассматривалась
SN> организаторами, как что-то особо трудное и, как мне рассказывал М. И.
SN> Башмаков, проводивший у нас эту олимпиаду, считалось существенным, что
SN> некоторый факт, кажущийся очевидным, требовалось доказать (по
SN> индукции). Доказавшие получали максимальное количество баллов за
SN> решенную задачу, не посчитавшие нужным - теряли баллы. Никто не
SN> ожидал, что кто-то построит доказательство совсем иначе, что и дало
SN> мне столь нужное мне преимущество :-)

Как это? Если в задаче встретилась теорема Пифагора, приводить её доказательство? Вы не считались с расходом графита и времени.

>> Не помню, я уже рассказывал тут про коэффициент трения бруска о
>> стол?

SN> Рассказывал. Очень хорошая задача. Требуется оптимальное сочетание
SN> экспериментатора и теоретика. Экспериментатор непременно попробовал бы
SN> (среди всего прочего) потолкать брусок на разной высоте, а теоретик
SN> потом быстренько нарисовал бы нужные формулы :-)

Формулы элементарные, главное - догадаться, что брусок надо поставить на стол, а не положить. На уроках физики его подцепляли к динамометру и возили по столу, картинка эта у всех в памяти.

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

С уважением - Alexander
--- -

Sergei Nickolaev написал(а) к Alexander Hohryakov в Jul 17 21:51:24 по местному времени:

Привет!

13.07.2017 8:31, Alexander Нohryakov пишет:

> Мне окружность показалась более красивой, но о вкусах не спорят.

Если ты внимательно посмотришь на свое доказательство (разумеется,
правильное), то увидишь, что равносторонний треугольник ты там построил
:-) В результате, остальные построения становятся лишними - треугольника
достаточно.

> Это интереснее. Надо обдумать, а у нас настала ясная погода :-)

У нас тоже вчера началось, наконец-то, лето :-). Я отметил это дело
окрошкой.
И липа зацвела, опоздание относительно типичного срока - почти 2 недели.
Сегодня с утра съездили с приятелями грибов пособирать, их пока мало, но
практически все - без червей. Белые (боровые, сосновые) и подосиновики.
Еще полно лисичек, но я не любитель ...

> Две пересекающиеся окружности с центрами по разные стороны границы цветов. Первое, что приходит в голову после одной окружности из задачи 1.

Ага, понятно. Здесь еще нужно доказать, что обязательно найдутся две
точки разного цвета на расстоянии меньше А. Иначе у тебя не получатся
пересекающиеся окружности. Это, понятно, доказывается легко. В
результате у тебя получится стандартное решение в чуть другом оформлении.
Стандартное решение такое:
По условию задачи существует пара точек разного цвета. Соединяем их
ломаной линией со звеньями длиной А. Это просто.
Если точки находятся на расстоянии меньшем, чем А, то ломаная - боковые
стороны равнобедренного треугольника, у которого основание - отрезок
соединяющий точки.
Если расстояние - А или кратно А, то ломаная линия вся лежит на отрезке,
соединяющем точки.
Если расстояние больше А и не кратно А, то ломаная линия лежит на
отрезке, соединяющем точки, кроме последних двух звеньев, которые
строятся, как в первом случае.
Для получения максимума баллов за эту задачу нужно было еще привести
доказательство такого утверждения:
Если концы ломаной линии имеют разный цвет, то найдется хотя бы одно
звено этой ломаной, имеющее концы разного цвета.

Сергей


---
Это сообщение проверено на вирусы антивирусом Avast.
https://www.avast.com/antivirus

--- FIDOGATE 5.1.7ds

Alexander Hohryakov написал(а) к Sergei Nickolaev в Jul 17 00:01:36 по местному времени:

Здpавствуй, Sergei!

Четверг 13 Июля 2017 21:51, ты писал(а) мне, в сообщении по ссылке area://starper.limited?msgid=2:5020/2140.2+71784766:

>> Мне окружность показалась более красивой, но о вкусах не спорят.

SN> Если ты внимательно посмотришь на свое доказательство (разумеется,
SN> правильное), то увидишь, что равносторонний треугольник ты там
SN> построил
SN> :-) В результате, остальные построения становятся лишними -
SN> треугольника достаточно.

Я знаю, но окружность всё равно эстетичнее: не возникает вопроса, почему выбрали эту точку, а не ту. Все равны, как рыцари за столом короля Артура (про него я читал лишь в кратком пересказе, как и про математику)

>> Это интереснее. Надо обдумать, а у нас настала ясная погода :-)

SN> У нас тоже вчера началось, наконец-то, лето :-). Я отметил это дело
SN> окрошкой.

Эх!

SN> И липа зацвела, опоздание относительно типичного срока - почти 2
SN> недели. Сегодня с утра съездили с приятелями грибов пособирать, их
SN> пока мало, но практически все - без червей. Белые (боровые, сосновые)
SN> и подосиновики.

Здорово! У нас уже волна белых прошла, ждём следующую.

SN> Еще полно лисичек, но я не любитель ...

Собирать или есть? Готовить их меня научили лет десять назад. Главное - не перегреть; чуть сильнее огонь - и вместо грибов резинообразная консистенция.

С уважением - Alexander
--- -