Бегство от перебора

Добрый день.

Решение задачи может осуществляться как минимум с двумя целями:
- узнать ответ (речь о решении проблем на работе или сдаче экзаменов),
- развить себя, решая задачу.

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

Когда я говорю о важности избегания переборных решений, то, конечно, не отказываю этому способу в эффективности. Более того, иногда быстрая реализация решения перебором тоже полезна (например, чтобы с интересом изучать язык программирования). Но исходный смысл задачки «одним росчерком превратить 5+5+5+5=555 в верное равенство» был всё же в развитии воображения и интуиции (что никак не отменяет полезности переборного решения).

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

Поэтому давайте решим ту вторую систему, не используя грубую силу. Итак, задачка состояла в следующем — решить систему:
     Г*О+Д=21,
     В*Е+К=21,
     Э*Р+А=21.

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

Интуиция подсказывает, что полезно проанализировать цифры, являющиеся делителями числа справа (21). Легко почувствовать, что с тройкой бывает много разных решений, поэтому сконцентрируемся на семёрке. Вопрос: где она может стоять в равенстве A*B+C=21?

Если вдруг C=7, то A*B=14, из чего следует, что или A, или B должно быть равно 7, чего не может быть (так как разным цифрам соответствуют разные буквы, а C=7 по предположению). Тогда рассмотрим случай A=7. Легко увидеть, что это возможно только при C=0. Это значит, что если семёрка входит в ответ, то одно из равенств выглядит так: 7*3+0=21.

Как мы ранее уже говорили, с тройкой трудно ждать чего-то интересного, поэтому рассмотрим цифру 0. Вопрос: где 0 может стоять в равенстве A*B+C=21? Легко понять, что ни A, ни B не могут быть равны 0. Это значит, что C=0. Другими словами, если в ответ входит 7, то в него входит и 0. А если в ответ входит 0, то в него входит 7. Поскольку у нас на 9 букв претендуют 10 цифр, то не может быть, что 7 и 0 одновременно не входят в ответ. А это значит, что они обе входят. И это очень хорошо, так как они с собой забрали ещё и цифру 3.

Теперь наша задача звучит так:
     3*7+0=21,
     В*Е+К=21,
     Э*Р+А=21.

Давайте подумаем, какие самые маленькие множители могут быть в произведениях В*Е и Э*Р. Свободные цифры у нас такие: 1, 2, 4, 5, ... Но разве может быть меньшим множителем 5? Нет, так как 5*6 уже больше 21. А может ли быть наименьшим множителем 1? Тоже нет, так как 1*A+B=21 не имеет решения в цифрах. Это означает, что на две позиции у нас ровно два кандидата, поэтому можно считать, что В=2, а Э=4.

Теперь наша задача звучит так:
     3*7+0=21,
     2*Е+К=21 (2<Е),
     4*Р+А=21 (4<Р).

Из Э=4 сразу следует единственная возможность не превысить 21: 4*5+1=21. А с В=2 получаем уже небольшой перебор — свободные цифры у нас такие: 6, 8, 9. Но тут уже трудно не найти 2*6+9=21. Получается, что цифра 8 у нас не может участвовать в решении. Первая задача (где вместо 21 стоит 15) решается совершенно аналогично.

К сожалению, далеко не всегда есть возможность почувствовать направление, в котором надо идти, чтобы эффективно отсекать заведомо неинтересные случаи. Но иногда это возможно, поэтому жалко упускать такой случай. Где компьютер проведёт быстрый и бессмысленный перебор, человек может сразу сконцентрироваться на важных шагах. Но чем больше компьютер помогает маленькому человеку избегать тренировок мозга, тем меньше взрослый человек начинает отличаться от компьютера (в том смысле, что тоже не чувствует, куда двигаться эффективнее, а тупо перебирает все варианты по алфавиту).

Повторюсь: полностью от перебора уйти почти невозможно. Сильные шахматисты не только имеют хорошее шахматное чутьё, но и быстро-быстро перебирают варианты. Но поскольку человек не может рассмотреть все варианты развития шахматной партии, он вынужден тренировать своё «чувство поля». Стоит привыкать стараться сокращать перебор, чтобы взявшись за настоящую и сложную задачу в зрелом возрасте, не опускать руки со словами «всех компьютеров планеты не хватит, чтобы решить эту задачу за век», а бодро проинтуитить, как отбросить огромные объёмы бессмысленных вычислений. Впрочем, нельзя забывать, что хоть ощущения и могут хорошо направить, но им никогда нельзя верить (т.е. обязательно надо за ними проверять).

Если вы согласны, что важно тренировать интуицию в раннем возрасте, то, пожалуйста, поделитесь ссылкой на заметку в Twitter, Google+, Facebook, Вконтакте или добавьте её в свой блог/ЖЖ: <a href="http://my-tribune.blogspot.com/2012/12/brute-force.html">Бегство от перебора</a>. Спасибо!

Хороших выходных!