Взяли шесть натуральных чисел и для каждых двух записали их сумму. Могло ли оказаться, что все 15 получившихся сумм оканчиваются разными цифрами в 15-ричной записи (другими словами, дают попарно различные остатки при делении на 15)?

задан 12 Июн '17 15:39

1

Написал небольшую программу в Maple для перебора всех вариантов (их всего 5005). Оказалось, что 15 остатков не получить, и даже 14 не получить, а 13 можно очень многими способами. Теперь надо придумать "ручное" доказательство -- думаю, оно точно есть.

(12 Июн '17 18:51) falcao

@falcao, пока большое спасибо и на этом.

(13 Июн '17 15:45) Аллочка Шакед
10|600 символов нужно символов осталось
4

Предложу такую геометрическую переформулировку, которая представляет отдельный интерес.

Будем рассматривать все числа по модулю 15, и расположим их на окружности в вершинах правильного 15-угольника. Шесть точек разбивают окружность на 6 дуг. Проведём все 15 попарных соединений. Условие задачи (в своём отрицательном варианте) равносильно тому, что среди 15 хорд найдутся по крайней мере две параллельные хорды, не имеющие общих точек. Это легко проверить в обе стороны, но нас в первую очередь интересует доказательство в одну из сторон.

В самом деле, параллельные хорды стягивают дуги равной длины. Если эти дуги не пересекаются, то в наборе имеются числа a, a+d, b, b+d, где d -- (комбинаторная) длина дуги. При этом сумма двух крайних будет равна сумме двух средних по модулю 15. Обратное также легко проверяется: если есть 4 числа a, b, c, d, для которых a+b=c+d mod 15, то полусуммы (a+b)/2 и (c+d)/2 по модулю 15 также равны, где под 1/2 понимается число, обратное 2 по модулю 15, то есть 8. В итоге получается совпадение середин двух дуг, откуда следует параллельность хорд.

Таким образом, возникает такая чисто геометрическая задача: рассматривается 6-угольник, вершины которого выбираются среди вершин правильного 15-угольника, и требуется доказать, что в этот 6-угольник обязательно вписан некоторый 4-угольник с двумя параллельными сторонами (то есть равнобочная трапеция или прямоугольник).

Среди шести дуг, на которые 6 точек разбивают окружность, обязательно найдутся дуги равной длины, так как сумма 6 попарно различных натуральных чисел не меньше 21. Если дуги равной длины не пересекаются, то всё доказано. Поэтому далее можно считать, что дуги равной длины имеют общую вершину. Это касается не только 6 изначальных дуг, но и любых дуг, которые могут быть составлены из нескольких последовательных. Например, если где-то идут рядом две дуги длиной a, а в другом месте имеется дуга длиной 2a, не пересекающаяся с предыдущими дугами, то всё также доказано.

Отметим, что наличие трёх дуг равной длины также сразу ведёт к решению (за исключением "объединённых" дуг длиной 5+5+5.

Теперь начинаем рассматривать случаи. Пусть у нас повторились дуги длиной 1. Тогда они будут соседними, и их только две. Остальные 4 дуги в сумме дают 13. Среди их длин опять имеются совпадения, так как 2+3+4+5 > 13. Допустим, что совпали значения 2 и 2. Тогда они тоже идут подряд, и мы получаем непересекающийся случай "дуги" 1+1 и дуги 2. Ясно также, что хотя бы одна дуга длиной 2 должна быть -- в противном случае 4 числа, каждое из которых >=3, в сумме дают 13, и одно из чисел повторится трижды. Получается, что три дуги должны идти в порядке 1, 1, 2 в одном из направлений. Далее сумма длин трёх дуг равна 11, где ни 1, ни 2 не встречается. Тогда длины равны 3, 3, 5 или 3, 4, 4. Длина 3 точно есть, и она идёт после 1+2, чтобы были пересечения. Итого имеем 1, 1, 2, 3. Очевидно, что вариант с 3 и 5 даёт две хорды одинаковой длины. Остаётся 1, 1, 2, 3, 4, 4. А здесь есть совпадения длин дуг 1+1+2 с предпоследней дугой длины 4.

Аналогично анализируются оставшиеся случаи. Они, по сути, даже проще, так как если совпали длины дуг, скажем, 2 и 2, то на оставшиеся дуги приходится меньшая длина и меньшее число случаев. Наличие дуг 2+2 (идущих подряд) даёт на остальное сумму 11, и тогда там должна быть дуга длины 1 (помним, что тройных повторов длин нет). Три дуги с суммой 10 означают длины 3, 3, 4. При этом 4 примыкает к 2 и 2 (иначе есть совпадение 2+2=4). Получается 2, 2, 4, и далее идут 3, 3, чтобы не было совпадения 2+4=3+3 для дизъюнктных дуг. Значит, за ними идёт 1, и тогда получается 1+2=3.

Фактически, этим всё рассмотрено, так как если 1 и 2 встречаются не более чем однажды, то на 4 дуги в сумме приходится >=12, а это даёт 4 одинаковых длины.

Заметим ещё, что если бы конфигурация без параллельных хорд существовала, это давало бы пример вписанного 6-угольника, в котором каждая из 15 хорд параллельна ровно одной из сторон правильного 15-угольника, то есть все направления были бы ровно по разу задействованы. А задача весьма симпатичная получилась.

ссылка

отвечен 13 Июн '17 23:46

1

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

(14 Июн '17 1:15) Urt
1

@Urt: у меня эта идея возникла не сразу, но вчера вечером я даже начал набирать текст. Потом отложил, так как возник перебор, а мне хотелось чего-то более ясного. Сегодня я сначала хотел написать схему, но потом увидел, что всё перебирается до конца.

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

(14 Июн '17 1:19) falcao

@falcao, большое спасибо и +200 Вам очков за оригинальное решение!

(15 Июн '17 12:20) Аллочка Шакед
10|600 символов нужно символов осталось
6

Пусть $% N=\{n_1, \dots, n_6\} $% – подходящий набор чисел. Для любого целого числа $%a$% и $% c \equiv 2, 4, 7, 8, 11, 13,14 \mod 15 $% наборы $% a+N = \{a+n_1, \dots, a+n_6\} $% и $% cN= \{cn_1, \dots, cn_6 \}$%, также будут подходящими. С учетом этого будем считать, что одно из чисел набора равно нулю: $%N=\{0, n_2, \dots, n_6\}$%.

Нетрудно установить, что любой подходящий набор (мультимножество) содержит одинаковое количество чисел, соизмеримых по модулю 3, т. е. $% N \equiv \{0,0,1,1,2,2\} \mod 3 $%. Ясно также, что по модулю 5 в подходящем наборе одно из чисел будет соизмеримо с некоторым другим (только одним) числом, а остальные 4 числа будут несоизмеримы ни с одним другим числом из набора. Если $% n_i \equiv n_j \mod 5 $% , то $%N-n_i$% - подходящий набор, содержащий 0, для которого $%N-n_i \equiv \{0,0,1,2,3,4\} \mod 5 $%.

Числа в наборе будем задавать двумерным вектором, компоненты которого равны остаткам от деления данного числа на 3 и 5 соответственно. Учитывая, что набор N содержит единственное число $%(0,0)=0,$% для задания подходящего набора теперь достаточно подходящим образом разместить числа 0, 1, 2, 3, 4 в нижней строке матрицы

$%M_N=\matrix(^{\ 0\ 0\ 1\ 1\ 2\ 2}_{\ 0\ x\ x\ x\ x\ x}) $%.

При этом мы можем поставить 0 в третий столбец. Действительно если он находится в 4-м столбце, то изменим нумерацию соответствующих чисел, если же в 5-м или 6-м, то предварительно умножим числа набора на 11. В результате преобразований получим матрицу подходящего набора в виде

$%M_N=\matrix(^{\ 0\ 0\ 1\ 1\ 2\ 2}_{\ 0\ x\ 0\ x\ x\ x}) $%. Далее умножением чисел набора на 4, 7 или 13 можно привести матрицу $%M_N$% к виду

$%M_N=\matrix(^{\ 0\ 0\ 1\ 1\ 2\ 2}_{\ 0\ 1\ 0\ x\ x\ x}) $%.

В результате осталось проверить 3 варианта:

$%M^1_N={\matrix(^{\ 0\ 0\ 1\ 1\ 2\ 2}_{\ 0\ 1\ 0\ 2\ 3\ 4})} $%,

$%M^2_N={\matrix(^{\ 0\ 0\ 1\ 1\ 2\ 2}_{\ 0\ 1\ 0\ 3\ 2\ 4})} $%,

$%M^3_N={\matrix(^{\ 0\ 0\ 1\ 1\ 2\ 2}_{\ 0\ 1\ 0\ 4\ 2\ 3})} $%,

которые оказываются непригодными, а именно в $%M^1_N: n_1+ n_2= n_4+ n_6, n_1+n_4=n_5+n_6; $% в $%M^2_N: n_2+ n_3= n_5+ n_6, n_2+n_5=n_3+n_4; $% в $%M^3_N: n_1+ n_2= n_4+ n_5, n_1+n_3=n_5+n_6$%.

Как видно, попарные суммы из набора шести чисел не могут образовать более 13 несоизмеримых по модулю 15 чисел.

ссылка

отвечен 13 Июн '17 16:28

изменен 13 Июн '17 18:40

1

@Urt: я поначалу шёл примерно по тому же пути, рассматривая остатки от деления на 3 и 5. Но потом мне пришла в голову интересная геометрическая интерпретация. Там не обходилось без какого-то перебора (пусть и не слишком сложного), но в таком виде я записывать это дело не стал. Думаю, что сама переформулировка представляет интерес, поэтому я коротко изложу общую идею.

(13 Июн '17 23:07) falcao

@Urt, большое спасибо!

(15 Июн '17 12:19) Аллочка Шакед
10|600 символов нужно символов осталось
4

Решение Ильи Богданова

  1. Рассмотрим 30 попарных разностей шести исходных чисел по mod 15. Они принимают значения от 1 до 14, поэтому среди них есть три совпадающих. Если среди трех совпадений найдутся две непересекающихся пары $%b-a=d-c$%, то сразу получаем совпадение двух разных попарных сумм $%b+c=a+d$%, то есть противоречие.

  2. Значит, непересекающихся пар нет, но тогда три совпадения это $%b-a=c-b=a-c$%, то есть три числа $%a,b,c$% находятся в вершинах правильного треугольника, - совпадают по модулю 5. Тогда три попарные суммы $%a+b,b+c,c+a$% целиком покрывают один остаток по mod 5, три попарные суммы $%d+a,d+b,d+c$% целиком покрывают другой остаток по mod 5, три попарных суммы $%e+a,e+b,e+c$% покрывают третий остаток, а $%f+a,f+b,f+c$% - четвёртый. Непокрытыми остались только три значения с пятым остатком по mod 5, и покрыть их должны попарные суммы $%d+e, d+f, e+f$%.

  3. Но тогда получается, что остатки у чисел $%d,e,f$% по mod 5 совпадают, а это сразу приводит к противоречию с различностью остатков, которые мы перечисляли в п.2.

Противоречие. Следовательно, 15 различных остатков по mod 15 не бывает.

ссылка

отвечен 16 Июн '17 22:47

1

@Аллочка Шакед - не пропустите

(16 Июн '17 22:48) knop
1

@knop: а для других случаев, когда берутся n чисел по модулю n(n-1)/2, этот вопрос изучен?

(16 Июн '17 23:06) falcao
1

@falcao возможно. Но не мной, и мне неизвестен результат. ;-) Для трех и четырех чисел есть примеры, для пяти - легкое противоречие по чётности (потому что если k четных и 5-k нечетных, то нечетных попарных сумм будет k(5-k), и это точно не равно 5). Вот шесть чисел были наименьшим нетривиальным случаем.

(16 Июн '17 23:25) knop
1

@knop: да, для меньших значений всё понятно, а уже для 7 чисел я не проверял. Мне было интересно, делал кто-то эти вещи уже, или нет. Хорошо было бы найти какие-то общие закономерности, чтобы избежать перебора. Кстати, если есть правильный треугольник, то дальше совсем просто доказать наличие хорд равной длины чисто геометрически.

(16 Июн '17 23:30) falcao
1

@falcao, ну так первый шаг для 7 делается совершенно аналогично. Там 42 разности должны уложиться в 20 значений. Поэтому правильный треугольник есть и там. То есть по модулю 7 оказываются полностью забиты 1+4=5 остатков. Попарные суммы в оставшейся четверке полностью должны забить два последних остатка, при этом там совпадающих остатков ни у каких двух чисел уже быть не должно. А так не бывает. Так что и для 7 все быстро делается.

(16 Июн '17 23:37) knop

@knop, большое спасибо Вам и товарищу Богданову!

(16 Июн '17 23:48) Аллочка Шакед
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,399
×1,114
×370
×211
×46

задан
12 Июн '17 15:39

показан
1106 раз

обновлен
16 Июн '17 23:48

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru