Математическое и загадочное

[Рогожников Евгений]

Ответ писать пока не буду. 

[Рогожников Евгений]

никто не отписался. ответ 10. то что подходит, легко проверить. То что нет большего числа следует из того, что пусть есть число N.  числа 3, 5, 7 простые.

Значит N-3, N-5, N-7 тоже простые. Но среди них есть то, что делится на 3. Значит, должна быть 3

[E.K.]

Точно так. Если N=n(mod 3), то:

 

N-3 = n(mod 3)

N-5 = n+1(mod 3)

N-7 = n+2(mod 3)

 

Одно из них простое и делится на три, т.е. равно трём. То есть, N-7=3 => N=10.

[E.K.]

Что-то я затупил и не могу решить задачку...

 

Вот есть... неважно чего, но куча. Пусть, например, конфет. Много, но всего 255 разных типов конфет. И мы начали выкладывать их в ряд. В очень длинный ряд. Какое минимальное количество конфет нам нужно, чтобы получить все возможные пары видов конфет? Например, если у нас всего три вида конфет, то нужно четыре конфеты - 1231. А если четыре вида, то восемь: 12342413.

 

UPD: А сколько потребуется для 256 типов конфет?

 

Для простого p всё очевидно, а вот для 255 меня как-то срубило..

[E.K.]

Что-то все притихли... Но у меня тоже не очень получается. Попробую решить задачку немного в другой формулировке: "нужно прочертить все рёбра связного графа не отрывая ручку от бумаги". В данной формулировке конфеты - это вершины графа, а пары конфет - рёбра.

Для простого p всё просто. Сначала рисуем рёбра между всеми соседними вершинами - это p рёбер.

Потом строим рёбра через одну вершину:

Поскольку p - простое, то оно взаимопросто с двойкой (да и со всеми остальными). То есть, шагая "через вершину" мы за p шагов пройдём все вершины и вернёмся в исходную.

 

Дальше "шагаем через две вершины" - и так далее до (p-1)/2. Поскольку шагать через (p+1)/2 и через большие числа вершин уже не надо - там уже всё нарисовано.

 

Итого, для простого p результат: нужно p*(p-1)/2 конфет и ещё одна (первая) конфета.

 

p*(p-1)/2 + 1

 

А вот для составных требуется проходить рёбра повторно. Но сколько раз - непонятно.

[Рогожников Евгений]

Если у  нас N нечетно, то вышеприведенное решение легко обобщить. Только сначала надо рисовать рёбра не в соседние вершины, а устроить цикл по делителям числа N. На каждом шаге надо идти с шагом в d. Ясно, что мы вернёмся в исходную вершину.  Тут важно, что 2d != N. Далее продолжаем цикл с новым делителем. Как только все делители будут исчерпаны, то перейдем в соседнюю вершину. Там повторим цикл по делителям и пойдём в новую соседнюю вершину. Только тут может быть ситуация, что мы в этой вершине уже побывали, когда шли с неким делителем из предыдущей вершины. Такие делители надо исключить. В итоге вернёмся в самую первую. Теперь пойдём с минимальным шагом q оттуда. Здесь уже q взаимно просто с N. В итоге вернёмся через N шагов в исходную вершину, обойдя все прочие. Таким образом, стартуя с некой вершины, мы в неё вернёмся, обойдя все рёбра по одному разу. Ну а всего рёбер у нас N*(N-1) /2.  Т. е конфет на одну больше. 

 

Для чётного случая 2N ответ скорее всего будет  2N*N. То что меньше нельзя, следует из того, что в цепочке конфет каждое число должно встретиться не менее    N раз. Ведь каждое вхождение даёт не более двух соседей, а у каждого числа соседями должны быть все числа. Надо подумать, как модифицировать алгоритм выше к данному случаю. У нас, получается, есть возможность повторно пройтись по N рёбрам. Т. е по половине от 2N

[Рогожников Евгений]

Для чётного числа 2N с утра также добил. Напомню, что там у нас в запасе есть N ходов для хождения повторно по уже пройденным рёбрам. И тогда мы можем модифицировать наш алгоритм и для этого случая. Там были проблемы с хождением с шагом длины N, ведь мы не могли вернуться в прежнюю вершину не пройдя по ребру повторно. Т. е мы идём из ребра, например, 1 в ребро (N+1) симметричное ему, а обратно возвращаемся по тому же ребру. Но теперь идём повторно. Таким образом, алгоритм у нас опять сходится. При этом будет N  повторных ходов. Так что мы опять пройдёт по каждому ребру по разу кроме рёбер, соединяющим симметричные вершины. По ним 2 раза. 

[Рогожников Евгений]

В предыдущем сообщении для решения для чётных есть ошибка. Ранее мы доказали, что для 2N нам нужно не менее 2N*N вершин. А в приведённом алгоритме мы прошлись по 2N*N рёбрам. Т. е вершин будет на 1 больше. Например, для 4 видно что алгоритм даст длину 9, тогда как мы нашли решение для 8.

Выход из ситуации тут прост. По одному из симметричных рёбер надо пройти только один раз.   Можно сделать это для ребра 1 -(N+1). Когда мы перейдем по этому ребру, то не делаем возврат в 1, а продолжаем алгоритм из вершины (N+1). В итоге, всё остальное останется тем же самым. Только мы сделаем ровно на один ход меньше и закончим алгоритм в другой вершине, а не в той где его начали

 

.

[E.K.]

14 hours ago, Рогожников Евгений said:

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

...

В итоге вернёмся в самую первую.

Если N= произведение простых без степеней, то да. Если есть степени, то вернёмся в вершину номер X="сумма всех делителей, степени которых отличаются от 1 плюс 1".

 

То есть, завершающий цикл по соседним пройдём за N-X шагов.

 

Вроде так...

 

То есть, для 255 типов конфет ответ будет: 32386 конфет.

[Рогожников Евгений]

Нет. Я имел ввиду, что в соседнюю вершину идём, делая шаг длины 1. И делаем его в конце, когда прочие шаги уже были пройдены в цикле. 

 

Там много писанины. Сейчас сложилось, вроде бы более простое описание. Пусть мы находимся в некой вершине  М.начинаем теперь из неё путь,  делая шаги длины d. Т. е переходим в М+ d, M+2d и так далее. Так как вершин конечно, то скоро попадем в вершину где были. Легко видеть, что первой такой вершиной будет сама М. Назовём этот путь орбитой М((d). Ясно, что все замкнутые пути в графе распадаются на непересекающиеся орбиты. 

 

Тогда алгоритм такой. Пусть мы изначально в первой вершине. Двигаемся по орбите 1(2). В конце мы опять в точке 1. Далее идём по орбите 1(3) и так далее. До самой последней 1(N-1). Далее идём в соседнюю вершину 2. Т. е делаем шаг длины 1. Там мы повторяем цикл. Т. е идём в начале по орбите 2(2), 2(3) и так далее. Если по какой-то орбите проходили, то повторно по ней не идём. 

 

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

 

[E.K.]

А вот ещё о связных графах:

 

При каких условиях существует путь в связном графе, который проходит через каждое ребро ровно один раз?

 

Т.е. задача - начертить граф, не отрывая карандаша от бумаги и не проходя два раза через одно и то же ребро. Какое необходимое и достаточно условие этого события?

[santax]

Из детства всплывает сразу же цитата: у такого графа не должно быть больше двух вершин с нечетным числом лучей, исходящим из них. Оно?

[E.K.]

Оно. Интересное у вас было детство. В моём детстве такого не было... 😕

[santax]

С математическими олимпиадами) правда дальше школы это не ушло.. универ, айти, сисадминство 😃

[E.K.]

Так... Давненько не было. Вот вам:  Является ли число 12345678926 квадратом?