В клетках бесконечной решетки записаны целые числа. Верно ли, что для любого целого N>0 найдется квадрат, сумма чисел в клетках которого делится на N?

Решетка представляет собой бесконечный тетрадный лист "в клеточку".

+19 или 17/ 2 = 8,5

(17) это не математические рассуждения
(18) причина? не умение мыслить обобщенно?
(19) что это?

(16) ну, и если принять, что бесконечное поле, забитое случайным образом случайными числами, подразумевает бесконечное количество комбинаций различных чисел, то таки да - верно

(22) + с учётом (13) и (14)

(22) кто сказал, что случайными? да и случайные они такие случайные

(21) как что - кусок тетрадного листа

(25) я не понял, что твой пример вообще дает к решению?

(0) неверно.
с учетом того что ноль целое число. и ограничений на заполнение решетки у нас нет. заполняем ее нулями, профит.

(26) он имел в виду, что "Число делится" <> "Число делится без остатка"

(27) 0 делится на любое ненулевое число, как-бы

(28) ну это было бы смешно конечно

(29) упс, не в ту стоорну прочитал)

(0)Делиться наверно нацело? А то так то любое число делиться на все кроме нуля. Если сумма чисел в квадрате будет простым числом то

Если сумма чисел в квадрате будет простым числом то делиться будет только на простое число

(32) ну а я бы задавал бы задачу, если бы не нацело?
насчет простых чисел фигня, смотри в (11) контрпример, когда получаются составные числа

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

(35) не так ты понял условие, есть решетка с числами (кто-то ее уже заполнил)
и есть число N, нужно показать, что для этого числа найдется или не найдется нужного квадрата

(34) а вот уточняй условия!

(37) кто в теме и так понял, остальным накуа?

отрицанием будет - что существует N для которого сумма в любом квадрате не делится на N. вопрос что доказать проще )

(34) Смотри, сумма клеток в квадрате в любом случае будет натуральным числом. Если эта сумма будет простым числом например 7 то по условиям задачи тебе надо найти любой квадрат сумма которого кратна 7. По сути надо доказать что для любого числа cумма N^2 случайных чисел будет кратна 7. Или что среди бесконечного набора чисел найдется число 7 или кратные ему величины. По сути, при бесконечной выборке случайный чисел из натуральных встретить определенное число стремиться к 1

(40) про случайные там нет ни слова)) в том то и дело что квадрат должен быть неслучайно заполнен

(39) понятно, что найдется бесконечное количество чисел, для которых выполняется условие, но ведь это не значит что для любого N

(41)>>сумма чисел в клетках
не определено каких.   следовательно случайны

(43) в клетках квадрата, а следовательно свое уберите, странная логика
здесь математика, а не Привоз в Одессе

(44) в клетках квадрата находятся числа, не указана логика заполнения чисел в квадрате, какие там еще могу быть числа

(45) не указана и что? там могут быть целые числа

(36) Хотя можно доказать так. Заполним все поле простым  числом М. Тогда условие "для любого целого N>0" не будет выполнятся, поскольку сумма квадратов будет являтся рядом
М*n^2 где n натуральные числа от 1 до бесконечности(размерность клетки). Среди последовательности целое больше 0 мы найдем бесонечное множество чисел не входящи в последовательность чисел М*n^2

А если вся клетка заполнена в шахматном порядке числами 1 и -1 ?

(46) могут быть целые, могут быть не целые. Науке сие не извесно. По условиям задачи они заполнены, значит не null ;)

(47) а нам и не надо равенство, нам деление проверить, а M*n^2 всегда делится на n
(48) плохо будет, сумма квадрата 2*2 даст 0, а 0 делится на любое N
(49) выключай тупилку

+(48) Тут надо уточнить делится ли 0 на N.

(51) поверь, делится ))

(50) так, мы ищем чтобы для любого N был квадрат или чтобы было хотя бы они N для любого квадрата, это немного разные вещи

(53) нам дают заполненную решетку и число N

(54) да не дают же нам число N
у нас более сильное утверждение что для ЛЮБОГО N существует квадрат.

(55) не вижу разницы? дать могут ЛЮБОЕ число

Пример
1. Если есть 0 - от сумма в квадрате из одной ячейки = 0 делиться всегда
2. Если все заполнено еденицами.
1,4,9,16,25, ... n*n , ...  соответвенно лдя любого n  всегда есть квадрат n*n.
3. для заполненного одинаковыми числами  m решение сводиться к предыдущему в виде m*n*n.

(57) Хорошо, мы рассмотрели один вариант заполнения из бесконечности. Осталось еще ... бесконечность.

есть же некая закономерность распределения простых чисел в натуральном ряду. их концентрация уменьшается. может с этим как-то связано?

Кстати, думаю, для опровержения эту задачу можно чвести к другой.

Пусть существуют таблица Т из элементов t: 0<t<N и число N>0, такие что не существует квадрата на этой таблице, чтобы сумма его элементов делилась на N.

Может это проще будет доказать.

Давайте попытаемся решить частный случай, при N=2 все просто, рассмотрим N=3

Намного проще доказать что всегда будет делить на n не только на плоскости, но и в ряду чисел всегда найдется подпоследовательность для любого N

(61)
Вот и подсказал :)

(62) доказать нетрудно, но что это даст для данной задачи?

(64) это даст решение данной задачи, то есть выбирать можем не квадрат, а линию (квадрат размера 1xМ)

(61) при N=3 размещать надо 1 и 2. Т.е. можно считать, что всё заполнено единицами и некоторые заменены двойками. Сумма чисел в ячейках квадрата будет равна квадрату его размера плюс число двоек попавших в этот квадрат.

(65) квадрат - это M*M, а 1*M - не квадрат

(67) торможу, прочитал квадрат, а в голове прямоугольник.

(0) все заполняем в виде
12121212
21212121
12121212

для n=3 всего два варианта
121
212
121 сумма 13

или
212
121
212 сумма 14

на 3 не делится

(65) про последовательности очевидно, что остатки у двух подпоследовательностей совпадут и разность даст 0 по модулю, а вычитать квадраты не получается

(69) квадрат 2*2

(71) в условии для любого N

(72) N - это заданное число, а размер квадрата может быть любым

(73) дошло

+(66) задача сводится к возможности размещения двоек:
для любого квадрата стороной кратной 3 - число двоек было некратно 3;
а для квадрата не кратного 3 (L^2 mod 3 = 1) - число двоек не рано 2 по модулю 3

(69) и что?

1    2    1    2    1
2    2    2    2    2
1    2    1    2    1
2    2    2    2    2
1    2    1    2    1
вот таким образом заполненная таблица, ни когда не даст сумму для 3. опытным путем + интуиция. что-то с остатками, обоснавать немогу, но чувство такое. (принцип таблицы везде 2, 1 - в пересечении нечетных строк и нечетных столбцов)
и все пошел домой.

(77) продли табличку на 1 ряд - получишь общую сумму 9*7=63

Наоборот, любые закономерности и повторы приведут к делимости. Осталось доказать, что повторы будут. Это точно связано с тем, что получится совпадение в строках/квадратах или каких-то хитрых блоках, но что дальше делать с этими совпадениями пока непонятно)

Получается, что и от смущающей бесконечности можно уйти. нужно доказать, что для любого N найдется квадрат, заполненный числами т: 0< т < N, такой что один из квадратов подмножеств имеет сумму элементов кратную N. ИМХО, здесь уже стоит подключать комбинаторику.

(80) понятно, что для конкретного N, найдется конечное M, что для любого квадрата (размещения чисел) M*M найдется подквадрат суммой кратной N. Только если для N=2 M=2, то для N=3 уже M>9 (для 9*9 есть контрпример).
Чем тебе поможет комбинаторика, посчитать число "подквадратов"? Для M оно равно 1^2+2^2+..+M^2 ~ (M^3)/3

(81) показывай контрпример для 9*9

<< понятно, что для конкретного N, найдется конечное M, что для любого квадрата (размещения чисел) M*M найдется подквадрат суммой кратной N.>>
Мне вот не понятно... Это и нужно доказать.

Возьмеме решетку, заполним кажду клетку бесконечно большими числами. Тогда сумма любого взятого квадрата кроме квадрата со стороной 1*1 будет равна порядок бесконечности равным 2.
Теперь берем любое эн. Делится ли бесконечность на эн, да.
Берем в качестве эн бесконечно большое число, делиться ли бесконечносто второго порядка на бесконечность первого порядка, да.

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

(84) новое слово в математике? ))

Че это новое? Про порядок бесконечности оч хорошо на лимитах рассказывать

(82)  перепроверил - там ошибка

(87) только это в делимости не работает

(89) это че, в лимите делить низя? Вроде лимит и от инегралов, и от степеней берется

(90) у тебя каша в голове

(91)
я так понимаю можно заполнять таблицу не вообще числами а при конкретном N рассматривать заполнение числами от 0 до N-1. то есть остатками от деления.
для 3 - заполнение 0,1,2.
так ли?

(92) естественно, это классы вычетов

(93) Хоть бы говорил что у тебя есть хоть какаято система заполенния клеток

(0) Ну так как у нас бесконечное пространство, то в нем наверняка встретится число кратное N, которое есть "квадрат" со стороной 1 "сумма чисел в клетках которого делится на N".
Таким образом: Утверждение 1 - имеет смысл рассматривать систему заполнения пространства, которая настроена на "непоявление" квадрата, удовлетворяющего нашему условию. И далее, рассматривая эту систему, надо прийти к выводу, что это невозможно ;-)
В частности, предположим, что пространство заполнено числами k*N+m, где k - целое число, а m - некая константа меньшая чем N, в таком пространстве квадрат со стороной N будет делиться на N

(94) нету у меня никакой системы

(95) не несите бред, хорошо? вы тут в ветку с идей "наверняка встретится" не первый

(97) Я просто уточню, что если числа заполнены абсолютно случайным образом, то "наверняка встретиться" вполне адекватное утверждение, ведь вероятность появления числа, кратного N - 1/N, а чисел у нас бесконечность, так что (по теории вероятности) чисел таких будет 1/N*~ = ~

(98) никто не говорил как заполнены числа

(99) Ну и я про то же, просто рассматриваем различные варианты заполнения пространства. В частности, имеет смысл рассматривать пространство, заполненное числами от 1 до N-1, ведь любое заполнение, можно свести к этому, т.к. вместо каждого из чисел можно оставить лишь остаток от деления этого числа на N, на делимости суммы чисел на N это преобразование никак не скажется.

(99) Тогда смотри  (84) случай когда условие не выполнится. Тоесть существует по крайне мере 1 вариант когда существует решение. Если есть 1 решение то утверждение верное

(100) тогда как минимум от -N-1 до N-1

(101) зачем? не нулевых остатков от деления N-1

Никакого движения вперед ((
Какой максимальный контрпример для N=3, хотя бы 6*6 получилось у кого-нибудь?

(101) Тебе уже написали, что добавив еще один ряд к твоему квадрату ,получишь нужный. А так как у нас таблица бесконечная, то это не является контр-примером.

Стоп, а разве квадрат нельзя привести к одномерному ряду? Пусть квадрат представляет из себя ряд, состоящий из чисел сумм его строк или столбцов. Тогда мы уже ищем подпоследовательность бесконечного ряда, как раз то, о чем говорил NS в (62).

(105) зачем еще чтото добавлять если мы уже нашли квадрат удовлетовряющий условиям?

(107) ну как бы в строке может быть любое число слагаемых, в квадрате только степени двойки
В строке ты можешь сложить 6, 7 чисел. В квадрате только 4 или 9 чисел.

(107) А, я перепутал с другим сообщением. В (84) вообще бред.

(108) "в квадрате только степени двойки"
Что?

(106) нельзя привести

(111) почему нет?

(112) Потому что отрезки можно складывать, а складывая 2 квадрата получишь не квадрат.

Если в эту сторону копать?

Введем на решетке прямоугольную систему координат с центром в некоторой ячейке и осями параллельными осям решетки.
Для ячейки с координатами (i,j) i,j>=0 вычислим b[i,j] = sum(a[s,t], s=0..i, t=0..j), где a[s,t] – значение в ячейке с координатами (s,t). Наконец «покрасим» ячейку (i,j) в один из N цветов, соответствующий остатку от деления b[i,j] на N.
Если мы найдем 4 ячейки одного цвета в углах некоторого квадрата, то задача решена. Действительно, пусть b[x,y], b[x+m,y], b[x,y+m], b[x+m,y+m] имеют одинаковые остатки от деления на N (один цвет раскраски),  тогда
sum(a[s,t], s=x+1 .. x+m, t=y+1 .. y+m) = b[x+m,y+m]- b[x+m,y] - b[x,y+m] + b[x,y] делится на N.

(114)  утверждение, что найдется квадрат с одноцветными вершинами более сильное, чем b[x
+m,y+m]- b[x+m,y] - b[x,y+m] + b[x,y] =0(mod N). Вряд ли это проще доказать.
А идея с суммированием хороша

"Плоскость раскрашена в n цветов. Доказать, что существует квадрат с вершинами одного цвета.
Эта на первый взгляд обычная олимпиадная задача на тему "Раскраски" неожиданно оказывается очень непростой — попытайтесь ее решить и убедитесь в этом сами."

http://www.mccme.ru/dubna/2005/courses/bugaenko.html

(116) раскопал ))

(116) читаю http://www.mccme.ru/free-books/dubna/bugaenko.pdf

(118) больше 10 страниц - сейчас я да же прочитать такое не осилю, не то что осознать ))
я ожидал от NS, что он придет и скажет:
- типа это одна из открытых задач математики...
или
- задача для 7-го класса,
а он про квадараты 1*M ))