Геометрия «счастливых» билетов

72

ких последовательных натуральных чисел.
4. В клетках шахматной доски произвольным образом расставлены числа 1, 2, 3,…,64. Доказать, что найдется по крайней мере три квадрата $2 \times 2$, сумма чисел в каждой из которых больше 100.
5. Доказать, что если $a, b, c$ — стороны произвольного треугольника, то $a^2 + b^2 + c^2 < 2(ab + ac + bc)$.
6. Сколько существует параллелепидов, все грани которых — одинаковые ромбы с острым углом $a$? Найти отношение наобъем таких параллелепидов к наименшему.
Информация

1. Разработать алгоритм и написать (на любом языке программирования) программу, выбирающую из произвольной последовательности целых чисел сначала все положительные числа в порядке возрастания, затем все отрицательные числа в порядке убывания.
2. Разработать обучающие-контроллерную программу по теме «Закон Кулона». Реализовать ее на любом языке программирования.
3. Автомат по продаже газированной воды сbstроенным в него микропроцессором должен работать следующим образом:
   В ответстве монетприемника опускают одна или несколько монет общим достоинством от 1 до 6 коп. После этого нажмите одна из трех кнопок: «Без сиропа — 1 коп.», «С сиропом — 3 коп.», «С двойным сиропом — 5 коп.».
   Автомат определяет сумму поступившей мелочки, если ее достагоно, то распределет монеты по соответствующим бункерам (для 1, 2, 3 и 5-копечных монет), наполняет стакан водой, выдает сдачу и возвращается в исходное состояние; если денег не достаточно, то автомат их возвращает.
   Описать алгоритм работы микропроцессора,bstроенного в автомат. Нapisать (на любом языке программирования) программу, реализующую этот алгоритм.
   В. Н. Сердеев

Геометрия «счастливых» билетов

В статье В. Г. Болтянского «Программы перебора» («Квант», № 1) рассматривается задача определения числа «счастливых» билетов, т. е. шестизначных чисел, у которых сумма первых трех цифр равна сумме остальных. Эта задача сводится к подсчету количества трехначных чисел с заданной суммой цифр S. Из приведенного в статье описания алгоритма следует, что первый две цифры числа $K$ и $L$ должны удовлетворять следующим неравенствам:
$$0 \leq K \leq 9, \quad 0 \leq L \leq 9, \quad K + L \leq S, \quad K + L \geq S - 9.$$
Заметим, что вместе последнего неравенства в программе В. Г. Болтянского (см. с. 7) содержится ошибочное; строка 70 должна иметь следующий вид:
$$70 \text{ IF } K + L > S - 10 \text{ THEN } Q = Q + 1$$
Отметим на координатной плоскости $OKL$ точки с координатами $(K, L)$, удовлетворяющие выписанным выше условиям. Если $S \leq 9$, то соответствующие точки образуют треугольник (рис. 1). Если $S > 9$ (но $S$ не больше 17) — шестиугольник (рис. 2). Расматривая число «допустимых» точки $Q(S)$ в порядке
$$S \quad 0 \quad 1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \quad 9 \quad 9 \quad 10 \quad 11 \quad 12 \quad 13$$
$Q(S) = Q(S - 1) + S + 1.$
Если $S > 9$, то из общего числа 100 точек квадрата следует вычесть количество точки в левом нижнем ($Q(S - 10)$) и правом верхнем ($Q(S - 17)$) треугольниках.

Поскольку $Q(0) = 1$, можно последовательно определить $Q(1), Q(2), \dots, Q(9)$ и выписать их в таблицу. Используя полученные элементы, вычислим $Q(S)$ для $S$ от 10 до 13 и заполним таблицу до конца.

Телерь, следуя алгоритму В. Г. Болтянского, возвращает квадрою $Q(S)$ в квадрат, просуммирует эти значения и удаляет результат. Не забудем вычесть 1 — билета с номером 000 000 не существует,— и мы получим результат: число счастливых билетов равно 55 251. Простые геометрические соображения настоящего коократили перебор, что мы обошлись без ЭВМ!

Г. Н. Гуртман