There is a car race where there will be a couple of cars and the cars are numbered from $1$ to $X$, not necessarily incrementally but all distinct positive integers. But strangely all possible sums of $10$ car numbers cannot be divided by $10$.
If that's the case,
What is the maximum possible number of cars in the race?
The answer is
18. In fact, if 10 were replaced by a general $n$ I think the answer would be $2n-2$.
Upper bound
Theorem:
there must be less than 19 cars.
Proof:
Assume there are at least 19.
Pick any 3 cars, and note that 2 of these numbers must have the same parity. Remove those 2 cars from the race, pick another 3 from the remaining 17, and choose 2 with the same parity again. Keep going until we have 9 pairs of cars such that the sum of numbers for each pair is even.
It will suffice to prove that among 9 (even) numbers, there must be a subset of size 5 whose sum is a multiple of 5.
This can be shown by some long arguments involving examining each possible case and congruence class individually, or by using the proof (valid with 5 replaced by a general prime) posted by Barukh here.
Lower bound
Shown by Glorfindel in his answer.
Let's brute force this; start with
9 numbers ending on 1, e.g. 1, 11, 21, 31, 41, 51, 61, 71 and 81. Now, we cannot add another number ending in 1. But we can add a few ending in 2; each sum we can make has $a$ '2s' and $10-a$ '1s', so its last digit is $a$. As long as we have 9 numbers ending on 2, $1 \le a \ge 9$ and the sum won't be divisible by 10. We cannot add more numbers; if we add a single car number ending in $x$, we can take $b$ car numbers ending on 2, $9-b$ ending on 1 and $x$ to produce a sum which is equal to $9 + b + x \pmod {10}$, so just choose $b = 1-x$ (if $x=0,1$) or $b = 11-x$.
So my answer is
18.
Let each car type belong to a particular digit between $0$ and $9$, which represents the remainder after dividing by $10$.
As we already have a solution for $n=18$, namely:
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
we consider $n=19$.
If the number of different car types used was say $6$, a typical selection might be:
0 2 5 6 7 9
and therefore $\binom{10}{6}$ in total.
In general, $k$ car types have $\binom{10}{k}$ options.
Because we cannot have $10$ or more of one car type, $k$ is at least $3$ by the Pigeonhole Principle, and at most $10$ by the number of car types.
As we have $19$ cars in all, we place a $k$-weak composition of $19$, with the additional restraint that no part is greater than $9$, on top of a $k$-selection, and this gives us the numbers of cars at our disposal. (A weak composition allows $0$'s in the expansion, e.g. $1+3+6+1+0+8=19, k=6$). There are $\binom{18+k}{k-1}$ of these.
So, using our examples, we have the following cars:
0 2 5 6 7 9 : car type
1 3 6 1 0 8 : count
and in full:
0 2 2 2 5 5 5 5 5 5 6 9 9 9 9 9 9 9 9
We need to find a subset of $10$ cars that sum to a multiple of $10$, otherwise we have found $19$ cars that don't have such a subset.
Now list all the $k$-weak compositions of $10$ ($\binom{9+k}{k-1}$), and apply this to each possibility. If a part of the $10$-weak composition is greater than the corresponding part of the $19$-weak composition, this can be immediately rejected. Otherwise, do the sum to see if the result is a multiple of $10$.
If we find a single failure, then $n\ge19$.
Our example can become:
0 2 5 6 7 9 : car type
1 3 6 1 0 8 : count
1 1 1 3 3 1 : sum
which immediately fails, or
0 2 5 6 7 9 : car type
1 3 6 1 0 8 : count
1 1 5 0 0 3 : sum
gives $0+2+5+5+5+5+5+9+9+9=56$, but this is not a counter-example for the whole car selection as we need to test all of the possible sums.
The total number of cases that therefore need to be examined is:
$$\sum\limits_{k=3}^{10} \binom{10}{k}\binom{18+k}{k-1}\binom{9+k}{k-1}$$
which is $2,384,504,435,280$ according to Wolfram Alpha.
However, as soon as a selection returns a multiple of $10$, it can be discounted. There are:
$$\sum\limits_{k=3}^{10} \binom{10}{k}\binom{18+k}{k-1}\\=91,466,550$$
of these. (Wolfram Alpha)
