Weirdly Numbered Cars

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?

• So $X\geqslant 10$? – Mr Pie Jul 28 '18 at 8:46
• But it states that "all possible sum of $10$ car numbers cannot be divided by 10". What if I choose an arbitrary $X < 10$? – Mr Pie Jul 28 '18 at 8:49
• I assume the car numbers are distinct integers (which is rather ... ehm ... natural) and the sum needs to be taken of 10 different car numbers. – Glorfindel Jul 28 '18 at 9:25
• @Glorfindel yes exactly that is what I meant. – Oray Jul 28 '18 at 9:27
• @user477343 $X<10$ wouldn't be the maximum possible, though, would it? – Rand al'Thor Jul 28 '18 at 9:43

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.

• A green tick and no upvote? :-o – Rand al'Thor Jul 28 '18 at 15:39

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$.

18.

• You've shown that you can achieve a certain number of cars by a particular method, and that that particular method won't let you add more cars, but it doesn't look to me as if it shows that no method can allow more cars. – Gareth McCaughan Jul 28 '18 at 9:47
• True, I was aware of that. "final" in this context meant 'at the end of the calculation". – Glorfindel Jul 28 '18 at 10:37

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)