Вопросы о количестве билетов

Самым простым вопросом в этой "опере" является вопрос о количество счастливых чисел в интервале определенной длины. Наприме, "Сколько счастливых чисел может уместиться в интервал длиной 50 чисел?" или "Существует ли 4 последовательных счастливых числа в интервале длиной 30 чисел?".

Для начала, давайте попробуем выяснить, какие вообще бывают интервалы между двумя последовательными счастливыми числами:

In[]

S = set()
for i in range(1, len(N)):
    S.add(int(N[i])-int(N[i-1]))
print(S)

Out[]

{65, 36, 38, 9, 74, 139, 47, 175, 18, 83, 157, 56, 121, 27, 92, 29, 222}

Информации не так много, как хотелось бы. Давайте хоть взглянем на эти разности, может быть они возрастают линейно?

In[]

S = list(S)
S.sort()
%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(S)
plt.show()

Визуализация разности между значениями чисел соседних счастливых билетов

Что ж, это интересно, но давайте вернемся к другим вопросам. Например, какие именно счастливые числа дают разность равную 9 или 175. Для этого попробуем сделать словарь, в котором ключами будет разность, а значениями – числа, дающие эту самую разность.

In[]

import pprint    #  модуль для "красивой печати"

k = list(diff.keys())
k.sort()

for i in k:
    print('\nРазность равную ' + str(i),
          ' дают следующие пары билетов:', )
    
    #  Сделаем вывод длинющего списка компактным:
    pprint.pprint(diff[i], compact = True)

Out[]

Разность равную 9  дают следующие пары билетов:
[(1432, 1423), (1634, 1625), (1643, 1634), (1652, 1643), (1735, 1726),
 (1762, 1753), (1836, 1827), (1845, 1836), (1854, 1845), (1863, 1854),
 (1872, 1863), (1937, 1928), (1946, 1937), (1973, 1964), (1982, 1973),
 (2314, 2305), (2350, 2341), (2415, 2406), (2460, 2451), (2516, 2507),
 (2543, 2534), (2570, 2561), (2617, 2608), (2680, 2671), (2718, 2709),
 (2745, 2736), (2754, 2745), (2763, 2754), (2790, 2781), (2846, 2837),
 (2873, 2864), (2947, 2938), (2956, 2947), (2965, 2956), (2974, 2965),
 (2983, 2974), (3021, 3012), (3214, 3205), (3250, 3241), (3416, 3407),
 (3425, 3416), (3461, 3452), (3470, 3461), (3517, 3508), (3526, 3517),
 (3571, 3562), (3580, 3571), (3618, 3609), (3627, 3618), (3654, 3645),
 (3681, 3672), (3690, 3681), (3728, 3719), (3791, 3782), (3856, 3847),
 (3865, 3856), (3874, 3865), (3957, 3948), (3984, 3975), (4132, 4123),
 (4215, 4206), (4260, 4251), (4316, 4307), (4325, 4316), (4361, 4352),
 (4370, 4361), (4518, 4509), (4527, 4518), (4536, 4527), (4572, 4563),
 (4581, 4572), (4590, 4581), (4628, 4619), (4637, 4628), (4682, 4673),
 (4691, 4682), (4738, 4729), (4765, 4756), (4792, 4783), (4967, 4958),
 (4976, 4967), (4985, 4976), (5023, 5014), (5032, 5023), (5041, 5032),
 (5216, 5207), (5243, 5234), (5270, 5261), (5317, 5308), (5326, 5317),
 (5371, 5362), (5380, 5371), (5418, 5409), (5427, 5418), (5436, 5427),
 (5472, 5463), (5481, 5472), (5490, 5481), (5638, 5629), (5647, 5638),
 (5683, 5674), (5692, 5683), (5748, 5739), (5793, 5784), (5876, 5867),
 (6024, 6015), (6051, 6042), (6134, 6125), (6143, 6134), (6152, 6143),
 (6217, 6208), (6280, 6271), (6318, 6309), (6327, 6318), (6354, 6345),
 (6381, 6372), (6390, 6381), (6428, 6419), (6437, 6428), (6482, 6473),
 (6491, 6482), (6538, 6529), (6547, 6538), (6583, 6574), (6592, 6583),
 (6758, 6749), (6794, 6785), (6987, 6978), (7025, 7016), (7034, 7025),
 (7043, 7034), (7052, 7043), (7061, 7052), (7135, 7126), (7162, 7153),
 (7218, 7209), (7245, 7236), (7254, 7245), (7263, 7254), (7290, 7281),
 (7328, 7319), (7391, 7382), (7438, 7429), (7465, 7456), (7492, 7483),
 (7548, 7539), (7593, 7584), (7658, 7649), (7694, 7685), (8026, 8017),
 (8035, 8026), (8062, 8053), (8071, 8062), (8136, 8127), (8145, 8136),
 (8154, 8145), (8163, 8154), (8172, 8163), (8246, 8237), (8273, 8264),
 (8356, 8347), (8365, 8356), (8374, 8365), (8576, 8567), (9027, 9018),
 (9036, 9027), (9045, 9036), (9054, 9045), (9063, 9054), (9072, 9063),
 (9081, 9072), (9137, 9128), (9146, 9137), (9173, 9164), (9182, 9173),
 (9247, 9238), (9256, 9247), (9265, 9256), (9274, 9265), (9283, 9274),
 (9357, 9348), (9384, 9375), (9467, 9458), (9476, 9467), (9485, 9476),
 (9687, 9678)]

Разность равную 18  дают следующие пары билетов:
[(1423, 1405), (1450, 1432), (1524, 1506), (1542, 1524), (1560, 1542),
 (1625, 1607), (1670, 1652), (1726, 1708), (1753, 1735), (1780, 1762),
 (1827, 1809), (1890, 1872), (1964, 1946), (2534, 2516), (2561, 2543),
 (2635, 2617), (2653, 2635), (2671, 2653), (2736, 2718), (2781, 2763),
 (2837, 2819), (2864, 2846), (2891, 2873), (3645, 3627), (3672, 3654),
 (3746, 3728), (3764, 3746), (3782, 3764), (3847, 3829), (3892, 3874),
 (3975, 3957), (4031, 4013), (4123, 4105), (4150, 4132), (4756, 4738),
 (4783, 4765), (4857, 4839), (4875, 4857), (4893, 4875), (5124, 5106),
 (5142, 5124), (5160, 5142), (5234, 5216), (5261, 5243), (5867, 5849),
 (5894, 5876), (5986, 5968), (6042, 6024), (6125, 6107), (6170, 6152),
 (6235, 6217), (6253, 6235), (6271, 6253), (6345, 6327), (6372, 6354),
 (7126, 7108), (7153, 7135), (7180, 7162), (7236, 7218), (7281, 7263),
 (7346, 7328), (7364, 7346), (7382, 7364), (7456, 7438), (7483, 7465),
 (8053, 8035), (8127, 8109), (8190, 8172), (8237, 8219), (8264, 8246),
 (8291, 8273), (8347, 8329), (8392, 8374), (8457, 8439), (8475, 8457),
 (8493, 8475), (8567, 8549), (8594, 8576), (9164, 9146), (9375, 9357),
 (9586, 9568)]

Разность равную 27  дают следующие пары билетов:
[(1230, 1203), (2130, 2103), (2341, 2314), (3241, 3214), (3452, 3425),
 (4352, 4325), (4563, 4536), (5463, 5436), (5674, 5647), (6574, 6547),
 (6785, 6758), (7685, 7658), (7896, 7869), (8796, 8769)]

Разность равную 29  дают следующие пары билетов:
[(1809, 1780), (2709, 2680), (2819, 2790), (3012, 2983), (3609, 3580),
 (3719, 3690), (4013, 3984), (4619, 4590), (5014, 4985), (5409, 5380),
 (6015, 5986), (6309, 6280), (6419, 6390), (7016, 6987), (7209, 7180),
 (7319, 7290), (8219, 8190)]

Разность равную 36  дают следующие пары билетов:
[(1340, 1304), (2451, 2415), (3140, 3104), (3562, 3526), (4251, 4215),
 (4673, 4637), (5362, 5326), (5784, 5748), (6473, 6437), (6895, 6859),
 (7584, 7548), (8695, 8659)]

Разность равную 38  дают следующие пары билетов:
[(1708, 1670), (1928, 1890), (2608, 2570), (3508, 3470), (3829, 3791),
 (4729, 4691), (5308, 5270), (6208, 6170), (6529, 6491), (7429, 7391),
 (8109, 8071), (8329, 8291)]

Разность равную 47  дают следующие пары билетов:
[(1607, 1560), (2507, 2460), (2938, 2891), (4307, 4260), (4839, 4792),
 (5207, 5160), (5739, 5692), (7108, 7061), (7539, 7492), (8439, 8392),
 (9128, 9081)]

Разность равную 56  дают следующие пары билетов:
[(1506, 1450), (2406, 2350), (3948, 3892), (4206, 4150), (5849, 5793),
 (6107, 6051), (7649, 7593), (8549, 8493), (9238, 9182)]

Разность равную 65  дают следующие пары билетов:
[(1405, 1340), (3205, 3140), (4958, 4893), (5106, 5041), (6859, 6794),
 (8659, 8594), (9348, 9283)]

Разность равную 74  дают следующие пары билетов:
[(1304, 1230), (4105, 4031), (5968, 5894), (8769, 8695), (9458, 9384)]

Разность равную 83  дают следующие пары билетов:
[(3104, 3021), (6978, 6895), (9568, 9485)]

Разность равную 92  дают следующие пары билетов:
[(9678, 9586)]

Разность равную 121  дают следующие пары билетов:
[(2103, 1982), (8017, 7896)]

Разность равную 139  дают следующие пары билетов:
[(4509, 4370), (5629, 5490)]

Разность равную 157  дают следующие пары билетов:
[(3407, 3250), (6749, 6592)]

Разность равную 175  дают следующие пары билетов:
[(2305, 2130), (7869, 7694)]

Разность равную 222  дают следующие пары билетов:
[(9018, 8796)]

Чтож, теперь мы знаем какая может быть разность между подряд идущими счастливыми числами. А какой она может быть если, взять числа идущие через один?

In[]

S = set()
for i in range(2, len(N)):
    S.add(int(N[i])-int(N[i-2]))

S = list(S)
S.sort()

print(S)

Out[]

[18, 27, 36, 38, 45, 47, 56, 65, 74, 83, 92, 101, 110, 119, 130, 148, 166, 184, 202, 231, 249]

Снова не так уж и много вариантов. Мы не будем выводить на экран все "тройки" чисел дающие соответствующие разности, так как мы уже знаем, что это скорее всего будет очень громоздко. Мы просто выведем рядом с соответствующей разностью количество таких "троек":

In[]

diff_3 = {}

for i in range(2, len(N)):
    
    d = int(N[i])-int(N[i-2])
    
    if d not in diff_3:
        diff_3[d] = 1
        
    else:
        diff_3[d] += 1

k = list(diff_3.items())
k.sort()        
        
pprint.pprint(k, compact = True)

Out[]

[(18, 92), (27, 92), (36, 36), (38, 26), (45, 16), (47, 24), (56, 24), (65, 20),
 (74, 16), (83, 8), (92, 8), (101, 10), (110, 4), (119, 2), (130, 2), (148, 6),
 (166, 4), (184, 2), (202, 2), (231, 2), (249, 2)]

И так, мы видим, что существует целых 92 "тройки" счастливых чисел, в которых разность крайних из них не превосходит 20.

А давайте посмотрим разность счастливых чисел между которыми располагается 2 других:

In[]

diff_4 = {}

for i in range(3, len(N)):
    
    d = int(N[i])-int(N[i-3])
    
    if d not in diff_4:
        diff_4[d] = 1
        
    else:
        diff_4[d] += 1

k = list(diff_4.items())
k.sort()        
        
pprint.pprint(k, compact = True)

Out[]

[(27, 42), (36, 56), (45, 48), (47, 25), (54, 24), (56, 34), (65, 36), (74, 22),
 (83, 24), (92, 20), (101, 14), (110, 6), (119, 4), (121, 4), (128, 2),
 (137, 2), (139, 2), (157, 8), (175, 6), (184, 2), (193, 4), (211, 4), (240, 2),
 (258, 2), (323, 4)]

Теперь представим, что мы сидим на экзамене и нам нужно ответить на вопрос: "Есть ли последовательность из 30 натуральных чисел среди которых имеется 4 счастливых билета?". И как нам быть? Вручную выполнять все предыдущие скрипты??? На самом деле здесь не так уж много работы. Нам достаточно оптимизировать перебор с помощью нехитрых умозаключений.


Ручной перебор

Для начала разберемся с обозначениями. В алгебре мы привыкли обозначать числа буквами, например \(a\) может принимать любые значения, например \(1\), \(77\) или \(3,14\). Но в нашем случае речь идет об отдельных цифрах числа и такой контекст должен быть отражен в обозначении. Ничего лучше чем \(\overline{abcd}\), пока не придумано. Тогда наше число может быть записано в такой форме:

$$N = \overline{abcd} = a\cdot 1000 \;+\;b\cdot100\;+\;c\cdot10\;+\;d$$

А условия, которые определяют "счастливость" числа, могут быть записаны вот так:

$$a+b=c+d;\;\;a \neq b \neq d \neq c;\;\; 0\leq a,b,c,d\leq9$$

В принципе, таких обозначений нам уже достаточно, что бы приступить к ручному перебору. Здесь важно понимать, что сам по себе перебор, должен быть аккуратным и оптимальным. Самый простой способ организовать его - это создать таблицу. Напомню, вопрос звучит так: "Есть ли последовательность из 30 натуральных чисел среди которых имеется 4 счастливых билета?"

Левые и правые части счастливых билетов
\(a+b\) и несколько
примеров \(\overline{ab}\)
\(c+d\) и примеры
подходящих \(\overline{cd}\)
\(\overline{01}\) или \(\overline{10}\) И ежу понятно, что в этом случае нет подходящих цифр для составления счастливого билета. Так что в этом случае мы ставим \(\varnothing\) - символ, обозначающий пустое множество. т.е. множество подходящих пар цифр для того что бы продолжить счастливый билет начинающийся с \(\overline{01}\) - не содержит никаких вариантов.
\(\overline{02}\) или \(\overline{20}\) Снова \(\varnothing\). Мы конечно, могли бы написать \(\overline{11}\) но цифры должны быть разными.
\(\overline{03}\) или \(\overline{30}\) А вот здесь мы можем указать два варианта: \(\overline{12}\) и \(\overline{21}\), но их всего два, а нам нужно четыре.
А давайте сразу \(\overline{90}\) напишем Тогда у нас может быть целая куча вариантов: \(\overline{18}\), \(\overline{27}\), \(\overline{36}\), \(\overline{45}\), \(\overline{54}\), \(\overline{63}\), \(\overline{72}\), \(\overline{81}\). Как вы догадались, в этом месте можно остановиться.

В самом деле. У нас получилось 8 счастливых билетов: \(9018\), \(9027\), \(9036\), \(9045\), \(9054\), \(9063\), \(9072\), \(9081\). Разность между \(9045\) и \(9018\) равна 27. А нас как раз и интересует последовательность из \(30\) чисел в которой могут быть расположены четыре счастливых числа. В ответе мы можем указать интервал \([9017; 9047)\). Почему именно полуоткрытый интервал? Потому что если мы укажем вот такой интервал \([9017; 9047]\), аргументируя тем что \(9017-9047=30\) то в нем на самом деле окажется 31 число. Например в интервале \([1; 6]\) не пять чисел а шесть: \(1,2,3,4,5,6\).

В общем, один балл на экзамене можно заработать почти "по халяве". Наверное с этого и стоило начинать. Однако, неудовлетворять свое любопытство, это то же самое, что заставлять голодать свое тело - очень опасное занятие.