Combinatorics problem: How many ways can you choose three numbers from the range from 1 to 300 so that their sum is divisible by 3?

Question

Combinatorics problem: How many ways can you choose three numbers from the range from 1 to 300 so that their sum is divisible by 3?

I came across one problem on the test-first of all, I do not understand from what field, either from combinatorics, or dynamic programming ... (but I'm more inclined that the combinatorial)

There are numbers from 1, 2, 3 ... 300

How many ways can you choose from them 3 numbers such that their sum is divisible by 3 ?

My thoughts:

Number of ways to choose any 3 numbers from 300 it is clear that these are combinations of 3 of 300 - C(3, 300)

But how now calculate the number of samples only for those whose sum is divisible by 3 ??

Well, such numbers have the form 3*(i + j + k) for example, and what to do next ??

Did I choose the right direction in the solution ?

1

c++алгоритм комбинаторика

Author: jfs, 2017-04-20

Source

2 answers

score 4 · Answer 1

Once with repetitions, then everything is simple:
the first number is 300 ways. The second number is another 300. Total - 90,000. The third number is 100 ways - those that have the desired remainder when divided by 3. Total-9000000 ways.

Direct search is confirmed by :)

Here is the code

int main(int argc, const char * argv[])
{
    int total = 0;
    for(int i = 1; i <= 300; ++i)
        for(int j = 1; j <= 300; ++j)
            for(int k = 1; k <= 300; ++k)
                if ((i+j+k)%3 == 0) ++total;

    cout << total << endl;
}

Gives the required 9000000

No repetitions-just to resolve disputes -

int main(int argc, const char * argv[])
{
    int total = 0;
    for(int i = 1; i <= 300; ++i)
        for(int j = i+1; j <= 300; ++j)
            for(int k = j+1; k <= 300; ++k)
                if ((i+j+k)%3 == 0) ++total;

    cout << total << endl;
}

Gives 1485100. You can evaluate this number - 3 numbers can be selected 300*299*298/6! = 455100 ways, of which about a third will be needed-1485033 (once again, this is a score, not an exact answer.

P.S. It is only necessary to clarify-repetitions of the same numbers are considered the same or not? I considered them different. That is, I actually estimate the probability that when sampling three numbers with a return to the sample, there will be a number divisible by 3.

score 2 · Answer 2

If we assume that repetitions of the terms are allowed, but the variants obtained by permuting the terms are not considered different, then you can make a sum divisible by 3 from the three terms only in one of the following ways

All terms give a remainder of 0 when divided by 3
All terms give the remainder 1 when divided by 3
All terms give the remainder 2 when divided by 3
The summands give the residuals 0, 1, 2 when divided by 3

Quantity options in each of the first three groups - the number of combinations with repetitions of 3 of them 100 = (100 + 3 - 1)!/(3! * 99!) = 171700

Number of variants of the fourth group = 100 * 100 * 100 = 1000000

Total: 1515100

A head-on check gives the same result: http://coliru.stacked-crooked.com/a/1578d2a7db5da0d9