[Архив!] Чистая математика, физика, химия и т.п.: задачки для тренировки мозгов, никак не связанные с торговлей - страница 450
Вы упускаете торговые возможности:
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Регистрация
Вход
Вы принимаете политику сайта и условия использования
Если у вас нет учетной записи, зарегистрируйтесь
На самом деле есть более общее наблюдение (оно видно из распринтовки MD): вероятно, все разумные варианты ограничиваются парами чисел 2^n и p (простое). Я его не доказал, просто предполагаю.
Теперь, опираясь на это предположение, сделаем нечто реальное. Самое сложное в диалоге мудрецов - это последняя реплика. Именно она пока требует расматривать много вариантов. Давайте предположим, что три реплики у нас уже состоялись, и осталась только последняя. А много ли сумм из МДС могут быть представлены в виде 2^n + простое?
Почему именно такое разложение? Да просто потому, что Б в последней реплике, расматривая возможные разложения сумм (см. мой предыдущий пост) и соответствующие произведения, встретив произведение 2*...*2*простое, уже заранее знает, что из сумм для него только одна и может быть допустимой, т.к. только одна нечетна - если числа равны степени двойки и нечетному простому. Это сразу дает реального кандидата.
Итак, поехали.
11 = 2^2+7 = 2^3+3. Кандидатов - два. Облом сразу.
17 = 2^2+13. Больше таких представлений нет. Хороший кандидат.
23 = 2^2+19 = 2^4+7. Облом.
27 = 2^2+23 = 2^3+19 = 2^4+11. Тем более облом.
29 = 2^4+13. Представление единственно. Еще один кандидат.
35 = 2^2+31 = 2^4+19 = 2^5+3. Облом.
37 = 2^3+29 = 2^5+5 . Облом.
41 = 2^2 +37. Представление единственно. Кандидат.
47 = 2^2+43 = 2^4+31. Облом.
51 = 2^2+47 = 2^3+43 . Облом.
53 = 2^4+37. Представление единственно. Кандидат.
Итак, из всех МДС у нас остались только 4 допустимые суммы - 17, 29, 41, 53.
____________________________________________________________
С 17 мы разобрались: Б, имея 17, в четвертой реплике вычисляет числа однозначно.
Продолжение следует. Нам осталось проанализировать только три числа, чтобы добить задачу.
__________________________________
P.S. Давайте все-таки сделаем все 4 числа кратко и изящно. Предполагаем, что три реплики уже произнесены, и остался только последний ход мудреца Б. Начнем с тех, которые не пройдут, чтобы быстренько перейти к главному.
29 = 4+25. П (=2*2*5*5) = 2*50 = 4*25 = 5*20 = 10*10. Суммы - 52, 29, 25, 20. Подходит одно только 29 из зелененького списка. Это однозначное решение, т.е. кандидат (числа 4 и 25). Однако еще одно однозначное у нас уже есть - это 16 и 13. Значит, Б свою реплику не скажет.
41 = 16+25. П (=2*2*2*2*5*5) = 2*200 = 4*100 = 5*80 = 8*50 = 10*40 = 16*25 = 20*20. Суммы - 202, 104, 85, 58, 50, 41, 40. Единственная допустимая - 41, т.е. кандидат (числа 16 и 25). Однако еще одно однозначное у нас уже есть - это 4 и 37. Значит, Б свою реплику не скажет.
53 = 13+40. П (=2*2*2*5*13) = 2*260 = 4*130 = 5*104 = 8*65 = 10*52 = 13*40 = 20*26. Суммы - 262, 134, 109, 73, 62, 53, 46. Единственная допустимая сумма - конечно, 53 (исходные числа - 13 и 40). Однако еще одно однозначное у нас уже есть - это 16 и 37. Значит, Б свою реплику не скажет.
И, наконец, 17. Пока короткого доказательства валидности решения не придумал. Думаю. Потом соберу доказательство полностью, чтобы оно было в одном посте. Но задача - вот теперь, now - решена полностью.
Нашёл ошибку. Переоптимизация называется. :)
В одном месте был неполный перебор, неверное условие окончания цикла. Поправил.
// см. строки 68-69
// for(uint i=2;i<=sqrt(n);i++) // ОШИБКА!!
for(uint i=2;i<n/2;i++) // Правильно так.
Теперь результаты удивили.
Решение единственно (S=17; P=52; a=4; b=13) вплоть до максимально допустиммой суммы == 867
При макс. сумме == 868 - два решения.
Вот распечатка.
2011.01.15 18:33:11 MetaSage (EURUSD,M1) //+---- Максимальная сумма = 867 -------------------+
2011.01.15 18:33:10 MetaSage (EURUSD,M1) S=17; P=52; a=4; b=13
2011.01.15 18:33:10 MetaSage (EURUSD,M1) //+---- Максимальная сумма = 867 -------------------+
2011.01.15 18:33:10 MetaSage (EURUSD,M1) //============== СТАРТ ========================
2011.01.15 18:32:59 MetaSage (EURUSD,M1) //+---- Максимальная сумма = 868 -------------------+
2011.01.15 18:32:59 MetaSage (EURUSD,M1) S=65; P=244; a=4; b=61
2011.01.15 18:32:59 MetaSage (EURUSD,M1) S=17; P=52; a=4; b=13
2011.01.15 18:32:59 MetaSage (EURUSD,M1) //+---- Максимальная сумма = 868 -------------------+
2011.01.15 18:32:59 MetaSage (EURUSD,M1) //============== СТАРТ ========================
Так, у этой задачи огромный потенциал, а не какая-то жалкая сотня. Нашел текст:
А вот что говорит RockMover, который решал эту задачу на компьютере: Следующая пара - 4 и 61, она появляется, когда наибольшее допустимое число - 437. (Если я ничего не напутал). В диапазоне примерно до 800 появляется еще пара (32, 131), а пара (16, 73) - только когда диапазон больше 900.
Точнее проверять я не стал из-за медленнодействия вычислительной машины, а воспользоваться суперкомпьютером Cray I я не мог, так как во-первых пришлось бы отрывать людей от работы, а во-вторых сейчас все равно выходные.
MD, прогони до пары тысяч, а?
Следующая граница 1503 (2 решения) / 1504 (3 решения)
2011.01.15 18:50:34 MetaSage (EURUSD,M1) //+---- Максимальная сумма = 1504 -------------------+
2011.01.15 18:50:34 MetaSage (EURUSD,M1) S=163; P=4192; a=32; b=131
2011.01.15 18:50:34 MetaSage (EURUSD,M1) S=65; P=244; a=4; b=61
2011.01.15 18:50:34 MetaSage (EURUSD,M1) S=17; P=52; a=4; b=13
2011.01.15 18:50:34 MetaSage (EURUSD,M1) //+---- Максимальная сумма = 1504 -------------------+
2011.01.15 18:50:34 MetaSage (EURUSD,M1) //============== СТАРТ ========================
2011.01.15 18:50:10 MetaSage (EURUSD,M1) //+---- Максимальная сумма = 1503 -------------------+
2011.01.15 18:50:09 MetaSage (EURUSD,M1) S=65; P=244; a=4; b=61
2011.01.15 18:50:09 MetaSage (EURUSD,M1) S=17; P=52; a=4; b=13
2011.01.15 18:50:09 MetaSage (EURUSD,M1) //+---- Максимальная сумма = 1503 -------------------+
Алексей > "И, наконец, 17. Пока короткого доказательства валидности решения не придумал. Думаю."
Ну здесь короткого и не будет, ибо весь диалог корректен. Тут полный проход нужен. "Бее.."
Так, у этой задачи огромный потенциал, а не какая-то жалкая сотня. Нашел текст:
MD, прогони до пары тысяч, а?
Выражаю огромную благодарность ValS за то, что подсунул такой великолепный и древний... боянчег.
Одновременно предлагаю присвоить задачке титул самой крутой в ветке.
MD, ОК, прогоню сам. Пока не стоит :)
При двух тыщах 4 решения, однако границу искать не стал - комп тормозит, ручками перебирать границу нудно получается.
2011.01.15 18:59:14 MetaSage (EURUSD,M1) S=163; P=4192; a=32; b=131
2011.01.15 18:59:14 MetaSage (EURUSD,M1) S=89; P=1168; a=16; b=73
2011.01.15 18:59:14 MetaSage (EURUSD,M1) S=65; P=244; a=4; b=61
2011.01.15 18:59:14 MetaSage (EURUSD,M1) S=17; P=52; a=4; b=13
2011.01.15 18:59:14 MetaSage (EURUSD,M1) //+---- Максимальная сумма = 2000 -------------------+
Возможно тормозит в начале, из-за слишком большой таблицы разложений на множители.
У меня там таблица размером SMax*(SMax-1) строится на всяк случай. Щас подумаю, мож уменьшить корректно будет. Нужна лемма о максимальном произведении... :))
1. Выражаю огромную благодарность ValS за то, что подсунул такой великолепный и древний... боянчег.
2. Одновременно предлагаю присвоить задачке титул самой крутой в ветке.
3. MD, ОК, прогоню сам. Пока не стоит :)
Mathemat:
Так, у этой задачи огромный потенциал, а не какая-то жалкая сотня. Нашел текст:
А вот что говорит RockMover, который решал эту задачу на компьютере: Следующая пара - 4 и 61, она появляется, когда наибольшее допустимое число - 437. (Если я ничего не напутал). В диапазоне примерно до 800 появляется еще пара (32, 131), а пара (16, 73) - только когда диапазон больше 900.
Точнее проверять я не стал из-за медленнодействия вычислительной машины, а воспользоваться суперкомпьютером Cray I я не мог, так как во-первых пришлось бы отрывать людей от работы, а во-вторых сейчас все равно выходные.
По большому счету надо снимать ограничения на сумму. Все рассуждения остаются по сути такими же, просто их больше.
Судя по тому, что в цитате челу потребовался Cray 1, его алгоритм был менее оптимизирован, чем твой :)