Сибирская олимпиада

Ian · Сообщение **Ian** » 10 ноя 2019, 15:40

Одна из задач.
Доказать, что из 50 различных трехзначных чисел можно выбрать 4 различных a,b,c,d, что a+b=c+d

В лоб не катит, пар

C^2_{50}=1225 а суммы от 201 до 1997 могут быть

zykov · Сообщение **zykov** » 11 ноя 2019, 01:52

Пусть

упорядочены как $a<c<d<b$

.
Тогда

эквивалентно $b-c=d-a=r$

, при этом $1\leq r \leq 999-101=898$ .
(Аналогично, $c-a=b-d=r_1$

.)
Как уже замечено $C^2_{50}=1225>898$ .

Ian · Сообщение **Ian** » 11 ноя 2019, 11:28

Например разность r=2 у Вас встретилась дважды, 105-103=103-101 и что найдено? Ээ нет, природу не обманешь, надо учитывать что попарные суммы (да и разности) это какая-то квазирешетка а не произвольный набор.Не случайно это единственная, которая не решена тут https://dxdy.ru/topic137255-15.html

zykov · Сообщение **zykov** » 11 ноя 2019, 12:16

Да, есть тонкости.
Может найтись две пары $b,c$

и

, такие что $c=d$

.
Но предположим, что нет ни одной нормальной четверки (чтобы все четыре разные) - есть только тройки.
Количество троек всё равно должно быть минимум $1225-898=327$

. Т.к. чисел всего 50, то найдутся две разные тройки с одним и тем же центром - $x-d_1,x,x+d_1$

и

. Тогда две пары $x-d_1,x-d_2$

и

дают нормальную четверку.

Вроде других проблем не вижу.

Ian · Сообщение **Ian** » 11 ноя 2019, 15:16

Да, Вы на час опередили тот форум, там тоже так решили.
Но это видимо очень грубая оценка. Сколько я могу предъявить трехзначных чисел, что никакие две суммы не совпадают? Увы только 15. Это 100,101,102,104,107,112,...,709 расстояния между соседними равно последовательным числам Фибоначчи. Каждое некрайнее -является центром. Кроме этого случая совпадения сумм случиться не может.
50 и 15 дистанция огромна...
Впрочем сразу видно, что к этому набору можно добавить 2 числа 999 и 990.Если только одно из них участвует в равенстве a+b=c+d, то другая сумма должна быть больше 1090 , а это только 709+476=1185, но чисел 186 и 195 в исходном множестве нет. Если 999 и 990 участвуют в разных суммах, то 9 -это первая разность которой не может быть у исходных 15ти.
Ну 50 и 17

zykov · Сообщение **zykov** » 11 ноя 2019, 16:26

У меня "в лоб" получилось 27 (просто добавляя поочередно по одному, если можно - если даёт только новые суммы).
100,101,102,104,107,112,120,129,138,152,173,194,227,251,281,311,357,415,473,512,575,630,645,707,816,897,961

129 - это уже не Фибоначчи

Ian · Сообщение **Ian** » 11 ноя 2019, 18:21

У Вас формировался логический массив типа

b_{300}=1 если сумма 300 есть и нулю, если такой суммы нет? Если да, то может Вам несложно визуализировать, каков он стал в конце, в виде закрашенных клеток в прямоугольнике или типа того? Насколько много дырок и не прослеживается какая-то фрактальная структура в нем.
Опс, а у Вас точно посчитано? сравните http://oeis.org/A010672 там 151 вместо Ваших 252

zykov · Сообщение **zykov** » 11 ноя 2019, 19:13

Ian писал(а):Source of the post сравните http://oeis.org/A010672 там 151 вместо Ваших 252

У них от 0, у нас от 100.
Их 151 - это наши 251.

zykov · Сообщение **zykov** » 11 ноя 2019, 19:22

Ian писал(а):Source of the post Вам несложно визуализировать, каков он стал в конце

Код: Выбрать все

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1111111110111101001111010010111110010111110010001101110101100001001000011110100110001000010011110100
1100010000100100000000101011101101000010000001100011101101000010101000100000001111101001100010000001
1010000001111010011010110000001010000001000010001000010011101011000010000010110000010100000000100000
0000100110000011101001000010010100100100000100000010100000000100001000001110100100011001000110000000
0100000110111101001000011000000100000100110001000100000000000001011100000011101001001010000000110001
0001010000001000000000010110011101001010010011111101010010100010100110010100000001110000000010001000
0110001110100100011000110110010000010010000010000000000110100000000010010000000110000101000000010000
1000000000100001110100100111000101010000100010000000010101000000000100000000000000001011110000001110
1101000011000000110000000100000000100000001010011000000000011111101101001000000010000010011000001010
0010000000001000010001010010000001000000010000010000001010000000000000001000010100000001000000000000
0000100100010000001100000000001000000000010000000000010000000000000000010010000001000000100000000000
0000000000010000010000000001000000001000000000000001000000000000000001000001000000000000001000000000
0000000010000000000000000000000001000000000001000000000000001000000000011000000000000000000000000000
0000000000000000000000100010000000010000010000000000000000000000000000000000000000000000001000000000
0001010000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000
0000000000001000000000000000000000000000000000000000000000000000000000000000100000000000000000000000
0000000000000000000000000000000000000000000000000000000001

zykov · Сообщение **zykov** » 11 ноя 2019, 19:26

Погонял тут случайные перестановки. Всё равно не более 27.
Либо 28 можно получить маловероятной специальной комбинацией.
Или вообще 28 невозможно. Как бы такое доказать?

zykov · Сообщение **zykov** » 11 ноя 2019, 20:03

Используя мой метод можно доказать не только для 50, но и для 32.
Это учитывая, что $1\leq r_1 \leq 449$ .
Остается вопрос насчёт 28, 29, 30, 31...

Ian · Сообщение **Ian** » 12 ноя 2019, 08:38

Что-то типа самоподобия массива из признаков наличия сумм, что выдерживает гомотетию с целым коэффициентом относительно начала, должно наблюдаться. Задача же не меняется принципиально от того, какой длины мы заложим интервал.Лет 10 назад на прежнем форуме Pavlovsky искал как можно более разреженную последовательность, что любое натуральное число представляется как сумма двух чисел из нее, много первых членов просчитано,и точно такой в OEIS не нашли. Это как бы двойственный вопрос.

zykov · Сообщение **zykov** » 12 ноя 2019, 11:40

zykov писал(а):Source of the post Используя мой метод можно доказать не только для 50, но и для 32.
Это учитывая, что $1\leq r_1 \leq 449$ .

Это всё же не верно, т.к. в количестве выборок у нас все пары, а для $r_1$

не все.
Напрямую этот метод до 44 работает. А дальше, если только с какой-то модификацией.

Портал Естественных Наук, версия 1.1