Решение задачи о двух мудрецах

Давеча была опубликована логическая задача про Шерил, а в комментариях к ней хаброюзер сообщил о более интересной задаче про двух мудрецов.

Собственно, задача:
У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».

Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.

Назовите эти числа.

Решение под катом.

Задачу я решил методом логики и подбора, видимо, иначе она не решается, во всяком случае я такого решения не встречал. Подбором просто найти первое решение, но остаётся загадкой единственно оно на заданном промежутке или нет. Мне пришла мысль написать решение с использованием ленивых коллекций и практики ради была выбрана scala. Итак начнём.

Будем двигаться по сообщениям мудрецов, смотреть, какую информацию они нам дают и писать соответствующие функции:

  1. Али говорит, что он не знает загаданных чисел. Отсюда можно сделать вывод, что хотя бы одно из загаданных чисел не простое, иначе число раскладывалось бы на множители единственным способом. Соответственно создаём стрим простых чисел:

    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,...), но мы пока этого делать не будем.

  2. Дальше Вали сообщает, что он знал, что Али не знает загаданных чисел. Откуда он мог это знать? Видимо его число раскладывается на суммы пар таким образом, что среди них нет ни одной, в которой оба числа были бы простыми. Приведу пример: предположим, что шейх шепнул Вали число 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)))

    Генерируем поток чисел, которые не имеют ни одного разложения на сумму двух простых.

  3. После того, как Али узнал, что числа, которые шейх мог сказать Вали ограничены, он восклицает, что знает ответ! Продолжаем распутывать клубок – судя по всему, число Али раскладывается на пару множителей так, что сумму только одной пары нельзя разложить на сумму двух простых чисел. То есть сумма только одной пары должна входить в список возможных чисел Вали!

    //раскладываем число на два множителя
      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)

    Раскладываем число на список из двух множителей и проверяем, что сумма только одной пары входит в список чисел Вали. Так мы получаем все числа, которые шейх мог шепнуть Али.

  4. Узнав, что Али вдруг понял, что-за числа загадал ему шейх, Вали тоже вычислил загаданные числа! Формулировка описания того, как он смог это сделать, получится весьма запутанной, так что подумайте сами :) А я лишь приведу пример кода, который фильтрует числа Вали так, чтобы для обоих мудрецов было решение:

    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"

Ссылка на сорцы
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 26

    +2
    Али говорит, что он не знает загаданных чисел. Отсюда можно сделать вывод, что хотя бы одно из загаданных чисел не простое, иначе число раскладывалось бы на множители единственным способом.

    А можно тут больше пояснений? Как Вы перешли к простым числам? Ведь в условии ни про них ни про разложение на множители ничего нету.
      +5
      Если бы шейх шепнул Али, например 15, то он сразу узнал бы загаданные числа — 3 и 5. Ведь все произведения двух простых чисел делятся без остатка только на «своих создателей» )) на себя и на единицу.
        0
        Да, действительно. Спасибо.
        +1
        Это же очевидно — если бы оба множителя были простыми, то они, по определению, не раскладывались бы на подмножители, и тогда Али сразу узнал бы числа. Пример: произведение равно 10. Тогда числа — 2 и 5 (оба простые). Если же произведение, например, 20, то у него 3 простых множителя — 2, 2 и 5, и, соответственно, числа могут быть (2, 10) и (4, 5)

        Upd не успел...
        +6
        Решение задачи однозначно.
        Причина, по которой автор не получил его, состоит в том, что, простые числа — недостаточно сильное условие.
        К примеру, из произведения 2691 можно вполне однозначно получить 39 и 69.
          0
          Да, спасибо — в конце, при подсчёте пар возможных загаданных чисел <100, не учёл возможности их разложения, делал это уже глазами и в самом конце, а когда писал код как раз не хотел ограничивать возможные решения.
          +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)
            0
            но ведь каждое число меньше 100, в задаче не говорится о том, что сумма и произведение тоже будут меньше 100
              +6
              Допустим шейх шепнул Али число 4672, тот не будучи дураком за 2 наносекунды разложил его на множители — (73 * 64) (146 * 32) (292 *16) (584 * 8) (1168 * 4) (2336 * 2). По условиям шейха Оба загаданных числа меньше 100, в списке множителей такой вариант только один, значит Али сразу узнал бы ответ — 73 и 64
                0
                понял, спасибо
              0
              У меня получились несколько иные результаты.
              Кроме пары 4-13 есть ещё две пары: 77-96 и 80-99.
              Например для пары 77-96 произведение 7392 может быть получено только ещё одной парой 84*88, которая не проходит по фильтру Vali's possible numbers. Для 80-99 аналогичная ситуация, вторая пара 88-90.
                0
                Впрочем, нет, ответ действительно один, фильтр неправильный, см. комментарий hidoba выше.
                  0
                  У вас ошибка в вычислениях. Обе пары «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
                  

                    0
                    То что я ошибся, это я уже понял, см. мой комментарий выше, но только причина ошибки другая.
                    Число 172 это произведение двух простых чисел 83*89, но ошибка в самом фильтре Вали.
                    Недостаточно проверить только произведения двух простых чисел.
                    Например для числа 172 произведение его слагаемых 73 и 99 равно 7227, и оно не может быть получено произведением каких либо других чисел меньших 100.
                      0
                      Я намеренно игнорировал условие что загаданные числа меньше 100, чтобы получить стрим всех возможных решений.
                +1
                Если более простого и красивого решения не существует, то, учитывая, что мудрецы провели все эти вычисления в уме, заключаю, что они либо обладают сверхспособностями в арифметике и запоминании, либо у них аутизм.
                  +5
                  А вам не кажется всё это подставой?
                  И мудрецы сообщили пораженному царю задуманные им числа.

                  Поражённому царю? Как мы выяснили существует только одна пара чисел, которую мог загадать царь из десяти тысяч (пренебрежём точностью) всевозможных пар! Складывается ощущение, что он знал какую пару выбрать :) А раз он знал, то и мудрецы видимо подставные! Цирк одним словом, всё ради того чтобы позабавить простых землепашцев.
                    0
                    Просто при выборе других чисел или Вали или Али мог ответить сразу.
                      0
                      То же замечание — какова вероятность случайно выбрать эти числа
                    +6
                    Либо у них scala.
                      0
                      Ну и не обязательно аутизм, вот посмотрите на этом видео один из таких «мудрецов».
                        0
                        А я так и сказал — либо аутизм, либо сверхспособности в арифметике
                      0
                      «существует всего четыре пары чисел, которые бы мог загадать шейх.»

                      Уфф, вы так не пугайте! Всю жизнь был уверен, что у этой красивой задачи всего одно решение, а тут — «на тебе!» :)
                      Хорошо, что в комментариях быстро восстановили справедливость :)
                        0
                        Иными словами, мудрецам неслабо фартануло :)

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

                        Ради однозначности решения задачу можно дополнить дополнительным условием, которое дает минимум информации о решении.
                          0
                          Что любопытно, решение (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);
                          

                            0
                            Хотя нет, не только 1732, там много и других неоднозначных произведений вылезает на 866. Пока не разбирался, какие в итоге оказывают влияние на финальный результат.

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Самое читаемое