комбинаторика, число способов, счастливые билеты

[daogiauvang]

1 Сколькими способами можно выбрать 3 числа среди натуральных чисел от 1 до 100 сумма которых делится на 3.
2.Автобусные билеты имеют номера от 000000 до 999999.
Сколько среди них счастливых то есть таких , у которых сумма трех первых цифр равна сумме трех последних?

[Nilenbert]

2.Счастливые билеты

(Оффтоп)

P.S. А почему у вас аватар похож на аватар Дария Гринберга?

[Бодигрим]

daogiauvang в сообщении #144986 писал(а):

1 Сколькими способами можно выбрать среди натуральных чисел от 1 до 100 сумма которых делится на 3.

Выбрать что?

[PAV]

1. Числа выбираются с повторами или без?

В любом случае, можно вычислить в указанном диапазоне количество чисел, дающих при делении на 3 остатки 0, 1, 2. Затем рассмотреть все возможные комбинации, там уже легко перебрать.

[daogiauvang]

PAV писал(а):

1. Числа выбираются с повторами или без?

В любом случае, можно вычислить в указанном диапазоне количество чисел, дающих при делении на 3 остатки 0, 1, 2. Затем рассмотреть все возможные комбинации, там уже легко перебрать.

нет, числа выбираются не с повторами.
Но пример: 1,2,3; 1,2,6 можно но 1,4,1 невозможно

[Батороев]

daogiauvang писал(а):

2.Автобусные билеты имеют номера от 000000 до 999999.
Сколько среди них счастливых то есть таких , у которых сумма трех первых цифр равна сумме трех последних?

А вот интересно, сколько среди них билетов "очень счастливых", т.е. одновременно "счастливых" и "счастливых по-московски" (сумма цифр, стоящих на чётных местах, равна сумме цифр, стоящих на нечётных местах)?

[Бодигрим]

Батороев в сообщении #145126 писал(а):

А вот интересно, сколько среди них билетов "очень счастливых", т.е. одновременно "счастливых" и "счастливых по-московски" (сумма цифр, стоящих на чётных местах, равна сумме цифр, стоящих на нечётных местах)?

6700
Складывая уравнения $a_1+a_2+a_3=a_4+a_5+a_6$ и $a_1+a_3+a_5 = a_2+a_4+a_6$, получим $ 2a_1+a_2+2a_3+a_5 = a_2+2a_4+a_5+2a_6 $. После очевидных преобразований получим условие $a_1+a_3=a_4+a_6$. Сравнивая его с исходными уравнениями, имеем $a_2=a_5$.

Таким образом, число очень счастливых билетов "третьего порядка" есть произведения числа счастливых билетов второго порядка на число счастливых билетов первого порядка. $670 \cdot 10 = 6700$.

Добавлено спустя 6 минут 21 секунду:

Вообще, пусть $h(n)$ число счастливых билетов порядка $n $ (т. е. состоящих из $2n$ цифр), а $H(n)$ - число очень счастливых билетов того же порядка. Тогда $ H(2k+1) = h(k+1)h(k) $ и $ H(2k) = (h(k))^2 $.

[General]

daogiauvang в сообщении #144986 писал(а):

1 Сколькими способами можно выбрать 3 числа среди натуральных чисел от 1 до 100 сумма которых делится на 3.

Вот такой наводящий вопрос:
Первые 2 числа можно выбрать произвольно, это 100*99 способов. А как быть с третьим?

[bot]

PAV в сообщении #145111 писал(а):

1. Числа выбираются с повторами или без?

daogiauvang в сообщении #145120 писал(а):

Но пример: 1,2,3; 1,2,6 можно но 1,4,1 невозможно

Недоговорённость осталась: а 1,2,3 и 2,3,1 - это одно и то же?

А PAV уж давно в сообщении #145111 писал(а):

В любом случае, можно вычислить в указанном диапазоне количество чисел, дающих при делении на 3 остатки 0, 1, 2. Затем рассмотреть все возможные комбинации, там уже легко перебрать.

В случае положительного ответа на мой вопрос (то есть тройки считаем как множества - неупорядоченными) из этого указания сразу пишется ответ:

$\binom{34}{3}+2\binom{33}{3}+34\cdot33^2$

В случае упорядоченных троек тоже несложно:
Сдвигаем диапазон вниз на единицу и превращаем его в 0, ... , 99 и рассмтриваем эти числа как цифры. Тогда тройку цифр можно считать не более чем трёхзначным числом в системе счисления с основанием 100. Поскольку $100 \equiv 1 \pmod 3$, то признак делимости на 3 здесь такой же, что и в десятичной системе. Каждое третье число делится на 3 и всего таких чисел $\frac{100^3+2}{3}$. Если бы повторы допускались, то это был бы ответ. А иначе числа с повторами надо выбросить - их количество посчитать несложно, опять же по указанию PAVa.

[Батороев]

Бодигрим писал(а):

Таким образом, число очень счастливых билетов "третьего порядка" есть произведения числа счастливых билетов второго порядка на число счастливых билетов первого порядка. $670 \cdot 10 = 6700$.

Почему то перебором у меня получилось $ 8360 $ очень счастливых билетов.

[Бодигрим]

Батороев в сообщении #145378 писал(а):

Почему то перебором у меня получилось 8360 очень счастливых билетов.

Я первоначально считал именно перебором - получилось 6700.

[Батороев]

Полученные мною результаты посотенно.
Если трехзначным числам левой части противопоставлять трехзначные числа правой части, то "левым" числам
от $ 0 $ до $99$ можно противопоставить $551$ число правой части.
От $100$ до $199$ - $641$ число.
От $200$ до $299$ - $721$ число.
От $300$ до $399$ - $791$ число.
От $400$ до $499$ - $851$ число.
От $500$ до $599$ - $901$ число.
От $600$ до $699$ - $941$ число.
От $700$ до $799$ - $971$ число.
От $800$ до $899$ - $991$ число.
От $900$ до $999$ - $1001$ число.
ИТОГО: $8360$

[Бодигрим]

Вас не затруднит сбросить на andrew точка lelechenko цербер gmail ком вашу программу и полные результаты ее работы?

[bot]

bot в сообщении #145288 писал(а):

Каждое третье число делится на 3 и всего таких чисел $\frac{100^3-1}{3}.

Ясен пень, на 1 больше - исправил.

[Батороев]

Бодигрим писал(а):

Вас не затруднит сбросить на andrew точка lelechenko цербер gmail ком вашу программу и полные результаты ее работы?

Я считал на бумаге.
В очень счастливом билете трехзначные числа левой и правой частей должны иметь одинаковые остатки по основанию $ 99 $.
Т.к. обратное не верно, то подсчитал из таких чисел количество возможных вариантов и получил таблицу:
По строчкам - диапазоны чисел левой части: $ 0..99; 100..199; 200..299; 300..399; 400..499; 500..599; 600..699; 700..799; 800..899; 900..999 $
По столбцам - последняя цифра числа левой части в указанных выше диапазонах.
$0$ - $ 1; 2; 3; 4; 5; 6; 7; 8; 9; 10 $
$1$ - $ 2; 3; 4; 5; 6; 7; 8; 9; 10; 10 $
$2$ - $ 3; 4; 5; 6; 7; 8; 9; 10; 10; 10 $
$3$ - $ 4; 5; 6; 7*; 8; 9; 10; 10; 10; 10 $
$4$ - $ 5; 6; 7; 8; 9; 10; 10; 10; 10;10 $
$5$ - $ 6; 7; 8; 9; 10; 10; 10; 10; 10; 10 $
$6$ - $ 7; 8; 9; 10; 10; 10; 10; 10; 10; 10 $
$7$ - $ 8; 9; 10; 10; 10; 10; 10; 10; 10; 10 $
$8$ - $ 9; 10; 10; 10; 10; 10; 10; 10; 10; 10 $
$9$ - $10; 10; 10; 10; 10; 10; 10; 10; 10; 10 $

Суммы по столбцам умножил на $10$ и добавил единицу, т.к. числа $ 9; 108; 207; 306; 405; 504; 603; 702; 801; 999 $ имеют $ 11 $ вариантов.

Например, для числа $040$ возможен $ 1 $ вариант - только $ 040 $,
а для числа $ 363$ левой части возможно $ 7* $ вариантов чисел правой части: $ 066; 165; 264; 363; 462; 561; 660 $.