Вы не сможете решить эту задачу про повышение и пароль
hard

Вы не сможете решить эту задачу про повышение и пароль

Задача дьявольски сложная, но решение есть

Любите математику?
Это для вас
Попробуйте бесплатный тренажёр «Основы математики для цифровых профессий».
Попробовать бесплатно
Любите математику? <br data-lazy-src="https://thecode.media/wp-content/uploads/2023/07/b54-mob.png"><noscript><img width="537" height="164" class=

Чтобы ваши мозги сегодня закипели пораньше, вот вам сверхсложная задача. 

Тимлид решил выдать новичку за хорошую работу новый ноутбук, а заодно решил убедиться, что его можно повысить в должности и поднять зарплату. Для этого он убрал ноутбук в сейф и сказал:

Ноутбук — в сейфе, и он твой, если ты сможешь открыть этот сейф. Пароль от сейфа — 9 цифр, от 1 до 9, причём каждая встречается только один раз. При этом:

  • девятизначное число пароля делится на 9 без остатка
  • если убрать последнюю цифру, то оставшееся восьмизначное число делится на 8 без остатка
  • если ещё убрать последнюю цифру, то оставшееся семизначное число делится на 7 без остатка
  • такое правило будет работать всё время: сколько цифр в числе, на эту цифру число делится без остатка.

Какой пароль нужно ввести новичку, чтобы получить ноутбук и повышение?

«А? Чё?» — произнёс новичок. Он не понял ничего из того, что ему сказал тимлид, поэтому решил задачу тупейшим перебором.

Сначала он написал функцию проверки, нет ли в числе повторяющихся цифр и ноля:

// проверяем число на уникальность цифр и на наличие ноля
function isUnique(digit) {
    // переводим в строку
    N = String(digit);
    // если есть ноль — проверка не прошла
    if (N.match(/0/)) {return false}
    // если есть повторяющиеся цифры — проверка не прошла
    if ((/([0-9]).*?\1/).test(N)) {return false} else {return true}
}

Потом он сделал функцию, которая проверяет, делятся ли все внутренние числа на количество их разрядов:

// проверяем, делятся ли все вложенные числа на количество разрядов
function isDivided(digit) {
    // переменная для промежуточных вычислений
    var temp;
    // по умолчанию считаем, что делятся
    res = true;
    // если число сразу не делится на 9 — проверка не прошла
    if (digit % 9 != 0) {res = false} 
    // перебираем все остальные разряды
    for (let i = 1; i < 9; i++) {
        // отбрасываем ненужные разряды справа
        temp = Math.floor(digit/10**i)
        // если результат не делится на количество разрядов — проверка не прошла
        if (temp % (9 - i) != 0) {res = false}
    }
    return res;
}

А потом он написал цикл, который перебирает и сразу проверяет все девятизначные числа:

// перебираем все девятизначные числа
for (let i = 100000000; i < 999999999; i++) {
    // если оно неуникальное — берём следующее
    if (isUnique(i) == false) { continue }
    // если оно делится по всем правилам — выводим его
    if (isDivided(i)) { console.log(i) }
}

Запустил в браузере и получилось:

Вы не сможете решить эту задачу про повышение и пароль

Алгоритмическая сила! 

А вот его код целиком:

// проверяем число на уникальность цифр и на наличие ноля
function isUnique(digit) {
    // переводим в строку
    N = String(digit);
    // если есть ноль — проверка не прошла
    if (N.match(/0/)) {return false}
    // если есть повторяющиеся цифры — проверка не прошла
    if ((/([0-9]).*?\1/).test(N)) {return false} else {return true}
}

// проверяем, делятся ли все вложенные числа на количество разрядов
function isDivided(digit) {
    // переменная для промежуточных вычислений
    var temp;
    // по умолчанию считаем, что делятся
    res = true;
    // если число сразу не делится на 9 — проверка не прошла
    if (digit % 9 != 0) {res = false} 
    // перебираем все остальные разряды
    for (let i = 1; i < 9; i++) {
        // отбрасываем ненужные разряды справа
        temp = Math.floor(digit/10**i)
        // если результат не делится на количество разрядов — проверка не прошла
        if (temp % (9 - i) != 0) {res = false}
    }
    return res;
}

// перебираем все девятизначные числа
for (let i = 100000000; i < 999999999; i++) {
    // если оно неуникальное — берём следующее
    if (isUnique(i) == false) { continue }
    // если оно делится по всем правилам — выводим его
    if (isDivided(i)) { console.log(i) }
}

Это сложная задача, поэтому чтобы не запутаться, обозначим все цифры буквами: ABCDEFGHI.

Теперь посмотрим на чётные группы цифр — каждая из них должна делиться на 2, а это значит, что последняя цифра в каждой группе чётная:

Вы не сможете решить эту задачу про повышение и пароль

Получается, что B,D,F,H — чётные цифры. Соответственно, A,C,E,G,I — нечётные.

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

Делим на 5

Начнём с деления на 5: чтобы число делилось на 5 без остатка, оно должно заканчиваться на 0 или 5. Это значит, что E — или 0, или 5. Но в нашем наборе цифр нет ноля, поэтому E = 5:

Вы не сможете решить эту задачу про повышение и пароль

Делим на 4

Чтобы число нацело делилось на 4, его последние две цифры вместе тоже должны делиться на 4. Получается, что CD делится нацело на 4. Мы знаем, что C нечётное, а D — чётное — выпишем все комбинации, при которых это делится на 4:

12 16

 

32 36

 

52 56

 

72 76

 

92 96

 

Видно, что D принимает только два значения — 2 и 6:

Вы не сможете решить эту задачу про повышение и пароль

Делим на 8

Применим то же правило деления на 4 к восьмизначному числу ABCDEFGH. Логика такая: если число делится на 8, то и на 4 оно тоже делится как на делитель восьмёрки. Это значит, что H тоже равно 2 или 6:

Вы не сможете решить эту задачу про повышение и пароль

Это значит, что оставшиеся числа B и F равны 4 или 8:

Вы не сможете решить эту задачу про повышение и пароль

Делим на 3 

Число из первых трёх цифр ABC делится на 3 — это ясно из условия задачи. Но число ABCDEF тоже делится на 3, потому что оно делится на 6, а значит — одновременно на 2 и 3. Но раз число из первых трёх цифр в ABCDEF делится на 3 (по условию), то и второе число из цифр DEF тоже делится на 3 без остатка:

Вы не сможете решить эту задачу про повышение и пароль

Теперь применим сюда те знания о числах, которые мы получили раньше:

Вы не сможете решить эту задачу про повышение и пароль

Выходит, что DEF может быть одним из четырёх чисел:

254

258

654

658

Но только два из них делятся на 3 без остатка — 258 и 654. Это значит, что если D = 2, то F = 8, а если D = 6, то F = 4. Добавим эту связь на общую схему:

Вы не сможете решить эту задачу про повышение и пароль

Долгая и нудная работа с числами

Теперь так же проверим число ABC, учитывая, что в середине стоит 4 или 8. Вот все числа, которые можно так составить:

143 147 149

341 347 349

741 743 749

941 943 947

183 187 189

381 387 389

781 783 789

981 983 987

Выберем из них те, что делятся на 3 без остатка:

147 183 189

381 387 741

783 789 981

987

Но мы выяснили, что число DEF может быть только 258 или 654. Если мы добавим эти три цифры в те варианты ABC, что делятся на 3 без остатка, то получим ABCDEF, которое должно делиться на 6 без остатка:

147258 183258 189258 381258 387258 741258

783258 789258 981258 987258

147654 183654 189654 381654 387654 741654

783654 789654 981654 987654

Теперь отбросим все числа, где цифры встречаются больше одного раза. Вот что останется:

147258 183654 189654 381654

387654 741258 783654 789654

981654 987654

А теперь самое сложное: чтобы получить семизначное число, добавим к каждому в конец нечётную цифру, которая ещё не встречалась в этом числе. Например, в числе 147258 использовались 1, 7 и 5, поэтому в конец можно добавить только 3 или 9. Сделаем так с каждым числом и получим 20 чисел, которые нужно будет проверить:

1472583 1836547 1896543 3816547

3876541 7412583 7836541 7896541

9816543 9876541

1472589 1836549 1896547 3816549

3876549 7412589 7836549 7896543

9816547 9876543

Из этих чисел всего три делятся на 7 без остатка: 1472583, 3816547 и 7836549.

Теперь к этим трём числам добавим восьмую цифру. Помним правило выше: если D = 2, то H = 6:

14725836 38165472 и 78365492

Нацело на 8 делится только одно число — 38165472. При этом у нас осталась неиспользованная девятка, которая при добавлении в конец и даст нам нужное число: 381654729.

Проверим, выполняются ли все условия:

381654729 / 9 = 42406081

38165472 / 8 = 4770684

3816547 / 7 = 545221

381654 / 6 = 63609

38165 / 5 = 7633

3816 / 4 = 954

381 / 3 = 127

38 / 2 = 19

3 / 1 = 3

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Алексей Сухов

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев

Соцсети:

Аня Соколова

Любите математику? Это для вас
Попробуйте бесплатный тренажер «Основы математики для цифровых профессий». Это все необходимые знания, чтобы закрыть пробелы в математике для айтишника.
Попробовать бесплатно
Любите математику? Это для вас Любите математику? Это для вас Любите математику? Это для вас Любите математику? Это для вас
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
hard