Проект основателей компании «Ваш репетитор»
ERUDITOR.RU

1. Раскраска.1.

Есть большая область, раскрашенная в N=2 цвета — черный и белый.
Доказать, что существуют две точки, расположенные на расстоянии 1,
а) покрашенные в один цвет
б) покрашенные в разные цвета
в) пункт «а» для N=3 цветов
г) пункт «а» для N=4 цветов
2006-11-22

Обсуждение


Задачи :: Раскраска (эквидистантные точки)
↓↓ 0 ↑↑   eruditor.ru (100 / 206)   26 янв 2007 17:20   »»


А в чем собственно подвох?
↓↓ 0 ↑↑   Fender (0 / 15)   29 мар 2007 15:49   «« #2 »»   Ответить


Я может тупой, но не понял, что во что покрашено и что надо доказать?
↓↓ 0 ↑↑   Китаец (0 / 12)   01 май 2007 05:35   «« #3 »»   Ответить


а. на области находим равносторонний треугольник с длинами сторон 1.
Возможны 2 варианта :
- все вершины треугольника окрашены в один цвет, следовательно берем любые 2
вершины,
окрашены в один цвет, и лежат на расстоянии 1;
- 2 вершины одного цвета, а третья другого, тогда решением будут те 2 вершины одного
цвета
↓↓ 0 ↑↑   _KII (0 / 4)   29 май 2007 22:48   «« #4 »»   Ответить


а. на области находим равносторонний треугольник с длинами сторон 1.
Возможны 2 варианта :
- все вершины треугольника окрашены в один цвет, следовательно берем любые 2
вершины - они окрашены в один цвет, и лежат на расстоянии 1;
- 2 вершины одного цвета, а третья другого, тогда решением будут те 2 вершины одного
цвета
↓↓ 0 ↑↑   _KII (0 / 4)   29 май 2007 22:49   «« #5 »»   Ответить


Пожалуйста скажите, условие кто то понял???
↓↓ 0 ↑↑   Biatris (0 / 20)   31 май 2007 17:35   «« #6 »»   Ответить


решение для трех цветов.
Плоскость покрашена в три цвета. Пусть это будет красный, синий, зеленый
цвет. Докажем, что всегда найдутся две точки одного цвета, на расстоянии 1. Предположим противоположное, что существует раскраска плоскости для которой не существует таких точек. Пусть ABCD - ромб в котором AB=BC=CD=DA=1=BD. Не уменьшая общности можно считать, что А красная. АBD - равностороний треугольник, поэтому B - синяя, D - зеленая (или B - зеленая, D -синяя). BCD - равностороний треугольник, поэтому C - красная. Итак для ромба АBCD A и С одного цвета. Рассмотрим другой ромб AKLM, для которого AK=KL=LM=MA=KL=1, и LC=1. L - красная, LC=1 получили противоречие. Итак из A, B, C ,D, K, L, M всегда найдутся две одного цвета на расстоянии 1.


Для 4 цветов это открытая проблема.
↓↓ 0 ↑↑   2+2=5 (0 / 3)   24 ноя 2007 02:32   «« #7 »»   Ответить


хмм.. для 4 цветов - решения нет!
задача решается для случаев когда площадь окрашена в два или три цвета, это елементарно, как аксиома, но вот для 4 цветов - нихт. Представим ситуацию, когда площадь окрашена следующим образом (красный, зеленый, синий, черный): круг черного цвета, небольшого размера по ширине кольцо примыкающего к черному кругу синего цвета, далее очень широкое кольцо зеленого цвета примыкающее к кольцу синего цвета (ширина зеленого во много раз превосходит ширину внутренего синего кольца и черного круга), остальнач площадь окрашена в красный цвет. При таком положении цветов нельзя найти такого растояния черного-красного, которая бут равняца черному-синему. Или я чегото недопонял, или условие задачи некорректно.
↓↓ 0 ↑↑   Zloy (0 / 69)   21 дек 2007 14:41   «« #8 »»   Ответить


Решение есть!и возможно для любого количества цветов больше одного и для сплошной области
Условие (а) выполняется если за единицу принять диаметр окружности полностью попадающей в монотонную часть области
↓↓ 0 ↑↑   Arietz (0 / 9)   16 мар 2008 12:18   «« #9 »»   Ответить


Доказательство (а) определяет также выполнение (б)
Количество цветов не имеет значения, так как любая пара цветов уже будет разными цветами:)
рассмотрим две монотонные области разных цветов, соприкасающиеся хотябы в одной точке. Возьмем точку соприкосновения из одной области и соблюдение условия (а) для другой. Из этой точки проведем окружность, проходящую через максимально удаленную точку соседней области. Учитывая условие (а) получаем радиус окружности >=1. Окружность любого меньшего радиуса также пересекает соседнюю область хотя бы в одной точке (равнозначно тому,что точки разного цвета находятся на расстоянии радиуса). А окружность с радиусом =1 попадает в это определение.
↓↓ 0 ↑↑   Arietz (0 / 9)   16 мар 2008 12:50   «« #10 »»   Ответить


Значение единицы, как и раскраска - задано, его нельзя выбирать
↓↓ 0 ↑↑   eruditor (128 / 439)   16 мар 2008 18:59   «« #11 »»   Ответить


3 и 4
Представьте белую плоскость, где есть одна красная и одна белая точка на расстоянии, например, 10 единиц. 3 и 4 тогда не выполнятся. Так что надо определять правила раскрашивания.
↓↓ 0 ↑↑   Slavan (0 / 2)   11 апр 2008 14:55   «« #12 »»   Ответить


2 Slavan
Неужели вы не найдёте на почти белой плоскости две точки белого цвета, находящиеся на расстоянии 1?
↓↓ 0 ↑↑   eruditor (128 / 439)   12 июн 2008 04:20   «« #13 »»   Ответить


для 3 и 4, и более цветов доказательство работает также, как и для 2-х. Точки всего две, и они могут быть окрашены либо в один цвет, либо в 2 разных. Окрашенная область состоит из множества точек, а вообще любую плоскость, как известно, можно построить на
↓↓ 0 ↑↑   Lilu (0 / 2)   01 фев 2010 01:01   «« #14 »»   Ответить


основе 3-х точек
↓↓ 0 ↑↑   Lilu (0 / 2)   01 фев 2010 01:01   «« #15 »»   Ответить


двух одинаковых рядом может и не быть если они расположены строго в шахматном порядке
↓↓ 0 ↑↑   йцукеекуцй (0 / 1)   13 окт 2010 20:58   «« #16 »»   Ответить


Цвета, конечно, могут повторяться на разных расстояниях и одинаковые рядом тоже могут быть, если их расскрашивать разнообразно по своему усмотрению в яркие цвета!
↓↓ 0 ↑↑   Черных Ольга Витальевна (-10 / 3)   14 окт 2013 16:00   «« #19 »»   Ответить


Для любого количества цветов задача решается . Разместить окружность диаметром 1 можно так , чтобы окружность пересекала все цвета . А если цвета распределять в особом порядке , то это уже будет другая задача .
↓↓ 0 ↑↑   Виктор (0 / 7)   22 апр 2011 18:04   «« #17 »»   Ответить


Опечатка
Разумеется вместо "диаметр" нужно читать "радиус" .
↓↓ 0 ↑↑   Виктор (0 / 7)   27 апр 2011 14:37   «« #18 »»   Ответить


Две одинаковые точки могут повторяться на любом расстоянии, ведь вершины гор всегда усыпаны белым снегом с различными оттенками
↓↓ −5 ↑↑   Черных Ольга Витальевна (-10 / 3)   14 окт 2013 16:10   «« #20   Ответить



Ваше имя
Email
Текст ответа
© 2006-2017   Авторы