New Year's Countdown Day 13: Unlucky Number

Probability Level 3

Find the smallest positive integer $N$ such that any subset of size $N$ taken from the set of the first 2017 positive integers will always include at least two integers that differ by exactly 13.

The answer is 1015.

1 solution

Arjen Vreugdenhil
Dec 12, 2017

Let $n$ be included precisely if $\left\lfloor\dfrac {n-1}{13}\right\rfloor$ is even.

It is then easy to check that if $n$ is included in the set, then $n \pm 13$ are not included.

This set contains 78 blocks of 13 integers, or 1014 integers: $\{1,2,3,\dots,13;\ 27,28,29,\dots,39;\ 53,54,55,\dots,65; \dots; 2003,2004,2005,\dots,2015\}$

This is a maximal set; adding any more numbers in the given range will cause two to have a difference of 13. Therefore the answer is $1014 + 1 = \boxed{1015}$ .

Note : I have not given a proof that no better set could be found. Any takers?

Note : Another intuitive approach is to include precisely all odd numbers. However, in that case, any 1010th number added will be even and at distance 13 from one of an odd number.

There's an easy argument that your set is maximal. Consider all the numbers are that are congruent to 1 modulo 13: $1, \ 14, \ 27, \ 40, \ 53, \ \dots, \ 2016.$ There are 156 elements in this list. You cannot take any two elements that are consecutive in this list, so you can have at most $156/2 = 78$ elements from this list. The other residues work similarly.

Jon Haussmann - 3 years, 5 months ago

My set indeed excludes all even-numbered entries in the sequence $(n, 13+n, 26+n, \dots)$ for $n = 1\dots 13$ .

With this argument, we end up excluding $2\times 78 + 11\times 77 = 1003$ numbers from the list of 2017, leaving $1014$ as the maximum size.

Thanks!

Arjen Vreugdenhil - 3 years, 5 months ago

New Year's Countdown Day 13: Unlucky Number

The answer is 1015.

1 solution

0 pending reports