Перейти к основному содержимому

Эксперимент 001: вертикальный Мат. Праздник 2023, класс 7, задача 2

(Проект эксперимента доступен здесь.)

В феврале 2023-его года ещё один Математический Праздник прошёл в Москве и нескольких других городах. Это олимпиада для 6-ых и 7-ых классов, которая проходит каждый февраль. На ней была задача:

Найдите какое-нибудь решение ребуса Ф/Е+ВР/АЛЬ=1\text{Ф}/\text{Е} + \text{ВР}/\text{АЛЬ} = 1. Разным буквам соответствуют разные цифры. Черта обозначает деление. В ответе запишите полученное числовое равенство.

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

Сначала давайте начнём с идеи программы!​

Идея проста: мы просто переберём все возможные значения букв в ребусе. Это означает, что мы переберём все 7-размещения (Ф,Е,В,Р,А,Л,Ь)(\text{Ф}, \text{Е}, \text{В}, \text{Р}, \text{А}, \text{Л}, \text{Ь}) множества возможных цифр {0,1,2,3,4,5,6,7,8,9}\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} и проверим каждое из них, удовлетворяет ли оно ребусу.

Но всего существует A107=10!(10−7)!=604  800A_{10}^{7} = \frac{10!}{(10-7)!} = 604\;800 возможных размещений. Мы можем хранить их в списке и отображать/фильтровать в новый список несколько раз, чтобы получить все искомые ответы. И тут нет никакой проблемы, потому что это не такое большое число элементов для компьютера, чтобы испытывать трудности. Наоборот, таким образом будет быстрее, чем манипулируя последовательностями, для такого числа элементов. Но давайте воспользуемся последовательностями, так что не будет проблем с будущими изменениями в коде, когда будет сильно большее количество данных для обработки.

Решение​

Сначала мы создадим data-класс для размещений и простой фальш-конструктор из списка для него:

data class ФЕВРАЛЬ(val Ф: Int, val Е: Int, val В: Int, val Р: Int, val А: Int, val Л: Int, val Ь: Int)

fun ФЕВРАЛЬ(args: KoneList<Int>): ФЕВРАЛЬ {
    require(args.size == 7u) { "Cannot construct ФЕВРАЛЬ from list $args" }
    val (Ф, Е, В, Р, А, Л, Ь) = args
    return ФЕВРАЛЬ(Ф = Ф, Е = Е, В = В, Р = Р, А = А, Л = Л, Ь = Ь)
}

Затем простой код для получения дробей из ребуса:

val ФЕВРАЛЬ.frac1: Rational get() = Rational(Ф, Е)
val ФЕВРАЛЬ.frac2: Rational get() = Rational(В * 10 + Р, (А * 10 + Л) * 10 + Ь)

Затем давайте проверим, что данное размещение корректно:

fun ФЕВРАЛЬ.check(): Boolean = Ф != 0 && Е != 0 && В != 0 && А != 0 && context(Rational.context) { frac1 + frac2 eq one }

Здесь мы проверяем, что первый цифры не равны нулю и что сумма дробей выше равна единице.

Теперь давайте воспользуемся этой функцией и получим все решения! Во-первых, давайте получим все размещения:

val digits = (0 until 10).toKoneList()
val февральPermutations: Sequence<ФЕВРАЛЬ> =
    digits.permutations(7u)
        .map { ФЕВРАЛЬ(it) }

Во-вторых, мы просто отфильтруем неверные размещения:

val февральPermutations: Sequence<ФЕВРАЛЬ> =
    digits.permutations(7u)
        .map { ФЕВРАЛЬ(it) }
        .filter { it.check() }

И наконец, давайте отсортируем их по значению первой дроби, а затем по значению Ф\text{Ф}:

val февральPermutations: Sequence<ФЕВРАЛЬ> =
    digits.permutations(7u)
        .map { ФЕВРАЛЬ(it) }
        .filter { it.check() }
        .sortedWith(
            Comparator<ФЕВРАЛЬ> { perm1, perm2 -> context(Rational.context) { (perm1.frac1 - perm2.frac1).numerator compareTo 0 } }.thenBy { it.Ф }
        )

Теперь у нас есть все искомые решения в переменной февральPermutations. Давайте выведем их в трёх разных форматах:

fun main() {
    println("Ф Е В Р А Л Ь | ФЕВРАЛЬ | Ф/Е+ВР/АЛЬ")
    for (февраль in февральPermutations) println(февраль.run { "$Ф $Е $В $Р $А $Л $Ь | $Ф$Е$В$Р$А$Л$Ь | $Ф/$Е+$В$Р/$А$Л$Ь" })
}

Вот результаты:

Ф Е В Р А Л Ь | ФЕВРАЛЬ | Ф/Е+ВР/АЛЬ
2 6 9 0 1 3 5 | 2690135 | 2/6+90/135
2 6 9 8 1 4 7 | 2698147 | 2/6+98/147
3 9 6 8 1 0 2 | 3968102 | 3/9+68/102
3 9 7 2 1 0 8 | 3972108 | 3/9+72/108
3 9 8 4 1 2 6 | 3984126 | 3/9+84/126
3 8 6 5 1 0 4 | 3865104 | 3/8+65/104
3 8 7 5 1 2 0 | 3875120 | 3/8+75/120
2 5 7 8 1 3 0 | 2578130 | 2/5+78/130
4 9 7 0 1 2 6 | 4970126 | 4/9+70/126
2 4 5 3 1 0 6 | 2453106 | 2/4+53/106
2 4 6 5 1 3 0 | 2465130 | 2/4+65/130
2 4 6 9 1 3 8 | 2469138 | 2/4+69/138
2 4 7 8 1 5 6 | 2478156 | 2/4+78/156
2 4 7 9 1 5 8 | 2479158 | 2/4+79/158
2 4 8 5 1 7 0 | 2485170 | 2/4+85/170
2 4 9 3 1 8 6 | 2493186 | 2/4+93/186
3 6 5 2 1 0 4 | 3652104 | 3/6+52/104
3 6 5 4 1 0 8 | 3654108 | 3/6+54/108
3 6 7 9 1 5 8 | 3679158 | 3/6+79/158
3 6 8 5 1 7 0 | 3685170 | 3/6+85/170
3 6 9 2 1 8 4 | 3692184 | 3/6+92/184
4 8 5 3 1 0 6 | 4853106 | 4/8+53/106
4 8 6 5 1 3 0 | 4865130 | 4/8+65/130
4 8 7 6 1 5 2 | 4876152 | 4/8+76/152
3 5 4 8 1 2 0 | 3548120 | 3/5+48/120
3 5 6 8 1 7 0 | 3568170 | 3/5+68/170
3 5 7 2 1 8 0 | 3572180 | 3/5+72/180
3 5 7 6 1 9 0 | 3576190 | 3/5+76/190
3 5 8 4 2 1 0 | 3584210 | 3/5+84/210
3 5 9 6 2 4 0 | 3596240 | 3/5+96/240
5 8 3 9 1 0 4 | 5839104 | 5/8+39/104
2 3 5 8 1 7 4 | 2358174 | 2/3+58/174
4 6 7 3 2 1 9 | 4673219 | 4/6+73/219
4 6 9 1 2 7 3 | 4691273 | 4/6+91/273
6 9 3 4 1 0 2 | 6934102 | 6/9+34/102
6 9 5 8 1 7 4 | 6958174 | 6/9+58/174
6 9 7 8 2 3 4 | 6978234 | 6/9+78/234
6 9 8 1 2 4 3 | 6981243 | 6/9+81/243
5 7 8 6 3 0 1 | 5786301 | 5/7+86/301
3 4 2 7 1 0 8 | 3427108 | 3/4+27/108
6 8 3 5 1 4 0 | 6835140 | 6/8+35/140
6 8 4 3 1 7 2 | 6843172 | 6/8+43/172
6 8 5 1 2 0 4 | 6851204 | 6/8+51/204
7 9 2 4 1 0 8 | 7924108 | 7/9+24/108
7 9 4 8 2 1 6 | 7948216 | 7/9+48/216
7 9 5 8 2 6 1 | 7958261 | 7/9+58/261
4 5 2 6 1 3 0 | 4526130 | 4/5+26/130
4 5 3 2 1 6 0 | 4532160 | 4/5+32/160
4 5 3 6 1 8 0 | 4536180 | 4/5+36/180
4 5 3 8 1 9 0 | 4538190 | 4/5+38/190
4 5 6 2 3 1 0 | 4562310 | 4/5+62/310
4 5 7 2 3 6 0 | 4572360 | 4/5+72/360
4 5 7 6 3 8 0 | 4576380 | 4/5+76/380
4 5 7 8 3 9 0 | 4578390 | 4/5+78/390
5 6 2 9 1 7 4 | 5629174 | 5/6+29/174
6 7 5 9 4 1 3 | 6759413 | 6/7+59/413
7 8 4 5 3 6 0 | 7845360 | 7/8+45/360
7 8 5 2 4 1 6 | 7852416 | 7/8+52/416
7 8 6 3 5 0 4 | 7863504 | 7/8+63/504
7 8 6 4 5 1 2 | 7864512 | 7/8+64/512