Квадрат с вершинами одного цвета #716247

На координатной плоскости все точки с целыми координатами раскрашены в один из трех цветов. Обязательно ли найдется квадрат с вершинами в точках с целыми координатами, раскрашенными в один цвет?

да

[:||||||||:]

1) Крашу 1 координатную четверь в один цвет; 2) Высунув язык рисую квадрат (1;1) (2;2) (1;2) (2;1); 3) Квадрат не виден, его все вершины такого цвета, как и 1 координатная четверть! Что это?!

да

рёбра квадрата должны быть параллельны осям координат?

стороны квадрата? ну, вообще говоря, нет, но можно и потребовать ))

Задача для 10-го класса, не требующая особых знаний? Сейчас у сына спрошу, может решит.

Злой ты.

Вроде к последовательности должно сводится, но хрен знает как.

далеко тебе до десятиклассников

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

Сын восьмой класс закончил, но думаю решит.

может, с точки зрения бога, раскрашивать точки куда более важное занятие, чем какие-то там людишки

А по-русски: можно ли раскрасить точки координатной плоскости, так чтоб нельзя была нарисовать квадрат с вершинами одинакого цвета?

*было

Нет

В оригинале было: Плоскость раскрашена в n цветов. Доказать, что существует квадрат с вершинами одного цвета.

Правильный ответ - "Да".

А как доказать что существует?

Начиная с отрезка.

Дать ссылку на доказательство? Или пока помучаешься? Для справки - то что в оригинале написано что доступно для десятиклассников без спецзнаний - это видимо такой юмор. Не доказать сможет десятиклассник, а понять доказательство сможет десятиклссник. С огромным трудом научным миром в свое время была доказана намного более простая теорема.

А какой максимально большой квадрат плоскости можно разрисовать, чтобы в нем нельзя было построить квадрат с вершинами одинакого цвета?

А квадрат может иметь вершины с нецелыми координатами?

А смысл? Раскрашены ведь клетки, а клетки имеют целые координаты.

Да вдруг я не так условие понял, вот и уточняю

см. Это быстро доказать не выйдет. Краткое доказательство занимает 11 страниц текста :)

"Нутром чую, что литр, а доказать не могу"

Уууу учитывая понятно что найдется такой квадрат.

Понятно без доказательства?

Да, слишком много вариантов квадратов.

И почему же при большом количестве вариантов квадратов они не могут быть все удовлетворяющие условию?

Попой чувствую:)

Ответ "Нет"

Ответ да. Длина стороны - 4 клетки.

не вижу квадрата в 4 клетки

Возьми вертикальную сторону квадрата красного цвета в 4 клетки.

не вижу. ткни пальцем.

Возьми левую вертикальную сторону квадрата красного цвета в 4 клетки.

Ты уверен, что понял задание?

13*13 квадрат

Ой! Я дальтоник! :) Ага, и это не единственный случай.

Вот интересно тут доказательство "от противного" и матиндукцию можно совместить? Чтобы не 11 страниц было а поменьше )) Пусть и с кучей картинок ))

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

а если за шаг n+1 взять перестановку 2 цветов?

+ "от противного" же доказываем то нельзя сделать такую раскраску чтобы не было квадрата ))

Нет, я такое не осилю. Суть "от противного" получить логическое противоречие. Пока не могу связать перестановку с логическим противоречием.

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

Не катит. Если квадратов - несколько, то несколько - это конечное число. Для конечного числа "обязательность" не сработает. И ты всегда можешь привести пример такого несрабатывания.

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

можно, именно это и используется