Ну и в догонку - попытка решения задачи при Max= 64:
Что изменилось по сравнению с Max=60?
А добавились две возможные суммы 35 и 37. А в них появились новые произведения 66 и 70.
Поэтому можно удалить повторяющиеся произведения для суммы 17 (вот эти 66 и 77).
В результате для суммы 17 остается единственное произведение 52. А это позволяет второму мудрецу однозначно определить пару чисел 4, 13. И поэтому задача имеет единственное правильное решение.
Саша, вот смотри.
Я султан. Загадал два числа 4 и 13.
Сказал: каждое число меньше 60.
Первому: произведение 52.
Второму: сумма 17.
Почему они не могут найти?
Ответ есть; 4 и 13 даже при Max<30.
Султану пофиг, как они решали.
Может с этим ограничением Max/2 ребенка выплеснули?
Jak, Я в предыдущем посту подробно все рассписал.
Султану может и похер как они решали, но они не смогут решить его задачу при Max=60.
Конкретно в этом примере - для второго мудреца который знает сумму в 17 есть три возможных пары чисел:
4, 13 - произведение 52
6, 11 - произведение 66
7, 10 - произведение 70
В этот момент он не может однозначно определить какая пара чисел (одна из этих трех).
Он не может сказать 4-ю реплику "теперь и я знаю".
Поэтому в условиях задачи 4-я реплика будет другая - это уже не наша задача.
И мы вместе с мудрецами не можем найти однозначный ответ.
Jak, Вгляни на задачу с другой стороны.
Султан мог загадать любые два числа. Но на каждую пару чисел мудрецы бы отвечали по разному.
Но чтобы у них вышел такой диалог, как в условиях задачи, то эта пара чисел должна быть только 4, 13.
Причем султан должен задать число Max в пределах больше 63 (иначе нет решения) и меньше 867 (иначе есть два решения).
Во всех остальных случаях диалог двух мудрецов будет другой (имеется ввиду другие пары чисел).
А откуда у тебя тут появилось "27"? Оно же не простое. 😲
И для 17 ты не можешь исключить 72.
интересна тема лютого пампа токенов. Сколько это стоит команде (маркет мейкеру) разогнать токен на тысячи процентов?
До каких значений они могут разгонять этот токен?
из отыгранных идей это токены Myx, River, MMT
сейчас из активного это токен Rave
Для бирж я как понял это вообще золотая жила (огромные обьемы торгов, комиссии, фандосы, ликвидации) и они могут скрыто спонсировать этот движ.
Jak, Задачка слишком сложная, чтобы решить ее или даже просто понять алгоритм решения, каким-то поверхностным взлядом. Я бы сам ее не решил без компьютерного перебора. Но если ты действительно хочешь разобраться в алгоритме решения, то нужно затратить какое-то время на разборы. Я уже несколько раз ссылался на алгоритм решения - там есть все ответы на твои вопросы. Но мне кажется ты даже не читал этот алгоритм и мне приходится дублировать это.
Еще раз вот алгоритм:
Алгоритм решения.
Задача о двух мудрецах уже много лет всплывает на различных форумах и постоянно возобновляет к себе интерес. Готовой компьютерной программы, позволяющей решать такие задачи при любом заданном максимальном числе, обнаружить не удалось. Поэтому я решил сам написать подобную программу.
Алгоритм решения буду описывать на примере классической задачи для максимального числа равного 100.
1. Я не знаю этих чисел, сказал мудрец, знающий произведение двух чисел.
Отсюда вытекает, что это произведение, не может быть однозначно представлено в виде произведения двух чисел. Есть как минимум несколько способов, как можно получить это произведение с другими парами чисел, причем эти числа должны удовлетворять условию, что они оба меньше 100. Произведение, которое можно представить только одним способом, будем в дальнейшем называть уникальным.
С этого высказывания можно сделать вывод о некоторых свойствах этих чисел. Во-первых, они не могут оба быть одновременно простыми, иначе их произведение уникально и представляется только в виде произведения этих двух простых чисел. Это условие является необходимым, но не достаточным условием уникальности произведения. В дальнейшем мы обнаружим другие уникальные произведения, которые не являются произведением двух простых чисел.
2. Я это знал, сказал мудрец, знающий сумму двух чисел.
Сумму двух чисел S, можно представить парой чисел различными способами: 2 + (S - 2), 3 + (S - 3) и т.д.
Это высказывание говорит нам, что ни одна из этих пар чисел, при умножении друг на друга не дает уникальное произведение. Попробуем определить какие суммы двух чисел имеют такие свойства, т.е. составим список возможных кандидатов для сумм двух чисел.
Во-первых, как мы уже показали, два числа не могут быть оба простыми, поэтому их сумма не может быть суммой двух простых чисел. Итак, компьютерная программа, сначала вычисляет список всех простых чисел, которые меньше заданного максимального числа. Далее, находит все возможные суммы, которые могут быть получены этими простыми числами и исключает их из дальнейшего исследования. В результате мы получим первое приближение - возможных сумм:
11 17 23 27 29 35 37 41 47 51 53 57 59 65 67 71 77 79 83 87 89 93 95 97 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 174 175 177 179 181 182 183 184 185 187 188 189 190 191 192 193 195 196
В принципе, мы могли бы сразу все эти возможные суммы проверять на уникальность. Т.е. для каждой суммы составляем все возможные пары чисел и произведение этих чисел проверяем на уникальность. Если хоть одна пара чисел, для исследуемой суммы, дает уникальное произведение, то эта сумма вычеркивается из возможных кандидатов. Эта подпрограмма для проверки на уникальность произведения - самая сложная часть всей программы. Многие, кто пытался составить подобную программу, просто забывали об этом и получали не до конца корректные результаты.
В этой подпрограмме в начале исследуемое произведение разбивается на простые множители, далее составляется список всех возможных произведений, которые могут быть получены их этих простых множителей - это первый множитель. Второй множитель получаем делением произведения на первый множитель и проверяем только варианты, когда первый множитель меньше второго. Далее оба множителя проверяем, удовлетворяют ли они условию задачи (оба меньше максимального числа 100, или их сумма меньше Max). Так мы получаем допустимые разложения произведения на два множителя и если таких разложений только одно, то это произведение уникально.
Но перед тем, как начать проверку на уникальность, мы упростим задачу, чтобы не грузить компьютер лишними вычислениями. Воспользуемся не очень очевидным свойством - какая сумма может быть максимальной.
Если исследуемое произведение имеет множителем простое число больше 50 (больше половины Мax, в нашем случае это простое число 53), то это произведение уникально. Так как при попытке получить второй вариант разложения, мы как минимум должны умножать 53 на 2 и получаем множитель больший 100.
Для любой суммы S, больше чем 53 + 2 , мы можем найти пару чисел 53 и S - 53 и произведение этих чисел будет уникальным. Отсюда делаем вывод, что все суммы больше чем 55 можно исключить из дальнейших вычислений.
Это сужает круг поиска до 11 возможных сумм:
11 17 23 27 29 35 37 41 47 51 53
Теперь делаем проверку на уникальность произведения всех возможных пар чисел. Программа выводит уникальные произведения с отрицательным знаком.
1: X + Y = 11, X * Y = : 18 24 28 30
2: X + Y = 17, X * Y = : 30 42 52 60 66 70 72
3: X + Y = 23, X * Y = : 42 60 76 90 102 112 120 126 130 132
4: X + Y = 27, X * Y = : 50 72 92 110 126 140 152 162 170 176 180 182
5: X + Y = 29, X * Y = : 54 78 100 120 138 154 168 180 190 198 204 208 210
6: X + Y = 35, X * Y = : 66 96 124 150 174 196 216 234 250 264 276 286 294 300 304 306
7: X + Y = 37, X * Y = : 70 102 132 160 186 210 232 252 270 286 300 312 322 330 336 340 342
8: X + Y = 41, X * Y = : 78 114 148 180 210 238 264 288 310 330 348 364 378 390 400 408 414 418 420
9: X + Y = 47, X * Y = : 90 132 172 210 246 280 312 342 370 396 420 442 462 480 496 510 522 532 540 546 550 552
10: X + Y = 51, X * Y = : 98 144 188 230 270 308 344 378 410 440 468 494 518 540 560 -578 594 608 620 630 638 644 648 650
11: X + Y = 53, X * Y = : 102 150 196 240 282 322 360 396 430 462 492 520 546 570 592 612 630 646 660 672 682 690 696 700 702
Обнаруживается одно уникальное произведение - 578 = 2*17*17. Действительно это число можно представить только одним способом - 17 * 34, второй способ 2 * 289 , не удовлетворяет условию - оба числа меньше 100.
Значит сумма 51 так же удаляется их возможных кандидатов, оставляя только 10 допустимых сумм.
Кстати, благодаря программе, можно легко найти следующее простое правило, как обнаружить уникальные произведения.
Если произведение имеет вид 2 * P * P, где P - простое число, квадрат которого больше максимального числа (100), то это произведение уникально и оно соответствует сумме двух чисел P и 2*P и эта сумма равна 3*P.
Значит мы можем вычеркивать все суммы, которые равны 3*P, где P простое число больше 10. В нашем случае это сумма 51 = 3 * 17.
Итак, после первых двух реплик мудрецов, первый мудрец знает, что сумма двух чисел может быть только одна из 10 чисел: 11 17 23 27 29 35 37 41 47 53
3. Тогда я знаю эти числа, — обрадовался Али.
В каком случае Али может однозначно определить, на какую пару чисел разложить свое произведение? На ту пару чисел, сумма которой, равна одной из этих 10 сумм, причем только одна пара чисел имеет сумму из этого множества. С точки зрения компьютерного алгоритма, те произведения, которые встречаются больше одного раза, должны быть удалены. Например, произведение 30 встречается два раза - для суммы 11 и для суммы 17. Если бы Али сказали число 30, то он бы обнаружил, что условиям задачи удовлетворяют две пары чисел: 5, 6 (сумма 11) и 2, 15 (сумма 17) и он не мог бы однозначно сказать - я знаю эти числа. Значит все повторяющиеся произведения удаляются. В результате мы получаем такую картину - все допустимые суммы и все допустимые произведения для этих сумм:
1: X + Y = 11, X * Y = : 18 24 28
2: X + Y = 17, X * Y = : 52
3: X + Y = 23, X * Y = : 76 112 130
4: X + Y = 27, X * Y = : 50 92 110 140 152 162 170 176 182
5: X + Y = 29, X * Y = : 54 100 138 154 168 190 198 204 208
6: X + Y = 35, X * Y = : 96 124 174 216 234 250 276 294 304 306
7: X + Y = 37, X * Y = : 160 186 232 252 270 336 340
8: X + Y = 41, X * Y = : 114 148 238 288 310 348 364 378 390 400 408 414 418
9: X + Y = 47, X * Y = : 172 246 280 370 442 480 496 510 522 532 540 550 552
10: X + Y = 53, X * Y = : 240 282 360 430 492 520 570 592 612 630 646 660 672 682 690 696 700 702
4. Тогда и я знаю! — воскликнул Вали.
После третьей реплики, Вали проделал всю вычислительную работу как и мы и отбросил все повторяющиеся произведения. И он может определить однозначно числа только тогда, когда для его суммы, остается допустимым только одно произведение. С точки зрения компьютера - в одной строчке осталось только одно допустимое произведение. В нашем случае - это произведение 52 для суммы 17, которое соответствует паре чисел 4, 13. Это решение является единственным.
Возможно это описание слишком поверхностное и не дает всех ответов?
1. После первой реплики первого мудреца, мы делаем вывод, что числа не могут быть одновременно простыми.
2. После второй реплики второго мудреца, мы знаем что сумму чисел нельзя представить как сумму двух простых чисел.
Как это реализовать на компьютере?
Самый простой вариант - ищем все возможные суммы из двух простых чисел и исключаем их из дальнейшего иследования.
В результате такого отсева у нас остается довольно небольшой выбор из возможных сумм (для Max=100 таких чисел 11, для Max=64 таких чисел 7). Причем эти допустимые суммы не объязательно должны быть простыми числами, они просто удовлетворяют условию - нельзя ни коим образом их представить как сумму двух простых чисел.
Shizic @ 16.04.26
интересна тема лютого пампа токенов. Сколько это стоит команде (маркет мейкеру) разогнать токен на тысячи процентов?
До каких значений они могут разгонять этот токен?
Не знаю сколько это стоит ММ, но видимо это ему выгодно, так как такие манипуляции становятся все чаще.
Это серьезная проблема для дельта-нейтральных стратегий.
Вот из недавнего, монета ARIA, график дневка:
Типичная манипуляция маркет-мейкером.
За месяц монета вырастает на тысячи процентов и затем падает за полчаса на исходный уровень (-90%).
Через пару дней снова рост на тысячи процентов и затем очередное падение на -90%.
Это что рыночное движение цены? (вопрос риторический).
Я уже давно не гоняюсь за такими ситуациями, но тут увидел спред больше 100% по цене между двумя биржами и решил заскочить на небольшой объем (чуть больше 1К$). В результате лонг открыл, а шорт мне не позволило открыть ни по какой цене. Итого -900$ на ровном месте.
Те кто пробовал открыть шорт на Binance, те получили ADL по цене на 50% выше рыночной.
Это означает, что на лонге вы сильно получаете минус, а на шорте вас принудительно закрывают по несуществующей цене и вы не компенсируете даже половину минуса. И даже такой гигант как Binance ничего не компенсирует в таких случаях, а если ты сильно возмущаешься, то получаешь бан (чтобы много не пиздел).
По Rave знаю ребята залетали по 3-4 круга и фармили то ли фандинг, то ли спред. Я проигнорировал все эти движения - риски слишком велики.
Темку постепенно убивают. Еще два года назад (да даже год назад) было куча выгодных ситуаций, куча неэффективностей, которые можно было абузить. Нас таких кто в теме, было относительно не много и биржи и ММ на нас не обращали внимание.
Но за тем во многих каналах начали рекламировать эти темки. Инфлюенсоры в погоне за небольшими донатами или даже просто за плюсиками начали шилить эти темки. И к-во желающих на этом заработать кратно увеличилось. Биржи уже не могли на это не реагировать. Начались многочисленные баны за любую надуманную причину, потом и конфискации средств пошли в ход. Биржи начали резать лимиты на открытие шортов, фандингами стали играться (флипать в последнюю секунду) и т.д.
Ну и маркет-мейкеры подтянулись. Пока нас было мало, то затраты на манипуляцию ценой (взвинтить цену на 1000%) были видимо слишком большими. Но когда нас стало больше критической массы, то уже выгодно поднять цену, чтобы забрать деньги у большого к-ва игроков. Слишком много стало умников, которые хотят заработать на спреде или фандинге и становятся в шорт на большие суммы. Маркет-мейкер это видит и когда сумма становится критической, то запускает манипуляцию ценой.
Все это мое ИМХО. Возможно это просто совпадение и цена летает на 1000% из-за рыночной ситуации.
Но из-за этого уже зарабатывать на дельта-нейтральных стратегиях как раньше не получается. Риски попасть под манипуляцию ценой слишком высоки.
Ну и чисто мое мнение. Если вы нашли себе какую-то темку выгодную, то тихонько без шума абузьте ее, пока есть возможность.
Если у вас появляется соблазн монетизировать это дело, рекламируя свою темку, то сто раз подумайте - а стоит ли это того?
С одной стороны вы потенциально можете заработать немного на продаже идеи, но с другой стороны вы кратно увеличиваете риск того, что темка умрет и вы сами ничего в дальнейшем не сможете заработать.
Ребята, я понимаю что наши рассуждения про логические задачи здесь мало кому интересны.
Но они интересны мне и еще пару человекам близким к программированию. Так что извините и потерпите немного.
В своих старых архивах с программами я нашел еще несколько логических задач.
Одна из них была озвучена здесь:
https://forum.gipsyteam.ru/index.php?viewtopic=10&view=findpost&p=7538160
Условие задачи:
Определите количество способов выбрать 25 чисел из целых чисел от 1 до 50 так, чтобы для любых двух выбранных чисел одно не было делителем другого.
Тогда меня заинтересовала эта задача как программиста - смогу ли я создать код, который сможет считать для любого к-ва чисел. Проблема таких программ в том, что если писать код в лоб, прямым перебором всех вариантов, то могут получиться очень длительные вычисления и программа не найдет ответ за разумное время. Нужно придумывать всякие ухищрения, чтобы добится нужной скорости. Это то что я люблю - придумывать всякие оптимизации.
Так что это не плохой тест для программистов - сможете ли вы написать такую программу?
Сейчас я попробовал решить эту задачу без компьютера. Подсмотрел идею у ребят из той темы и тогда в Екселе получилось довольно быстро найти правильный ответ, который совпал с компьютерным.
Но сейчас стало модным задачи скармливать всяким ИИшкам типа ChatGPT.
Прошлую задачу, которую мы здесь обсуждали, ИИшка довольно сносно решила и дала правильный ответ, хотя к обоснованию ответа есть некоторые вопросы.
Но вот на эту задачу, хотя она намного проще на мой взгляд, она дает совсем бесмысленный ответ.
Возможно у меня слишком примитивная версия ИИ, или я неправильно задаю вопросы.
Сможете ли вы добится от нее правильного ответа (я его точно знаю) и обоснование этого ответа?
Сдаст ли ИИ экзамен на этот раз?
Galax, бесплатный дипсик чего-то там накодил на 130 строк и всё запустилось с первой попытки.
Программа выдала ответ: 32130 способов, время работы 12 миллисекунд.
Обоснование там на несколько страниц отборной математики, тоже особо не вникал :)
Но в своём словесном обосновании он вручную насчитал, что должно получаться 414720 способов.
P.S. После недолгих препираний написал программу, которая выдаёт:
N = 10 -> 4
N = 20 -> 26
N = 30 -> 72
N = 40 -> 264
N = 50 -> 1632
И теперь он уверен, что это должен быть правильный ответ. Но новая программа для N 50 работает уже почти 2 секунды.
Абсолютно все его генерации были рабочими с первой попытки, никаких ошибок синтаксиса и прочей фигни.
Galax, Исходный вариант за 9.5 секунд отработал, ответ 1957642878.
После просьбы ускорить выдал вариант, который при N=100 отрабатывает за 8 секунд, но зато для N=50 она работает 130 мс.
Ответ для N=100: 238147776, за 8 секунд
Что-то где-то не сходится :)
С ними так всегда, можно только идею подсмотреть, конкретную реализацию всё равно самому писать надо и перепроверять по много раз.
Manslay, У меня для N=100 выходит 1022976 вариантов.
Но это не проверенная инфа, не с кем валидироваться.
Но скорее ИИшка тут тупит.
Jak, Подробнее, я думаю что написал первый хороший калькулятор по китайскому покеру, если не в мире, то во всяком случае в России)). По нему обучались многие наши ведущие игроки за плату.
divs31, А в каком году ты сделал этот калькулятор?
А можно сверить с тобой какой-то расклад, ну чтобы проверить свой калькулятор?
Можно и в личку если что.
Вот и закончилась эпопея с RAVE:
Монета с 0,22$ выросла за пару дней до 28$, а затем упала на 90% до 3$ за пару часов.
В этой монете я не участвовал.
Зато оказался в M.
Шорт открывал по 1.8$, а сегодня цена доходила до 4.7$ и заставляла нервничать и корректировать позицию:
Вот такие рыночные движения цены. Это когда большинство альты упало на 80-90%, находятся монеты, которые летают на тысячи процентов и чисто случайно я оказываюсь в таких монетах.
Galax @ 18.04.26
А можно сверить с тобой какой-то расклад, ну чтобы проверить свой калькулятор?
Можно и в личку если что.
Да пожалуйста.
Год не помню. Помню заказчик заказал на OFCP где по одной карте сдавали, а через две недели говорит появился ананас. Помню что зашел на GamblerGames и играл по 1 руб. за куш
Jak, Блин, от тебя не ожидал такого).
Я несколько раз ссылался на алгоритм решения:
Но перед тем, как начать проверку на уникальность, мы упростим задачу, чтобы не грузить компьютер лишними вычислениями. Воспользуемся не очень очевидным свойством - какая сумма может быть максимальной.
Если исследуемое произведение имеет множителем простое число больше 50 (больше половины Мax, в нашем случае это простое число 53), то это произведение уникально. Так как при попытке получить второй вариант разложения, мы как минимум должны умножать 53 на 2 и получаем множитель больший 100.
Для любой суммы S, больше чем 53 + 2 , мы можем найти пару чисел 53 и S - 53 и произведение этих чисел будет уникальным. Отсюда делаем вывод, что все суммы больше чем 55 можно исключить из дальнейших вычислений.
Это сужает круг поиска до 11 возможных сумм:
11 17 23 27 29 35 37 41 47 51 53