Занимательная задачка «Несчастливый билет»

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

И чтобы развлечь себя до конца поездки, я изобрел концепт «Несчастливого билета». Билета, у которого ни одно число из множества значений, полученного при помощи первых трех цифр, не совпадет ни с одним числом из множества значений, полученного при помощи последних трех цифр. Подробности в условии задачи.

Условие задачи

Найти все значения из 6 цифр, для которых ни одно из значений множества, полученного из первых трех цифр, не совпадет ни с одним значением множества из последних трех цифр.

Множество значений для каждой триады нужно получить:

  • Применяя перестановку цифр в пределах триады
  • Выполняя арифметические действия между цифрами: +, -, *, /
  • Используя скобки.
  • Применяя в качестве значений множества только целые числа

Пример
Билет: 983060

Множество значений триады: 983 [96, 33, 2, 3, 35, 99, 4, 69, 5, 75, 11, 45, 14, 15, 48, 51, 19, 20, 216, 24]
Множество значений триады: 060 [0, 6]

Общего значения нет — это несчастливый билет.

P.S. Опускаю отрицательные значения, так как для каждого отрицательного значения найдется такое же положительное

Таким образом, если вы до конца поездки не смогли найти общее число для первых и последних трех цифр, используя действия из условия, значит вам попался несчастливый билет! Или у вас не очень с математикой.

Мой вариант решения задачи
Выкладывать весь код не вижу смысла, постараюсь объяснить главное.

Список всех комбинаций из трех цифр — 1000 штук. Набор, в который будут складываться найденные билеты.

   List<Combination> combinations = new ArrayList<>(1000);
   Set<String> tickets = new HashSet<>();

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

Пока общее значение не найдено, добавляем строку, означающую наш билет, в набор.
Как только значение найдется, удаляем билет из набора и переходим к следующему сравнению.

for (Combination comb1 : combinations)
        {
            for (Combination comb2 : combinations)
            {
                for (Integer x : comb1.getValues())
                {
                    if (comb2.getValues().contains(x))
                    {
                        tickets.remove(comb1.toString() + comb2.toString());
                        break;
                    }
                    else
                    {
                        tickets.add(comb1.toString() + comb2.toString());
                    }
                }
            }
        }

Привожу метод, вычисляющий множество значений для каждой комбинации:
(Метод выполняется для каждой перестановки 3 цифр комбинации)

 private void countValues(int a, int b, int c)
    {
        //Sum
        addValue(a + b + c);
        addValue(a + b - c);
        addValue(a + b * c);
        addValue((a + b) * c);

        if (c != 0 && b % c == 0) {addValue(a + b / c);}
        if (c != 0 && (a + b) % c == 0) { addValue((a + b) / c); }

        //Subtraction
        addValue(a - b + c);
        addValue(a - b - c);
        addValue(a - b * c);
        addValue((a - b) * c);

        if (c != 0 && b % c == 0) {addValue(a - b / c);}
        if (c != 0 && (a - b) % c == 0) {addValue((a - b) / c);}

        //Multiplication
        addValue(a * b + c);
        addValue(a * b - c);
        addValue(a * (b - c));
        addValue(a * b * c);

        if (c != 0)
        {
            double x = (double)a * (double)b / (double)c;

            if (isInteger(x)) { addValue((int)x); }
        }

        if (c != 0)
        {
            double x = (double)a * (double)b / (double)c;

            if (isInteger(x)) { addValue((int)x); }
        }

        //Division

        if (b != 0 && a % b == 0) { addValue(a / b + c); }
        if (b + c != 0 && a % (b + c) == 0) { addValue(a / (b + c)); }

        if (b != 0 && a % b == 0) { addValue(a / b - c); }
        if (b - c != 0 && a % (b - c) == 0) { addValue(a / (b - c)); }

        if (b != 0)
        {
            double x = (double)a / (double)b * (double)c;

            if (isInteger(x)) { addValue((int)x); }
        }

        if (b != 0 && c != 0)
        {
            double x = (double)a / (double)b / (double)c;

            if (isInteger(x)) { addValue((int)x); }
        }
    }

Итого: 23088 билетов.

Счастливый билет: каждый 18
Несчастливый билет: каждый 43

Спасибо за внимание!
Share post

Comments 31

    +6
    > И чтобы развлечь себя до конца поездки, я изобрел концепт «Несчастливого билета».

    Черт! А я книгу в телефоне читаю, чтобы скоротать время :-(
      0
      По вашей логике:
      9-8/3 = 6
      Отбрасывать хорошо — округлять интереснее…
        0
        Может и интересно, но как-то нечестно. В глубине души я буду знать, что эти числа не равны. Зато я не запрещаю использовать нецелые числа в процессе вычисления. e.g. 2/8*4
          0
          Смысл есть в этом? Ведь можно переставить и не целых промежуточных уже не будет
        +5
        Расширте до игры Ландау.
          0
          Жаль не могу вам поставить плюс, но спасибо за подсказку отличной игры! ^_^
          +1
          Жалко, что в приведенном решении перебор вариантов идет вручную. Самый сок задачи был бы в том, чтобы именно алгоритмически перебрать все возможные комбинации знаков и скобок.

          P.S. Не нашел комбинации a * (b - c).
            0
            Спасибо. Добавил, но на результат не повлияло. Буду рад, если кто-нибудь откликнется и опубликует собственный вариант решения.
              +1
              Деление лучше рассматривать в виде целой части и остатка от деления, это и алгоритм и момент из комментариев выше
              0
              Перестановка и обратная польская запись позволяют перебрать все варианты, правда с избытком из-за коммутативности сложения и умножения.
                0
                Вот я попробовал решить задачу перебора комбинаций операций.
                0
                Я играл ещё с факториалами, корнями и степенями.
                  +1
                  Есть известная вариация: расставляя знаки арифметических действий и скобки, получить в результате 100. Знаки само собой не обязательно расставлять между всеми цифрами, то есть для билета 777777 допустимым решением является (777-77)/7. Решения есть для значительной доли билетов (если мне не изменяет память, по опыту выходило где-то треть или половина), но зачастую очень хитрые.
                    0
                    У меня получилось раз 10… из 10. Может повезло. Но использовал все (если сравнить с игрой Ландау то далеко не все).
                      0
                      Закодил перебор. Если нигде не ошибся, то счастливыми являются 906735 билетов. Так что результат 10 из 10 кажется не сильно удивительным. Но, если честно, я поражён, что у вас так легко получилось. Порой я убивал всю поездку, чтобы найти сотню. Поэтому попробовал специально поискать сложные билеты (сам билет в заголовке спойлера, ответ внутри):
                      101048
                      (10+10/4)*8

                      399940
                      (3-9/(9+9))*40

                      146778
                      (14-6/7)*7+8

                      198797
                      1-9*(8/(7-9)-7)

                      Я постарался отсортировать их в порядке возрастания сложности.

                      P.S. Если запретить использовать многозначные числа (то есть требовать расставить все 5 знаков), то счастливых билетов остается 716270.
                        0
                        У меня тоже получается почти в 100% случаев, когда часто ездил на автобусе, специально собирал билетики, для которых не получилось в уме составить. За год поездок штук 10 таких билетов накопилось, из них для 7 или 8 решения и вправду не существует (проверял самописной программкой)
                          0
                          422400. Годами думал, не решил
                            0
                            4^(-log2(2))*400
                              0
                              Ну логарифм тоже не очень то вписывается, как и знак степени. Так то у меня была мысль:
                              (4^ — (2/2)) * 400
                              Для яваскрипта:
                              (4** — (2/2)) * 400
                              Но это выходит за рамки + — / * ( )
                                0
                                Но если решений без степени и логарифма нет (phvoryh подтвердил), то почему бы не воспользоваться.
                                  0
                                  Или факториал:
                                  4!*2*2+4+0+0
                                0
                                Перебор подтверждает, что решений нет.
                            +1
                            Предложенный алгоритм обхода можно слегка улучшить. Первое, что бросается в глаза — много ненужных операций с листом тикетов — почти каждый кандидат добавляется в лист, и почти каждый потом из листа убирается. Немного переписав цикл, можно оставить только добавление, которое будет происходить после внутреннего for, с заменой break на continue на внешний цикл. Второе — можно сравнивать forward-only (комбинацию с самой собой сравнивать не имеет смысла, комбинацию BA рассматривать после того как раньше рассмотрели AB тоже не имеет смысла), добавляя сразу comb1 + comb2 и comb2 + comb1.

                            for (int comb1Index = 0; comb1Index < combinations.size(); comb1Index++)
                            {
                            nextPair: // labeling for early exit from nested loop
                            for (int comb2Index = comb1Index + 1; comb2Index < combinations.size(); comb2Index++)
                            {
                            Combination comb1 = combinations[comb1Index];
                            Combination comb2 = combinations[comb2Index];
                            for (Integer x: comb1.getValues())
                            {
                            if (comb2.getValues().contains(x))
                            {
                            continue nextPair;
                            }
                            }
                            tickets.add(comb1.toString() + comb2.toString());
                            tickets.add(comb2.toString() + comb1.toString());
                            }
                            }

                            P.S. Прошу прощение за корявые отступы. Не могу использовать тэги, а пробелы и табы почему-то игнорируются.
                              0
                              Спасибо. Время выполнения уменьшилось с 2000 ms до 300 ms)
                              0
                              Еще как вариант (если много свободной памяти) можно заранее посчитать мэп обратных зависимостей (в то же время, когда прямые считаются) — от арифметического результата к списку триад. По этим данным легко быстро построить лист билетов, не удовлетворяющим условию задачи. Можно для этого создать массив из миллиона булов, в который писать тру, на каждую такую найденную комбинацию. В конце пройти по массиву, выбрав те индексы, где значение false.
                                0
                                Я в детстве еще факториал себе разрешал. И тогда несчастливых билетов не остается (это гипотеза :) )
                                В вашем случае 6 — 6/6 = 0! + 1 + 3
                                  0
                                  Всего 55252 счастливых билетов от 1 000 до 999 999
                                    +1
                                    Вот я тут думал, что мне с MAC'ами и IP'ами из подсети моего провайдера делать.
                                    Теперь знаю)
                                      0
                                      А я просто пытаюсь собрать значение 100 из цифр билетика. Только перестановка запрещена, т.к. в некоторых случаях очень сильно облегчает задачу. А так, использую любые арифметические знаки.
                                      Порой все легко, иногда очень сложно. Бывают случаи, когда невозможно (например, первые 95 билетов).
                                      Другими словами, нужно расставить арифметические знаки так, чтобы при решении вышло 100.
                                        +1

                                        Попробовал найти "в лоб" все несчастливые билеты. Оказалось несложно, компьютер считал где-то 5 секунд. Всего нашлось 874 комбинации.


                                        Код на Питоне
                                        opindex=["+","*","-","/"]
                                        partemplates=["%s%s%s%s%s","(%s%s%s)%s%s","%s%s(%s%s%s)"]
                                        def build(values,op1,op2,paren):
                                          textvalues=[str(a) for a in values]
                                          result=partemplates[paren] % (textvalues[0],opindex[op1],textvalues[1],opindex[op2],textvalues[2])
                                          return result
                                        
                                        tickets=[]
                                        calcs=[]
                                        
                                        def all_tickets():
                                          for d1 in range(0,10):
                                            for d2 in range(0,10):
                                              for d3 in range(0,10):
                                                calc_ticket((d1,d2,d3))
                                        
                                        def calc_ticket(ticket):
                                          calc=set()
                                          for o1 in range(0,4):
                                            for o2 in range(0,4):
                                              for p in range(0,3):
                                                form=build(ticket,o1,o2,p)
                                                try:
                                                  value=int(eval(form))
                                                  calc.add(value)
                                                except:
                                                  pass
                                          tickets.append(ticket)
                                          calcs.append(calc)
                                        
                                        bad_tickets=[]
                                        def find_bad_tickets():
                                          for i1 in range(0,len(calcs)):
                                            for i2 in range(0,len(calcs)):
                                              if calcs[i1].isdisjoint(calcs[i2]):
                                                bad_tickets.append((i1, i2))
                                        
                                        all_tickets()
                                        find_bad_tickets()
                                        print(len(bad_tickets))
                                          0
                                          Я думал, я один этим занимаюсь,*(

                                          Only users with full accounts can post comments. Log in, please.