Все целые числа раскрашены либо в черный, либо в белый цвет. Верно ли, что найдутся три числа A, B, C одного цвета, которые образуют арифметическую прогрессию, то есть C-B = B-A?

(0) Конечно верно.

найдутся три числа A, B, C одного цвета = любого цвета?

Черные 1,2,3 и белые 4,5,6?

(1) А доказательство?

а числав как раскрашены? закон раскрашивания есть?

(5) Нет закона. Незаконно раскрашены числа. )))

(5) произвольно

(4) Про доказательство ничего в (0) не сказано. Был вопрос про "верно". А что "найдутся" достаточно одного примера.

(8) Это твоя логика, ты в математику видимо случайно попал, не мешай другим.

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

бб.чббч.бб
Рядом с двумя б не может быть б -
чббччббччббч - думаю тут каждый увидит последовательность ииз трех ч.
(8) То есть? Тут недостаточно одного примера, тут нужно доказать что для любой последовательности найдутся.

(9) Сейчас буду наблюдать, как приведенные посты будут конкретизировать, уточнять, дополнять то, что же ты хотел в (0), но не сказал, хотел спросить, но не спросил, хотел узнать, но забыл сказать.
Коряво поставленный вопрос исключает применение математики.
Не так ли?

исходя из принципа дирихле

(10) "для любой последовательности найдутся" - сам придумал или (0) шепнул?!

(13) Тяжелый случай...
Именно это в ноль и написано.

(10) Блин, чуть не так.
Если у нас две б подряд, то по краям от них должны быть ч.
.бб.
чббч
Далее, у нас есть две ч, чтоб не было последовательностей одного цвета - доkжно быть
б..чббч..б
Теперь смотрим первую и вторую б, и также последнюю и предпоследнюю

бч.чббч.чб ->
бчбчб......

(9) Не ругай человека. Сам виноват. Слово "всегда" пропустил в условии.

(14) О! Еще один чтец между строк.
Этак жена или мама спросит есть ли 100 рублей и выслушает содержательный рассказ как ты в течении месяца тратил всю свою зп, причем со ссылкой на литературу метров математики.

(10)
Почему из б..чббч..б ты делаешь Бб.чБбч.Бб ?
Ты ведь тут уже получил прогрессию.

(15) а, во

(18) см (15)
Работа отвлекла, чуть ошибся.

Только ЕГЭ научит точно понимать вопрос!

(16) нафиг тут всегда?

(16) В условии ничего не пропущено.

(21) Смотри:
Верно ли, что, если числа раскрашены..., то найдутся ....
Для начальной школы здесь добавляют избыточное слово "всегда". Автор просто не рассчитывал на твой уровень.

(22) (23) Всегда, конечно, не обязательно.
Но звучит более доходчиво для любого уровня подготовки.

Верная формулировка звучит так: Для любой раскарски, существуют 3 числа, такие что ...

(0)
перебор всех возможных состояний
http://yadi.sk/d/jbgs4AEM5wLbK
является доказательством?
хватило 16 возможных состояний
исход из того что.
чередоваться цвета не могут, так как это явная прогрессия. три цвета подряд тожепрогрессия. Так что где-то найдется два числа подряд одного цвета. с них и начинается разбор. добавляя поочередно по одному цвету, исключая появившееся с прогрессией. И продолжая без таковой.
Всего 16 возможных вариантов развития событий.

(26) С тем же успехом можно спросить "Для определенной раскарски, существуют 3 числа, такие что ..."

Просто некоторые имеют склонности к математике, а у других ГСМ.

(28) ты наверно не знаком с языком епсилон дельта ))

(28) и твое утверждение совсем не тоже самое

(31) Не то же самое, но так же подходит под (0)

Обобщим:
Все целые числа раскрашены либо в черный, либо в белый цвет. Верно ли, что ЛЮБОГО натурального N найдутся  числа A1, ... AN одного цвета, которые образуют арифметическую прогрессию?

(33) Э... Доказательство на восьми страницах?

(34) ;-)

(33) При N=1 нифига у тебя не найдется

(32) В мат языке есть только кванторы "Для любого" и "Существует".
Других, типа "Для определенной" нету

(34) А чем твое (15) не подходит?

(33) Начитался вчера ))

(36) При N=1 - любое отдельное число и есть такая последовательность. Арифметическая прогрессия из одного элемента одного цвета.

(36) один слишком грустно, возьми N=4

(38) Мое только для N<=3

Док-во по индукции?

(37) Скудный какой язык )

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

(40) Так тогда получается, что в любом раскладе найдется прогрессия из одного элемента )

А, я условие неправильно понял

Кстати вчера на хабре интересная статья была про математику
http://habrahabr.ru/post/183374/?utm_source=twitterfeed&utm_medium=habrahabr&utm_campaign=twitter
Парадокс доказательства

(42) Ты начал доказательство с "чередоваться не могут"
Потом сразу вывод "значит будет последовательность из 2-х".
Ты пропустил: последовательности из 3-х быть не может.
Думаю если заменить 2 и 3 на N и N-1, то это и будет доказательство.

Верно для любого А=В=С

(49) В смысле? Я доказываю что всегда будет последовательность из трех.

Или так, пусть найти по прежнему надо 3 точки, но и цвета пусть будет 3.

(51) В смысле: последовательности из N подряд одинакового цвета быть не может.

(52) Мы еще предыдущую не решили....

(24) Ну вы, блин, даете! (Из фильма)
Третий чииитун между строк. Я вас всех пересчитаю!
А теперь глянь, что написано в (0) и в то, в чем ты убедил себя. Ты - юрист?!
:))
В начальной школе:
- Дети, придумайте вопрос к задаче и решите ее.

(55) Чтоб правильно понять условие не надо быть юристом. Достаточно хорошо понимать математику.
(54) Какую предыдущую не решили?

(53) Насколько я знаю, если я ничего не путаю - доказательство этого занимает восемь страниц.

(55) угомонись уже

"всегда чередоваться б и ч не могут" я вот это не понял. почему это не могут?

(59) потому что сразу получится арифм. прогрессия одного цвета

(60) ясно

(57) ТС вчера давал ссылку на статью - там страниц ~15, но там ещё более обобщенно

(62) я хочу доказательства "на пальцах"

(57) Кошмар какой!

(63) :))))))))

(63) я тоже хочу - но "не осилил"
Одна надежда на тебя, что осознал и покажешь "на пальцах"

(52)для трех цветов найдутся три числа одного цвета, дающие арифм. прогрессию:

1. Среди любых 4-х подрядидущих чисел есть два одного цвета. Пусть это цвет черный, а числа X1, X2. Пусть X3 = 2*X2-X1, тогда оно другого цвета, пусть белого. X3-X1<=6.

2. Среди наборов подрядидущих 7 чисел может оказаться не более чем 3^7 вариантов раскрасок (с учетом порядка). Поэтому если взять достаточно большой интервал (из 3^7+7 чисел), то там найдутся два одинаково окрашенных набора. То бишь:
Ч11-Ч12-Б13 ... Ч21-Ч22-Б23
где числа через черточку образуют прогрессию, цвет - буква, а троеточие - ну сколько-то там пропущено.
Выберем точку К33, так что Б13-Б23-К33 - прогрессия. Какого цвета К33? Белого не может быть, но и черного тоже: Ч11-Ч22-К33 - прогрессия. Итак К33 - красная. Можно посчитать насколько макс. может быть удалена К33 от Ч11. Пусть на М.
3. Тогда наборов из Х чисел можно покрасить 3^М вариантами. Ну и в каждом из них есть такая конструкция (только цвета меняются) но в конце концов найдутся и две и тут одинаковые. Пусть числа второй копии будут именовать также но с штрихом'.
Тогда выбрав Х так, что: К33-К'33-Х -прогрессия мы получим:
Ч11-Ч'22-Х - прогрессия, Б13-Б'23-Х - прогрессия. Ч.т.д.

+(67) аналогично доказывается для любого числа цветов, что найдутся три числа одного цвета в арифм. прогрессии.

+(67) пара замечаний:
1. получаются люто огромные числа.
2. графически нагляднее рассуждать.

(68) Это не интересно. Ты лучше докажи для двух цветов и любого N.

Теперь покажем, что для двух цветов найдется прогрессия из 4 одноцветных чисел.
Исходя из предыдущего у нас на достаточном большом куске встретится Ч-Ч-Ч-Б. Пусть это кусок длины М. Тогда его можно покрасить 2^М способами. Сделаем "альтернативную раскраску" чисел в 2^М цветов таким образом, что каждое число красится в цвет соответствующей исходной раскраске куска М с началом в этом числе. Так как для любого количества красок мы доказали что найдется прогрессия из 3 элементов, то вернувшись к нашей раскраски мы имеем:
... Ч-Ч-Ч-Б ... Ч-Ч-Ч-Б ... Ч-Ч-Ч-Б
Ну и возьмем такое Х, что Б-Б-Б-Х, тогда Х ни может быть не белым, ни черным.

аналогично по индукции для увеличения длины и количества цветов.

A, B и C - это буквы, а не числа. Глупости какие.

(71) я так понимаю, что расстояние между группами
... Ч-Ч-Ч-Б ... Ч-Ч-Ч-Б ... Ч-Ч-Ч-Б
должно быть одинаковым, а в рассуждениях этого не увидел

(73) читай внимательно, начала кажого из кусков в которых они лежат образуют прогрессию

(67) "Среди любых 4-х подрядидущих чисел есть два одного цвета" - это глупость. Нету!
Беру любые 4 подряд идущие и у меня получилось чбчб, беру опять и опять незадача.

Получилось бчбч.

А могу взять чччч и только или бббб. Любые не получится.

(74) всё равно в моей голове детали доказательства не укладываются
Понятно, что это доказуемо;
понятно, что работает принцип Дирихле: если взять достаточно большой кусок - обязательно что-нибудь повторится.
Интересна оценка длины минимального куска на котором найдется нужная подпоследовательность при заданном N и количестве цветов

(78) Мои числа раскашены чбчбчбчбчбч...чбчбч...
Что там повтроится и найдется?!
В условии не сказано о случайности раскраски.
Более того скажу, речь даже не идет о последовательных целых числах.

Мои целые числа А=1, В= 3, С=100.

(75) чбчб - 2 черных и 2 белых. чччч - 2 черных

(79) не случайная раскраска, а любая.
Если хочешь контрпример привести, то нужно найти такую раскраску, что нельзя найти чисел

(82) Я все привел. О любой раскраске речь не идет. Ты додумываешь.

(83) ты привел: Существует раскраска и существует 3ка чисел.
Ты вообще абстрактную математику не понимаешь

(83) ты боксом занимался наверно или в армии слишком долго служил

(84) Не спорь с ним. Он лучше автора знает, что он (автор) хотел сказать.

(84) Абстракция конкрентна, причем конкретна аксиоматично. А тут идет активное строительство "строгого" доказательства исходя из неопределенности исходных условий.

(87) где неопределенность в условии?

раз доказавыть никто не хочет, так хоть поспорить ))

(86) Я наоборот хочу сказать, что автор не знает чего хотел сказать. Или хотел сказать одно - получилось другое.

К примеру фраза - "Все целые числа раскрашены либо в черный, либо в белый цвет" я ярко воспринимаю 1 случай - все числа черные, 2 случай - все числа белые.

(91) вполне может быть. Что дальше

(91) Продолжай... ярко, понятно.
А контрастно ли?

(0) И все это ради того, чтоб вырезать нужный квадрат в решетке?

(92) Продолжаю. И чего ты тут "доказываешь"?!
:)

(92) Могу допустить, что ты додумался то третьего варианта?!
Да?!

(95) Для 1 случая верно и для 2го. А для 3го?

(97) Третьего нет. Иначе не будут все числа раскрашены в один цвет.

(98) ах вот ты к чему придрался

100

(99) Если это опустить еще есть притензии?

(99) Я не придирался. Я читал без додумывания.

(102) Да маленько автор тупанул, но потом вроде потом поправился, так что забей.

Интересно судя по заданию в (0) не ясно в какой цвет раскрашены дробные числа и упаси боже комплексные.

(103) Да я забил. Просто отвлекаюсь от 1С - спасибо автору!

Вот вариант "на пальцах" для двух цветов и N=3.
Разность между двумя числами одинакового цвета не может быть больше 3. Иначе мы сразу получаем прогрессию.
Запишем раскраску в виде последовательности х1,х2,х3...
Где х1-разность между первым и вторым числом одинакового цвета,
х2-между вторым и третьим и т.д.
Попробуем построить все возможные варианты этой последовательности.
Первое число может быть 1,2 или 3
1
2
3

Второе число не может быть равным первому.
12
13
21
23
31
32

Третье число не может быть равно второму, и не может быть равно сумме двух первых. Например, 1 2 3 не годится, потому что тогда получается прогрессия из 1,3 и 4 числа одинакового цвета.
Кроме того, сумма второго и третьего числа не может быть равна первому.
Итак, имеем:
1 2 1
1 3 1
1 3 2
2 1 2
2 3 1
2 3 2
3 1 2
3 1 3
3 2 3

Четвертое число не может быть равно третьему, не может быть равно сумме 2 и 3, сумма 3 и 4 не может быть равна 3, и сумма 1 и 2 не может быть равна сумме 3 и 4.
Такое число подобрать нельзя.
Не годятся:
1 2 1 1
1 2 1 2
1 2 1 3 и т.д.

Тьфу. Все проще:

Третье число не может быть равно второму, не может быть равно первому и не может быть равно сумме двух первых. Например, 1 2 3 не годится, потому что тогда получается прогрессия из 1,3 и 4 числа одинакового цвета.
Кроме того, сумма второго и третьего числа не может быть равна первому.
Итак, имеем:
1 3 2
2 3 1

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

Собственно все доказательство в одном, последнем абзаце поста (109)

(73)(78) Еще раз. Из предыдущего мы доказали, что для любого набора цветов есть довольно длинный (но заранее известной длины) кусок в котором есть прогрессия из 3 элементов. Возможно немного расширим этот кусок-шаблон, до того чтобы зафиксировать Ч-Ч-Ч-Б, где Ч одного цвета, Б - другого.
Теперь берем альтернативную мультираскраску. Например, если кусок из 3 чисел имел цвета в порядке следования: серый, бурый, малиновый, то для клетки "серый" альтернатива будет "серо-буро-малиновый", понятно что число цветов резко возрастет. Но нам важно, что и для них мы знаем некий шаблон в котором обязательно есть прогрессия длины 3, вот его и берем. А теперь возвращаемся к исходной раскраске, получаем:
(Ч-Ч-Ч-Б)-(Ч-Ч-Ч-Б)-(Ч-Ч-Ч-Б ) то есть прогрессия прогрессий как бы ну и далее берем точку, что Б-Б-Б-Х
Х ни белой, ни черной быть не может

(0) Это ж частный случай теоремы Ван дер Вардена

wiki:Теория_Рамсея#.D0.A2.D0.B5.D0.BE.D1.80.D0.B5.D0.BC.D0.B0_.D0.92.D0.B0.D0.BD-.D0.B4.D0.B5.D1.80-.D0.92.D0.B0.D1.80.D0.B4.D0.B5.D0.BD.D0.B0

Книжка такая есть. Хинчин "Три жемчужины теории чисел". Там эта теорема доказывается средствами элементарной математики (хотя доказательство далеко нетривиально).

(0)+(112) В общем теорема звучит так: Если множество натуральных чисел разбито на N классов любым способом, то по крайней мере в одном из классов найдется арифметическая прогрессия любой длины.

Вот, кстати сама книжка: http://ilib.mccme.ru/djvu/hinchin-3zhem.htm можешь попробовать ознакомиться с доказательством.

(112) ежкин котяра, так я ее и пытаюсь доказать, только доступным для 1С-ников путями в (67)(71)(111)

(114) "я ее и пытаюсь доказать, только доступным для 1С-ников путями" :) давай, как знать, может что и придумаешь. Настораживает только фраза "доступным для 1С-ников способом" :).

Я над этой задачей размышлял в свое время, вопрос интереснейший.

(114) Лукавишь. Твой способ - "на пальцах". А вот доступность его оценивать не берусь.
:)

(116) именно "на пальцах", тут важно скорее уловить идею, чем дотошно расписывать формулы

(11)+

(0) Автор, посоветуй чего почитать из популярного для тупого 1С-ка, для просвещения в области математики? Имеется потребность. По возможности то, что можно приобрести в бумажном виде.

(119) брошюрки библиотеки квант, в них по одной проблеме раскрывается средствами доступными для школьника

(120) где ж такое взять-то

(121) зайди в крупный книжный магазин

(119) Начни отсюда: http://heller.ru/blog/2013/05/math-plan/