Помните про счастливый билет в автобусе (кто ездил)?
Если сумма первых трех цифр номера билета равна сумме трех последних,то билет счастливый и его можно съесть. А сколько таких билетов существует?
При решении задачи не использовать циклы с перебором.

если цифр в билетике 6, то 1000 билетов (000-999 если есть нулевой номер), или 999 билетов

BSA, условие внимательнее прочти ;o)
никто не спрашивает, сколько может быть вариантов одинаковых номеров в двух трехзначных цифрах

?2*(1^2+3^2+6^2+10^2+15^2+21^2+28^2+36^2+45^2+55^2+63^2+69^2+73^2+75^2)

P.S. Если нулевого билета нет, то надо единичку отнять.



Исправлено 1 раз(а). Последнее : leonid, 07.05.07 14:34

leonid, откуда такой алгоритм? Обоснуй.

dvo
откуда такой алгоритм? Обоснуй.

Это относительно просто.

Сумма 3 цифр может принимать значение от 0 до 27. Значит, сначала надо найти сколько 3-значных чисел при суммировании их цифр дают значение 0, сколько дают значение 1, сколько ... 27.

Поскольку номер билета - это 6-значное число, то каждое найденное значение надо возвести в квадрат.

Например, в сумме, значение 2 будет получено у 6 трех-значных чисел. Чтобы билет был счастливым, каждому из 6 чисел слева может соответствовать одно из 6 чисел справа. Т.е. общее число счастливых билетов, сумма цифр которого равна 2, составляет 6^2 = 36

Отсюда в формуле все возведено в квадрат.

В формуле 14 слагаемых вместо ожидаемых 28 потому, что количество значений сумм от 0 до 13 равно количеству значений сумм от 14 до 27. Просто в первой серии идет возрастание, а во второй - убывание.

Отсюда в формуле 14 слагаемых, сумма которых, впоследствии удваивается.

Вот дальше веселее.

Если сумма трех цифр принимает значение от 0 до 9, то общее количество возможных чисел для каждой суммы определяется по формуле

(N+1)*(N+2)/2

где N - это сумма трех цифр.

Т.е. если сумма трех цифр - это 5, то количество чисел - это (5+1)*(5+2)/2 = 21

Вот на формуле для подсчета количества значений от 10 до 13 я пока "завис". Там сумма не одной, а двух арифметических прогрессий. Вроде бы что-то вроде этого

(19-N)*(N+2)/2 + (N-9)*(28-N)/2

Но пока не уверен, хотя с результатами Леонида - сходится.


Откуда я получил эти формулы? Ну, вот это объяснить сложнее. Скажем так, получены на основании анализа некоторых числовых последовательностей

Вот спасибо! Ни за что бы не сумел так хорошо все это написать. Прочитал - и даже самому понятнее стало.

Кстати, косвенным подтверждением правильности формулы является то, что если убрать возведение в квадрат получим ровно 1000

2*(1+3+6+10+15+21+28+36+45+55+63+69+73+75) = 1000

Это значит, что ничего не потеряли при подсчете. Ведь всего как чисел, так и вариантов может быть ровно 1000 (включая ноль).