2
$\begingroup$

This is a delightful Oxford entrance question from 1993, but I'm stuck on the final bit.

A sequence $$N_1, N_2, N_3, ..., N_{13}$$ of thirteen integers is said to be lucky if every selection of twelve terms from the sequence contains six terms whose combined sum is exactly half the combined sum of the selected twelve. Suppose that the above sequence is lucky.

(i) Prove that, if one of the terms of the sequence is zero, then all thirteen integers are even.

(ii) Show that if $N$ is any integer then the sequence $$N_1-N, N_2-N, N_3-N, ...,N_{13}-N$$ is also lucky.

(iii) Show also that if $k$ is any intger then the sequence $$kN_1, kN_2, kN_3, ..., kN_{13}$$ is lucky.

(iv) Deduce from these findings, or prove otherwise, that $$N_1 = N_2 = N_3 = ... =N_{13}$$


For a lucky sequence, the combined sum of any selection of twelve must be even, as there is a sum that is exactly half of it.

For (i), assuming WLOG $N_{13}=0$, I can demonstrate that since we have a lucky sequence the sum $N_1 + N_2 + ... + N_{12}=2P$ where there is a subset of six terms with sum $P$. For each $N_j,\, j = 1$ to $12$, replaced by $N_{13}$ the sum will again be even. Thus each $N_j,\, j = 1$ to $12$ must be even.

For (ii), any sequence of twelve integer with sum $2P$ has a subset of six integers with sum $P$. 'Mapping' the sequence to the newly formed sequences the sum would be $2P - 12N$ and the subset would be $P - 6N$

For (iii), similarly, any sequence of twelve now has sum $2kP$ and the subset of six would have sum $kP$.

It is part (iv) I'm stuck on.

I can demonstrate that the integers are either all odd, or all even using properties (i) and (ii) but can't see how property (iv) helps me here.

Any thoughts?

$\endgroup$
0
$\begingroup$

You descend through binary expansions. You can adapt your proof of iii to extend $k$ to include the reciprocal of the greatest common divisor of all the numbers. Use ii to subtract off the smallest one, leaving one of the numbers zero. i says they are all even, so all the original numbers had the same bit in the ones place in their binary expansions. Now all the numbers are even, so our extended iii says we can divide them all by $2$. Repeat the argument and you find that all the numbers have the same bit in the twos place.

Added, an easier approach: Assume there are any solutions where not all the numbers are equal. There must be one or a family where the difference between the two smallest numbers is minimal. Put the numbers in increasing order. Now subtract the smallest from all the numbers, so we have $N_1=0, N_2$ is positive and the smallest of the rest. By ii they are all even and by our modified iii we can divide them all by $2$. This makes a solution with smaller difference between the smallest numbers, which we assumed does not exist.

$\endgroup$
  • $\begingroup$ So the adapted (iii) allows me to ensure the sequence of numbers are all relatively prime? And I use (ii) to get $0, N_2, N_3, ..., N_{13}$ $\endgroup$ – MrHodgson Dec 9 '18 at 16:12
  • $\begingroup$ You use ii to get $0,N_2-N_1, N_3-N-1,\ldots$ $\endgroup$ – Ross Millikan Dec 9 '18 at 16:20
  • $\begingroup$ Yes, hence all have the same parity but you've lost me at the 'repeat the argument' bit. When I divide them all by two I get a sequence of 12 odd numbers and zero.Ah, so each subsequence partitions the twelve into two groups with equal sums. But for each subsequence that contains a zero I can show that the other six must contain an even number. $\endgroup$ – MrHodgson Dec 9 '18 at 16:22

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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