Архив задач олимпиады по математике и криптографии
Счастливые билеты, 10 кл.
На билетах в кинотеатры Криптоландии проставляется шестизначный номер от (0,0,0,0,0,0) до (6,6,6,6,6,6). При этом используются только цифры 0,1,2,3,4,5,6. Билет считается «счастливым», если остатки от деления на 7 суммы первых трех цифр и суммы последних трех цифр отличаются на фиксированное число k=3. Например, билеты с номерами 123226 и 111661 – счастливые, а с номерами 123000 и 666111 – нет. Найдите число счастливых билетов.
Количество трёхзначных чисел x1 x2 x3, у которых остаток от деления на 7 суммы цифр равен фиксированному значению t∈{0,1,…,6}, равно 72=49, поскольку любые две цифры однозначно определяют третью из соотношения r9 (x1+x2+x3 )=t. Приведём возможные варианты для значений остатков для первой и последней тройки цифр:
(0,3),(1,4),…,(3,6),
(3,0),(4,1),…,(6,3) их число равно 2×4=8, и тогда общее число счастливых билетов равно 2×4×72×72= 2×4×74=19208.