Собственно, задача:
У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».
Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.
Назовите эти числа.
Решение под катом.
Задачу я решил методом логики и подбора, видимо, иначе она не решается, во всяком случае я такого решения не встречал. Подбором просто найти первое решение, но остаётся загадкой единственно оно на заданном промежутке или нет. Мне пришла мысль написать решение с использованием ленивых коллекций и практики ради была выбрана scala. Итак начнём.
Будем двигаться по сообщениям мудрецов, смотреть, какую информацию они нам дают и писать соответствующие функции:
- Али говорит, что он не знает загаданных чисел. Отсюда можно сделать вывод, что хотя бы одно из загаданных чисел не простое, иначе число раскладывалось бы на множители единственным способом. Соответственно создаём стрим простых чисел:
lazy val primes: Stream[Int] = 2 #:: Stream.from(3).filter(i => isPrime(i)) def isPrime(x: Int): Boolean = { primes.takeWhile(i => i*i <= x).forall { k => x % k > 0} }
Всё просто — следующее число будет простым только если оно не делится без остатка ни на одно из всех уже известных простых чисел. Дальше можно создать список всевозможных чисел для Али убрав оттуда произведения простых чисел(6, 15,...), но мы пока этого делать не будем.
- Дальше Вали сообщает, что он знал, что Али не знает загаданных чисел. Откуда он мог это знать? Видимо его число раскладывается на суммы пар таким образом, что среди них нет ни одной, в которой оба числа были бы простыми. Приведу пример: предположим, что шейх шепнул Вали число 7, его можно разложить на пары (5+2), (4+3). Мы ведь знаем что загаданные числа больше единицы, так что нет смысла раскладывать на 6+1. Смотрим на 5 и 2 — они оба простые, значит шейх не мог шепнуть Вали число 7. Теперь мы можем составить список всевозможных чисел, которые шейх мог шепнуть Вали:
//раскладываем число на сумму двух других в соотв. с условиями задачи def expandBySum(x: Int): List[(Int, Int)] = { @tailrec def helper(accum: List[(Int, Int)], i: Int, j: Int): List[(Int, Int)] = { if (i < j) accum else helper((i, j) :: accum, i - 1, j + 1) } helper(List.empty, x - 2, 2) } lazy val ValiNumbers: Stream[Int] = Stream.from(4).filter(i => !expandBySum(i).exists(expanded => isPrime(expanded._1) && isPrime(expanded._2)))
Генерируем поток чисел, которые не имеют ни одного разложения на сумму двух простых.
- После того, как Али узнал, что числа, которые шейх мог сказать Вали ограничены, он восклицает, что знает ответ! Продолжаем распутывать клубок – судя по всему, число Али раскладывается на пару множителей так, что сумму только одной пары нельзя разложить на сумму двух простых чисел. То есть сумма только одной пары должна входить в список возможных чисел Вали!
//раскладываем число на два множителя def expandByProduct(x: Int): List[(Int, Int)] = { var biggestPossibleDivision = x / 2 @tailrec def helper(accum: List[(Int, Int)], i: Int): List[(Int, Int)] = { if (i == biggestPossibleDivision) return accum if (x % i == 0) { biggestPossibleDivision = if(x / i <= i) biggestPossibleDivision else x / i helper((x / i, i) :: accum, i + 1) } else helper(accum, i + 1) } helper(List.empty, 2) } def inValiNumbers(x: Int): Boolean = { ValiNumbers.takeWhile(valis => valis <= x).contains(x) } lazy val AliNumbers: Stream[Int] = Stream.from(4).filter(i => expandByProduct(i).count(expanded => inValiNumbers(expanded._1 + expanded._2)) == 1)
Раскладываем число на список из двух множителей и проверяем, что сумма только одной пары входит в список чисел Вали. Так мы получаем все числа, которые шейх мог шепнуть Али.
- Узнав, что Али вдруг понял, что-за числа загадал ему шейх, Вали тоже вычислил загаданные числа! Формулировка описания того, как он смог это сделать, получится весьма запутанной, так что подумайте сами :) А я лишь приведу пример кода, который фильтрует числа Вали так, чтобы для обоих мудрецов было решение:
lazy val ValiNumbersWithSolution: Stream[Int] = ValiNumbers.filter(valis => expandBySum(valis).map(expanded => expanded._1 * expanded._2).count(inAliNumbers) == 1)
Ленивый список со всеми возможными парами чисел, которые мог загадать шейх:
lazy val solution: Stream[String] = ValiNumbersWithSolution.map(valis => {
val solution = expandBySum(valis).filter(expanded => inAliNumbers(expanded._1 * expanded._2)).head
"Alis number: " + solution._1 * solution._2 + "; Valis number: " + (solution._1 + solution._2) + "; solution: " + solution._1 + " & " + solution._2
})Оказывается, в диапазоне от 1 до 100 существует всего четыре пары чисел, которые бы мог загадать шейх. Иными словами, мудрецам неслабо фартануло :)
println("Vali's possible numbers: " + (ValiNumbers.take(20).toList mkString ", "))
println("Ali's possible numbers: " + (AliNumbers.take(30).toList mkString ", "))
println("Vali's numbers that give solution to Ali: " + (ValiNumbersWithSolution.take(3).toList mkString ", "))
println(solution.take(3).toList mkString "\n")
"Vali's possible numbers: 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87"
"Ali's possible numbers: 18, 24, 28, 50, 52, 54, 76, 92, 96, 98, 100, 112, 124, 140, 144, 148, 152, 160, 172, 176, 188, 192, 208, 212, 216, 220, 228, 232, 242, 244"
"Vali's numbers that give solution to Ali: 17, 65, 89"
"Alis number: 52; Valis number: 17; solution: 13 & 4"
"Alis number: 244; Valis number: 65; solution: 61 & 4"
"Alis number: 1168; Valis number: 89; solution: 73 & 16"
Ссылка на сорцы
Комментарии (26)
hidoba
16.04.2015 13:11+6Решение задачи однозначно.
Причина, по которой автор не получил его, состоит в том, что, простые числа — недостаточно сильное условие.
К примеру, из произведения 2691 можно вполне однозначно получить 39 и 69.
pronvis Автор
16.04.2015 13:23Да, спасибо — в конце, при подсчёте пар возможных загаданных чисел <100, не учёл возможности их разложения, делал это уже глазами и в самом конце, а когда писал код как раз не хотел ограничивать возможные решения.
pronvis Автор
16.04.2015 13:11+8Оказывается, в диапазоне от 1 до 100 существует всего четыре пары чисел, которые бы мог загадать шейх. Иными словами, мудрецам неслабо фартануло :)
На самом деле это не так — решение одно. Остальные три пары: [61, 4], [71, 16], [73, 64] не подходят под ограничивающее условие «загаданные числа меньше 100». Али бы мог сразу их вычислить, назови шейх ему числа (61*4)=244, (73*16)=1168 или (73 *64)=4672. Ведь раскладываются они на множители, так чтобы оба множителя были меньше 100 единственным образом, например 4672: (73 * 64) (146 * 32) (292 *16) (584 * 8) (1168 * 4) (2336 * 2)
gregst
16.04.2015 15:51но ведь каждое число меньше 100, в задаче не говорится о том, что сумма и произведение тоже будут меньше 100
pronvis Автор
16.04.2015 15:57+6Допустим шейх шепнул Али число 4672, тот не будучи дураком за 2 наносекунды разложил его на множители — (73 * 64) (146 * 32) (292 *16) (584 * 8) (1168 * 4) (2336 * 2). По условиям шейха Оба загаданных числа меньше 100, в списке множителей такой вариант только один, значит Али сразу узнал бы ответ — 73 и 64
Polsky
18.04.2015 10:39У меня получились несколько иные результаты.
Кроме пары 4-13 есть ещё две пары: 77-96 и 80-99.
Например для пары 77-96 произведение 7392 может быть получено только ещё одной парой 84*88, которая не проходит по фильтру Vali's possible numbers. Для 80-99 аналогичная ситуация, вторая пара 88-90.Polsky
18.04.2015 11:19Впрочем, нет, ответ действительно один, фильтр неправильный, см. комментарий hidoba выше.
pronvis Автор
18.04.2015 11:27У вас ошибка в вычислениях. Обе пары «77-96 и 80-99» не являются решениями, так как тогда Али бы не смог вычислить искомую пару после фразы Вали "Я это знал" потому что таких пар больше одной; напомню что это такие пары, сумма которых должна раскладываться на сумму двух чисел таким образом, чтобы среди них не было ни одной пары с двумя простыми числами.
Например, возьмём 77 * 96 = 7392. Можно представить в виде 88 * 84; 88+84 = 172, 172 может быть числом Вали — оно не раскладывается на сумму двух простых. Как и 132 * 56 и ещё несколько других.
Поиск суммы пары множителей числа Али среди возможных чисел Вали:77 * 96 = 7392 x: 88; y: 84 (88 + 84) = 172 inVali's numbers:true x: 96; y: 77 (96 + 77) = 173 inVali's numbers:false x: 112; y: 66 (112 + 66) = 178 inVali's numbers:false x: 132; y: 56 (132 + 56) = 188 inVali's numbers:true x: 154; y: 48 (154 + 48) = 202 inVali's numbers:false x: 168; y: 44 (168 + 44) = 212 inVali's numbers:true x: 176; y: 42 (176 + 42) = 218 inVali's numbers:false x: 224; y: 33 (224 + 33) = 257 inVali's numbers:false x: 231; y: 32 (231 + 32) = 263 inVali's numbers:false x: 264; y: 28 (264 + 28) = 292 inVali's numbers:true x: 308; y: 24 (308 + 24) = 332 inVali's numbers:true x: 336; y: 22 (336 + 22) = 358 inVali's numbers:false x: 352; y: 21 (352 + 21) = 373 inVali's numbers:false x: 462; y: 16 (462 + 16) = 478 inVali's numbers:false x: 528; y: 14 (528 + 14) = 542 inVali's numbers:false x: 616; y: 12 (616 + 12) = 628 inVali's numbers:true x: 672; y: 11 (672 + 11) = 683 inVali's numbers:false x: 924; y: 8 (924 + 8) = 932 inVali's numbers:true x: 1056; y: 7 (1056 + 7) = 1063 inVali's numbers:false x: 1232; y: 6 (1232 + 6) = 1238 inVali's numbers:false x: 1848; y: 4 (1848 + 4) = 1852 inVali's numbers:true x: 2464; y: 3 (2464 + 3) = 2467 inVali's numbers:false x: 3696; y: 2 (3696 + 2) = 3698 inVali's numbers:true 80 * 99 = 7920 x: 90; y: 88 (90 + 88) = 178 inVali's numbers:false x: 99; y: 80 (99 + 80) = 179 inVali's numbers:false x: 110; y: 72 (110 + 72) = 182 inVali's numbers:false x: 120; y: 66 (120 + 66) = 186 inVali's numbers:false x: 132; y: 60 (132 + 60) = 192 inVali's numbers:true x: 144; y: 55 (144 + 55) = 199 inVali's numbers:false x: 165; y: 48 (165 + 48) = 213 inVali's numbers:false x: 176; y: 45 (176 + 45) = 221 inVali's numbers:false x: 180; y: 44 (180 + 44) = 224 inVali's numbers:false x: 198; y: 40 (198 + 40) = 238 inVali's numbers:false x: 220; y: 36 (220 + 36) = 256 inVali's numbers:false x: 240; y: 33 (240 + 33) = 273 inVali's numbers:false x: 264; y: 30 (264 + 30) = 294 inVali's numbers:false x: 330; y: 24 (330 + 24) = 354 inVali's numbers:false x: 360; y: 22 (360 + 22) = 382 inVali's numbers:false x: 396; y: 20 (396 + 20) = 416 inVali's numbers:false x: 440; y: 18 (440 + 18) = 458 inVali's numbers:false x: 495; y: 16 (495 + 16) = 511 inVali's numbers:false x: 528; y: 15 (528 + 15) = 543 inVali's numbers:false x: 660; y: 12 (660 + 12) = 672 inVali's numbers:false x: 720; y: 11 (720 + 11) = 731 inVali's numbers:false x: 792; y: 10 (792 + 10) = 802 inVali's numbers:false x: 880; y: 9 (880 + 9) = 889 inVali's numbers:false x: 990; y: 8 (990 + 8) = 998 inVali's numbers:false x: 1320; y: 6 (1320 + 6) = 1326 inVali's numbers:false x: 1584; y: 5 (1584 + 5) = 1589 inVali's numbers:false x: 1980; y: 4 (1980 + 4) = 1984 inVali's numbers:true x: 2640; y: 3 (2640 + 3) = 2643 inVali's numbers:false x: 3960; y: 2 (3960 + 2) = 3962 inVali's numbers:false
Polsky
18.04.2015 12:10То что я ошибся, это я уже понял, см. мой комментарий выше, но только причина ошибки другая.
Число 172 это произведение двух простых чисел 83*89, но ошибка в самом фильтре Вали.
Недостаточно проверить только произведения двух простых чисел.
Например для числа 172 произведение его слагаемых 73 и 99 равно 7227, и оно не может быть получено произведением каких либо других чисел меньших 100.pronvis Автор
18.04.2015 12:14Я намеренно игнорировал условие что загаданные числа меньше 100, чтобы получить стрим всех возможных решений.
me76
16.04.2015 16:27+1Если более простого и красивого решения не существует, то, учитывая, что мудрецы провели все эти вычисления в уме, заключаю, что они либо обладают сверхспособностями в арифметике и запоминании, либо у них аутизм.
pronvis Автор
16.04.2015 16:40+5А вам не кажется всё это подставой?
И мудрецы сообщили пораженному царю задуманные им числа.
Поражённому царю? Как мы выяснили существует только одна пара чисел, которую мог загадать царь из десяти тысяч (пренебрежём точностью) всевозможных пар! Складывается ощущение, что он знал какую пару выбрать :) А раз он знал, то и мудрецы видимо подставные! Цирк одним словом, всё ради того чтобы позабавить простых землепашцев.
andy1618
17.04.2015 08:21«существует всего четыре пары чисел, которые бы мог загадать шейх.»
Уфф, вы так не пугайте! Всю жизнь был уверен, что у этой красивой задачи всего одно решение, а тут — «на тебе!» :)
Хорошо, что в комментариях быстро восстановили справедливость :)
MichaelBorisov
18.04.2015 02:03Иными словами, мудрецам неслабо фартануло :)
Мудрецы, в отличие от нас, знали сумму и произведение чисел. Поэтому для них могло не быть такой неоднозначности, как для нас.
Ради однозначности решения задачу можно дополнить дополнительным условием, которое дает минимум информации о решении.
CaptainFlint
18.04.2015 14:20Что любопытно, решение (4, 13) будет уникальным, даже если поднять верхнюю границу с 99 до 865. Только при 866 появляется второе возможное решение (4, 61) из-за того, что 1732 начинает раскладываться неоднозначно (2*866, 4*433), не исключается на первом шаге и дальше влияет на всю цепочку рассуждений (от 99 до 433, разумеется, этого произведения нет совсем).
Если кому интересно, у меня свой вариант решения, написанный на Перле. Аргументом командной строки можно задавать максимальное значение для загаданных чисел. Если выставить $DEBUG в 1, будет на каждом шаге дампить все возможные значения и соответствующие им пары. (Код — тупой перебор всех пар.)
Код программы#!/usr/bin/perl use strict; use warnings; # Usage: perl solution.pl [MAX_NUM] # (default for MAX_NUM is 99) my $max_num = ($ARGV[0] || 99); my $DEBUG = 0; # Possible values Ali (muls) and Vali (sums) have (as we know it) # Key - sum/mul, value - possible pairs for this sum/mul my %sums = (); my %muls = (); # Search for an element in the array and delete it sub del_array_elem($$) { my ($arr, $elem) = @_; for (my $i = 0; $i < scalar(@$arr); ++$i) { if ($arr->[$i] eq $elem) { splice(@$arr, $i, 1); return; } } } # Dump current possible values sub dmp($;$) { my ($prefix, $force) = @_; return if (!$DEBUG && !$force); print "$prefix\nPossible muls:\n"; for my $i (sort { $a <=> $b } keys(%muls)) { print $i . '(' . join(',', @{$muls{$i}}) . ")\n"; } print "\n"; print "Possible sums:\n"; for my $i (sort { $a <=> $b } keys(%sums)) { print $i . '(' . join(',', @{$sums{$i}}) . ")\n"; } print "\n\n"; } # Initially, no information - all pairs are possible for (my $i = 2; $i <= $max_num; ++$i) { for (my $j = $i; $j <= $max_num; ++$j) { $sums{$i + $j} = [] if (!$sums{$i + $j}); push(@{$sums{$i + $j}}, $i . '+' . $j); $muls{$i * $j} = [] if (!$muls{$i * $j}); push(@{$muls{$i * $j}}, $i . '*' . $j); } } dmp('Initial:'); # Ali does not know x,y => mul is not a unique multiplication # And Vali knows this beforehand => sum is not sum of such a pair my @del_muls_from_sum = (); for (my $i = 2; $i <= $max_num; ++$i) { for (my $j = $i; $j <= $max_num; ++$j) { if (scalar(@{$muls{$i * $j}}) == 1) { delete $muls{$i * $j}; if ($sums{$i + $j}) { # Since we remove sum-values, we should also eliminate respective muls push @del_muls_from_sum, @{$sums{$i + $j}}; delete $sums{$i + $j}; } } } } dmp('No mul-unique pairs:'); print "\nTo delete: " . join(', ', @del_muls_from_sum) . "\n\n" if ($DEBUG); for my $sum (@del_muls_from_sum) { $sum =~ m/^(\d+)\+(\d+)$/ or die "Invalid format of '$sum'"; my $i = $1; my $j = $2; if ($muls{$i * $j}) { del_array_elem($muls{$i * $j}, $i . '*' . $j); if (scalar(@{$muls{$i * $j}}) == 0) { delete $muls{$i * $j}; } } } @del_muls_from_sum = (); dmp('Stage 2:'); # At this stage Ali knows the numbers => mul is a unique. # Remove all non-unique muls and leave only respective sums. my %restsums = (); for (my $i = 2; $i <= $max_num; ++$i) { for (my $j = $i; $j <= $max_num; ++$j) { if ($muls{$i * $j}) { if (scalar(@{$muls{$i * $j}}) > 1) { delete $muls{$i * $j}; } elsif (scalar(@{$muls{$i * $j}}) == 1) { if ($sums{$i + $j}) { $restsums{$i + $j} = [] if (!$restsums{$i + $j}); push(@{$restsums{$i + $j}}, $i . '+' . $j); } } } } } %sums = %restsums; dmp('Unique muls:'); # Vali also knows numbers => sum is a unique. # Remove all non-unique sums and leave only respective muls. my %restmuls = (); for (my $i = 2; $i <= $max_num; ++$i) { for (my $j = $i; $j <= $max_num; ++$j) { if ($sums{$i + $j}) { if (scalar(@{$sums{$i + $j}}) > 1) { delete $sums{$i + $j}; } elsif (scalar(@{$sums{$i + $j}}) == 1) { if ($muls{$i * $j}) { $restmuls{$i * $j} = [] if (!$restmuls{$i * $j}); push(@{$restmuls{$i * $j}}, $i . '*' . $j); } } } } } %muls = %restmuls; dmp('Final solutions:', 1);CaptainFlint
18.04.2015 14:25Хотя нет, не только 1732, там много и других неоднозначных произведений вылезает на 866. Пока не разбирался, какие в итоге оказывают влияние на финальный результат.
GIum
А можно тут больше пояснений? Как Вы перешли к простым числам? Ведь в условии ни про них ни про разложение на множители ничего нету.
pronvis Автор
Если бы шейх шепнул Али, например 15, то он сразу узнал бы загаданные числа — 3 и 5. Ведь все произведения двух простых чисел делятся без остатка только на «своих создателей» )) на себя и на единицу.
GIum
Да, действительно. Спасибо.
formatbce
Это же очевидно — если бы оба множителя были простыми, то они, по определению, не раскладывались бы на подмножители, и тогда Али сразу узнал бы числа. Пример: произведение равно 10. Тогда числа — 2 и 5 (оба простые). Если же произведение, например, 20, то у него 3 простых множителя — 2, 2 и 5, и, соответственно, числа могут быть (2, 10) и (4, 5)
Upd не успел...