Счастливый билет | |
---|---|
dvo Автор Сообщений: 21 Откуда: Воронеж Дата регистрации: 01.01.2005 |
Помните про счастливый билет в автобусе (кто ездил)?
Если сумма первых трех цифр номера билета равна сумме трех последних,то билет счастливый и его можно съесть. А сколько таких билетов существует? При решении задачи не использовать циклы с перебором. |
Re: Счастливый билет | |
---|---|
BSA Сообщений: 193 Дата регистрации: 26.05.2006 |
если цифр в билетике 6, то 1000 билетов (000-999 если есть нулевой номер), или 999 билетов
|
Re: Счастливый билет | |
---|---|
AlexSSS Сообщений: 6113 Откуда: Tallinn, Estonia Дата регистрации: 19.09.2005 |
BSA, условие внимательнее прочти ;o)
никто не спрашивает, сколько может быть вариантов одинаковых номеров в двух трехзначных цифрах |
Re: Счастливый билет | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
?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 |
Re: Счастливый билет | |
---|---|
dvo Автор Сообщений: 21 Откуда: Воронеж Дата регистрации: 01.01.2005 |
leonid, откуда такой алгоритм? Обоснуй.
|
Re: Счастливый билет | |
---|---|
Владимир Максимов Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
Это относительно просто. Сумма 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 Но пока не уверен, хотя с результатами Леонида - сходится. Откуда я получил эти формулы? Ну, вот это объяснить сложнее. Скажем так, получены на основании анализа некоторых числовых последовательностей |
Re: Счастливый билет | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Вот спасибо! Ни за что бы не сумел так хорошо все это написать. Прочитал - и даже самому понятнее стало.
|
Re: Счастливый билет | |
---|---|
Владимир Максимов Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
Кстати, косвенным подтверждением правильности формулы является то, что если убрать возведение в квадрат получим ровно 1000
2*(1+3+6+10+15+21+28+36+45+55+63+69+73+75) = 1000 Это значит, что ничего не потеряли при подсчете. Ведь всего как чисел, так и вариантов может быть ровно 1000 (включая ноль). |
© 2000-2024 Fox Club  |