PP wrote: Есть такое ощущение, что 0

Vladimirovich wrote: Похоже, задача была составлена под ответ. Целочисленных решений, очевидно, нет (сколько нечетных чисел может быть в этих суммах?). Но и не целочисленного, похоже тоже нет. Но это лень проверять

procrastinator wrote: Так что не светит нобелеффка академику.procrastinator wrote: Если конечное число цифр после запятой, то обобщить просто, а в противном случае условие не имеет смысла.

PP wrote: Я имел ввиду решение переопределенной системы линейных уравнений, где в правой части целочисленный 10-мерный вектор. Существует-ли такая правая часть допускающая решение и у которой все десять чисел заканчиваются на разные цифры?

Требуется решить следующую систему функциональных уравнений относительно функции *:

р + р* + рр* = 1, р** = р для любого 0 < р < 1.

Ее можно трактовать как вероятность события р, сопряженного события р* и совместного события рр*.

самоед-4 wrote:
Случайным образом такая функция есть и видимо только одна

*(p) = (1-p)/(1+p)

Да, это я тривиальность спросил. Достаточно даже одного 1-го уравнения. А вот интерпретация кажется более интересной...

Решил немного порешать классическую задачу о покрытии множества, поскольку она напрашивается. У меня есть множество точек, вдоль и поперек покрытое разнокалиберными интервалами, состоящими из этих точек. Точек 252, интервалов 455. Требуется выделить покрытие с минимальным числом интервалов.

Жадный алгоритм, который легко программируется, дает 12 интервалов. Поизвращался я и так и эдак, меньше никак не получается. Пишут еще про генетический алгоритм, но он как-то сложновато описывается...

Никак не соображу одну простую вещь (тут два юбилея подряд было)). Рассмотрим колоду карт и перетасуем ее следующим образом. Возьмем последнюю карту и переставим ее с любой предыдущей. Затем в образовавшейся колоде возьмем предпоследнюю карту и переставим ее с любой предыдущей. И так далее до начала колоды. Всё, один цикл перетасовки закончен. Спрашивается, всегда ли из любой колоды можно получить любую другую за некоторое число циклов?

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

самоед-4 wrote:
Надо пронумеровать карты в желаемом порядке.
Если ни одна карта не лежит на своем месте, то все вроде просто.
Надо запустить обратный процесс - 36ю положить на 36, 35ю на 35 и т.д.
Поскольку все абсолютно обратимо, можно на этой основе построить и укладку по исходным условиям.

Осталось показать, что мы можем добиться такого положения - ни одна на своем месте за отдельный прогон.
Но как говорил наш химик Бутлеров, остальное доделают немцы (с)

Если разрешить картам оставаться на месте, то все действительно просто. Но здесь не разрешается.

И даже если ни одна карта не лежит на своем месте, то все равно одного цикла может не хватить. Например, если вместо карт взять пять чисел: 3, 1, 2, 5, 4 --> 2, 5, 3, 4, 1.

самоед-4 wrote:
Ну так и сказано. Первый цикл для того, чтобы положить всех не на свое место. Потом указанная схема.
Никто на месте не остается.

Я не понял. Вот нужно перевести

перестановку 3, 1, 2, 5, 4 в перестановку 2, 5, 3, 4, 1.

Все цифры первой по сравнению со второй стоят не на своих местах. Переводим:

3, 4, 2, 5, 1;
3, 5, 2, 4, 1;
2, 5, 3, 4, 1;
5, 2, 3, 4, 1.

Не получилось: 2 и 5 оказались переставленными. Что делать дальше?

Да, тут больше сложностей, которые надо учесть

Вот, на компьютере нашел, какие перестановки можно получить из перестановки 3, 1, 2, 5, 4 за некоторое число циклов.

# 1: 5, 3, 1, 4, 2.
# 2: 1, 2, 4, 3, 5.
# 3: 2, 4, 5, 1, 3.
# 4: 3, 2, 1, 4, 5.
# 5: 5, 3, 2, 1, 4.
# 6: 4, 5, 3, 2, 1.
# 7: 1, 4, 2, 5, 3.
# 8: 4, 3, 5, 1, 2.
# 9: 5, 2, 3, 4, 1.
#10: 4, 3, 2, 5, 1.
#11: 3, 2, 5, 1, 4.
#12: 1, 4, 3, 2, 5.
#13: 5, 1, 4, 3, 2.
#14: 2, 3, 1, 5, 4.
#15: 3, 5, 4, 1, 2.
#16: 4, 2, 5, 3, 1.
#17: 3, 4, 2, 1, 5.
#18: 4, 1, 3, 5, 2.
#19: 4, 3, 1, 2, 5.
#20: 5, 4, 3, 1, 2.
#21: 1, 2, 5, 4, 3.
#22: 2, 5, 3, 1, 4.
#23: 2, 4, 3, 5, 1.
#24: 4, 1, 5, 2, 3.
#25: 3, 5, 1, 2, 4.
#26: 5, 1, 3, 2, 4.
#27: 2, 3, 5, 4, 1.
#28: 3, 1, 4, 2, 5.
#29: 2, 1, 5, 3, 4.
#30: 1, 3, 5, 2, 4.
#31: 3, 5, 2, 4, 1.
#32: 2, 1, 4, 5, 3.
#33: 1, 5, 3, 4, 2.
#34: 3, 1, 2, 5, 4.
#35: 5, 3, 4, 2, 1.
#36: 4, 2, 1, 5, 3.
#37: 5, 2, 1, 3, 4.
#38: 2, 1, 3, 4, 5.
#39: 4, 1, 2, 3, 5.
#40: 4, 5, 2, 1, 3.
#41: 3, 4, 1, 5, 2.
#42: 5, 2, 4, 1, 3.
#43: 4, 2, 3, 1, 5.
#44: 5, 4, 2, 3, 1.
#45: 1, 3, 4, 5, 2.
#46: 1, 5, 4, 2, 3.
#47: 5, 4, 1, 2, 3.
#48: 1, 5, 2, 3, 4.
#49: 5, 1, 2, 4, 3.
#50: 3, 4, 5, 2, 1.
#51: 2, 3, 4, 1, 5.
#52: 3, 2, 4, 5, 1.
#53: 1, 3, 2, 4, 5.
#54: 2, 5, 4, 3, 1.
#55: 2, 4, 1, 3, 5.
#56: 2, 5, 1, 4, 3.
#57: 3, 1, 5, 4, 2.
#58: 4, 5, 1, 3, 2.
#59: 1, 2, 3, 5, 4.
#60: 1, 4, 5, 3, 2.

Но желаемой перестановки 2, 5, 3, 4, 1 среди них нет.
Получается, не из всякой перестановки можно получить всякую. К моему сожалению.

Тут больше ограничений, как оказалось.
Надо все равно рассмотреть процесс ретроспективно

Допустим, мы хотим получить 1,2,3,4,5

Тогда последний цикл будет однозначным (в обратном порядке)
21345
31245
41235
51234

Предпоследний будет иметь больше вольностей, но тоже не много
Достигнет ли мощность группы перестановок 5!

Vladimirovich wrote: А нет. Туплю

Для проверки разрешил цифрам оставаться на месте. Проделал 1 млн экспериментов.
Один эксперимент - получить из указанной перестановки другую указанную: (3, 1, 2, 5, 4) --> (2, 5, 3, 4, 1).
В среднем на это уходит как раз 5! = 120 случайных циклов.
По ходу можно пройти любую из 5! = 120 возможных перестановок.
В среднем к исходной перестановке случилось вернуться 1 раз.

Ошибся насчет того, сколько раз была пройдена исходная перестановка. Сейчас исправлю. Расчет занимает 7 с небольшим минут.

Исправил.

Непонятно все-таки, почему в среднем нужно именно 120 циклов. Дисперсия при этом довольно большая: в одном эксперименте, например, потребовалось 2235 циклов.

самоед-4 wrote: Если я правильно понял задачу (в чем я начал сомневаться), то перестановка 5 и 36 чисел кардинально отличаются. При 36 числах, каждый цикл является нечетной перестановкой, а при 5 - четной, что сразу откидывает половину возможных исходов. Так что Ваш экперимент скорее оптимистичен, Вы получили все возможные 60 исходов.

procrastinator wrote:
А, вот в чем дело. Т.е. этим методом я смогу получить только половину возможных перестановок: либо одни четные, либо одни нечетные. Да, они будут случайными и даже практически равной частоты, но не всевозможными. Правильно?

Вообще-то, мне нужны просто случайные перестановки большого числа элементов, желательно все, конечно.

самоед-4 wrote: Ну так это совсем другое дело. Посмотрите Википедию и найдите одно отличие от алгоритма Кнута.

procrastinator wrote:
Это я знаю, что это не алгоритм Кнута, а алгоритм Фишера - Йетса. Только про него как-то так в Википедии написано (невнятно), что я понял, что вместо него вполне можно использовать алгоритм Саттоло, описанный там же. Но теперь вот выяснилось, что использовать можно, но не вполне.

А еще лучше использовать алгоритм Дурстенфельда, тоже там описанный. Он экономнее с точки зрения программирования.

самоед-4 wrote: Я, собственно, о другом. Алгоритм Кнута (или Фишера-Йетса) позволяет оставить число на месте, а ваш нет. Соответственно, проблема четности снимается.

Это не мой алгоритм, это алгоритм Саттоло, как я его понял. Только я-то думал, что это другой, но равноценный Кнуту (или даже лучше) алгоритм, а оказалось, что нет. Может, я и неправ, но такой вывод я сделал из нашего обсуждения, и у меня вроде как сложилось законченное, непротиворечивое понимание вопроса.

Мне кажется, они стебаются
www.popmech.ru/science/news-384312-smozh...ere-i-grossmeystere/
Мы предлагаем вам довольно сложную задачку, известную как задача о шулере и гроссмейстере.

В условиях задачи очевидно всегда будет ничья, потому действительно дальше играть бесполезно. Но было бесполезно и с самого начала