5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ So $X\geqslant 10$? $\endgroup$ – Mr Pie Jul 28 '18 at 8:46
  • $\begingroup$ But it states that "all possible sum of $10$ car numbers cannot be divided by 10". What if I choose an arbitrary $X < 10$? $\endgroup$ – Mr Pie Jul 28 '18 at 8:49
  • $\begingroup$ 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. $\endgroup$ – Glorfindel Jul 28 '18 at 9:25
  • $\begingroup$ @Glorfindel yes exactly that is what I meant. $\endgroup$ – Oray Jul 28 '18 at 9:27
  • $\begingroup$ @user477343 $X<10$ wouldn't be the maximum possible, though, would it? $\endgroup$ – Rand al'Thor Jul 28 '18 at 9:43
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A green tick and no upvote? :-o $\endgroup$ – Rand al'Thor Jul 28 '18 at 15:39
2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Gareth McCaughan Jul 28 '18 at 9:47
  • $\begingroup$ True, I was aware of that. "final" in this context meant 'at the end of the calculation". $\endgroup$ – Glorfindel Jul 28 '18 at 10:37
2
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.