Элементарный вопрос по элементарной комбинаторике

[Xenia1996]

Сколько существует трёхэлементных подмножеств множества $\{1, 2, 3, \dots , 3000\}$, сумма элементов которых кратна трём?

(Попытка)

Сумма трёх чисел делится на 3, когда либо все три числа имеют одинаковые остатки по модулю 3, либо все три остатка различны.
Таким образом, искомые подмножества имеют вид $\{3k_1, 3k_2, 3k_3\}$, либо $\{3k_1+1, 3k_2+1, 3k_3+1\}$, либо $\{3k_1+2, 3k_2+2, 3k_3+2\}$, либо $\{3k_1, 3k_2+1, 3k_3+2\}$.
В первых трёх случаях имеем по $\binom{1000}{3}$ подмножеств, в последнем - $10^9$. Всего выходит 1498501000.
Но правильный ответ, почему-то, равен 156829490

[gris]

А почему этот ответ правильный? Очень уж он маленький. Примерно для $\{1,2,3...1414\}$ подходит.

[Xenia1996]

gris в сообщении #445547 писал(а):

А почему этот ответ правильный? Очень уж он маленький. Примерно для $\{1,2,3...1414\}$ подходит.

1414 на 3 не делится (сумма цифр не кратна 3), поэтому считать немного по-другому надо.

А правильным я назвала этот ответ потому, что в книжке он назван правильным.

[gris]

Ну не делится и что? Будет 471 число с остатком 0, 471 с остатком 2 и 472 с остатком 1. А методика расчёта — Ваша. Хотя мне проще тупым перебором.

[Circiter]

gris в сообщении #445559 писал(а):

Хотя мне проще тупым перебором.

Прямой перебор для 3000-элементного множества дал результат, полученный Xenia1996 (т.е., 1498501000). Использовался примерно такой алгоритм:

    for(i=1; i<2999; i++)
        for(j=i+1; j<3000; j++)
            for(k=j+1; k<=3000; k++)
                if((i+k+j)%3==0) Result++;

Ответ 156829490 же действительно какой-то подозрительный... Для множества из 1414 элементов ответом будет число 156730902, а для 1415-элементного множества -- уже 157063899, перескочили. :)

[gris]

Вы действительно перебрали все тройки?
Ну на компе это ещё куда ни шло. Я то врукопашную, почти в уме . Ну, конечно, не все, а статистически. Просто выбрал несколько случайных троек и заценил, сколько там среди них подходищих. Ну и пропорцией. Точность, конечно, не высокая, но хотя бы порядок оценить можно. У меня получилось 2 миллиарда, что, в общем, неплохо приближает ответ.

[Circiter]

2gris

Цитата:

Я то врукопашную, почти в уме

Ничего себе. У меня от вышеприведенного кода компьютер "подвис" почти на две секунды! А ну да, вы же проверили подмножество, а потом просто проэкстраполировали результат с использованием соображений пропорциональности... Даже не знал, что так можно. :)

Цитата:

Вы действительно перебрали все тройки?

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