В числе 9876543210 зачёркиваются цифры (от 1 до 9 штук) так, чтобы оставшееся число делилось на 4. Не пиша компьютерной программы и не пользуясь катькулятором, определите, сколько таких различных чисел можно получить?
По признаку делимости на 444 достаточно смотреть последние одну или две цифры числа. Для двухзначного окончания 10x+y≡2x+y(mod4)10x+y\equiv2x+y\pmod410x+y≡2x+y(mod4), значит y≡−2x(mod4)y\equiv-2x\pmod4y≡−2x(mod4). Из этого: если десяток xxx чётный, то единица y∈{0,4,8}y\in\{0,4,8\}y∈{0,4,8}; если xxx нечётный, то y∈{2,6}y\in\{2,6\}y∈{2,6}. Число 987654321098765432109876543210 с индексами: (1:9,2:8,3:7,4:6,5:5,6:4,7:3,8:2,9:1,10:0)(1:9,2:8,3:7,4:6,5:5,6:4,7:3,8:2,9:1,10:0)(1:9,2:8,3:7,4:6,5:5,6:4,7:3,8:2,9:1,10:0). 1) Однозначные оставшиеся числа, делящиеся на 444: цифры 8,4,08,4,08,4,0 (позиции 2,6,102,6,102,6,10) — всего 333. 2) Двузначные (и более) окончания. Для пары позиций j<kj<kj<k с нужной парой цифр любое подмножество позиций 1,…,j−11,\dots,j-11,…,j−1 можно оставить или зачеркнуть (чтобы последние две цифры были именно j,kj,kj,k), значит вклад каждой такой пары равен 2 j−12^{\,j-1}2j−1. Подсчёт пар даёт для каждого jjj числа mjm_jmj пар справа: m=(2,2,2,2,1,1,1,1,0)m=(2,2,2,2,1,1,1,1,0)m=(2,2,2,2,1,1,1,1,0) для j=1,…,9j=1,\dots,9j=1,…,9. Тогда количество таких чисел ∑j=19mj2 j−1=2⋅1+2⋅2+2⋅4+2⋅8+1⋅16+1⋅32+1⋅64+1⋅128+0⋅256=270.
\sum_{j=1}^9 m_j2^{\,j-1} =2\cdot1+2\cdot2+2\cdot4+2\cdot8+1\cdot16+1\cdot32+1\cdot64+1\cdot128+0\cdot256=270. j=1∑9mj2j−1=2⋅1+2⋅2+2⋅4+2⋅8+1⋅16+1⋅32+1⋅64+1⋅128+0⋅256=270. Итоговое количество различных получаемых чисел, делящихся на 444: 270+3=273.
270+3=273. 270+3=273.
Число 987654321098765432109876543210 с индексами: (1:9,2:8,3:7,4:6,5:5,6:4,7:3,8:2,9:1,10:0)(1:9,2:8,3:7,4:6,5:5,6:4,7:3,8:2,9:1,10:0)(1:9,2:8,3:7,4:6,5:5,6:4,7:3,8:2,9:1,10:0).
1) Однозначные оставшиеся числа, делящиеся на 444: цифры 8,4,08,4,08,4,0 (позиции 2,6,102,6,102,6,10) — всего 333.
2) Двузначные (и более) окончания. Для пары позиций j<kj<kj<k с нужной парой цифр любое подмножество позиций 1,…,j−11,\dots,j-11,…,j−1 можно оставить или зачеркнуть (чтобы последние две цифры были именно j,kj,kj,k), значит вклад каждой такой пары равен 2 j−12^{\,j-1}2j−1. Подсчёт пар даёт для каждого jjj числа mjm_jmj пар справа: m=(2,2,2,2,1,1,1,1,0)m=(2,2,2,2,1,1,1,1,0)m=(2,2,2,2,1,1,1,1,0) для j=1,…,9j=1,\dots,9j=1,…,9. Тогда количество таких чисел
∑j=19mj2 j−1=2⋅1+2⋅2+2⋅4+2⋅8+1⋅16+1⋅32+1⋅64+1⋅128+0⋅256=270. \sum_{j=1}^9 m_j2^{\,j-1}
=2\cdot1+2\cdot2+2\cdot4+2\cdot8+1\cdot16+1\cdot32+1\cdot64+1\cdot128+0\cdot256=270.
j=1∑9 mj 2j−1=2⋅1+2⋅2+2⋅4+2⋅8+1⋅16+1⋅32+1⋅64+1⋅128+0⋅256=270.
Итоговое количество различных получаемых чисел, делящихся на 444:
270+3=273. 270+3=273.
270+3=273.