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

да

(0) [:||||||||:]

(1) http://s00.yaplakal.com/pics/pics_original/1/0/7/1775701.jpg

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

Числа в клетках

(5) да

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

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

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

(9) Злой ты.

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

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

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

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

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

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

*было

(0)Нет

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

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

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

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

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

С огромным трудом научным миром в свое время была доказана намного более простая теорема.

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

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

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

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

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

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

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

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

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

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

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

Ответ "Нет"
http://s018.radikal.ru/i517/1408/7a/53b2dfa786d9.jpg

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

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

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

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

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

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

(35) 13*13 квадрат

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

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

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

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

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

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

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

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

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

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

(35) http://savepic.ru/5487292.jpg