Brilli the Fortune Teller

Clearly, $1 \leq N \leq 49$ and $N$ is an integer. Additionally, $N < 30$ since there exists a counter example for all $N \geq 30$ , e.g. $(1, 2, 3, ... 30)$ .

The $N$ that satisfy the equation can be found by finding the values of $N$ which have a counterexample. We will find this in the following way: Starting with $1$ , list $N$ integers in a row, then skip the next $N$ integers, then list the next $N$ integers, etc. until we reach $50$ . For example, for $N = 17$ , we have $1, 2, 3, ... 17, 35, 36, 37, ... 49, 50$ . If the number of integers in this listing is at least 30, then we have a counter example for that value of $N$ , that is, any 30 element subset of those integers would be a counter example. If it is below 30, then more integers must be added who necessarily have an absolute difference of $N$ with an already listed integer. The number of integers in this sequence can be calculated by the following formulae:

If $\lfloor \frac {50}{N} \rfloor$ is odd, then $\frac {\lfloor \frac{50}{N} \rfloor - 1}{2} N + N \geq 30$

If $\lfloor \frac {50}{N} \rfloor$ is even, then $50 - \lfloor \frac{50}{2N} \rfloor N \geq 30$

Calculation can be facilitated by looking at numbers in groups. For example, when $17 \leq N \leq 25$ , that is, $\lfloor \frac{50}{N} \rfloor = 2$ , plugging it into the equation we get $50 - N \geq 30 \rightarrow N \leq 20$ , meaning that there exists a counter example for $17 \leq N \leq 20$ .

After a bit of calculation we find that $N = 10, 15 \leq N \leq 20, N \geq 30$ have counter examples and, thus, the rest of them do not. Adding the sum of the valid values we get $S_N = 320$ .

Let

$S = \{ 1, 2, 3, \dots, 50 \}.$

If we can make $t$ pairs $(a,b)$ with $t \geq 21$ from the integers from $1$ to $50$ such that $\lvert a - b \rvert = N$ , then by the pigeonhole principle, given any set

$T \subset S \quad \text{ with } \lvert T \rvert = 30,$

there are two integers $p,q \in T$ such that $(p,q)$ is one of those pairs. This is because there are $50 - 2t$ integers not in a pair and thus there are at most

$30 - (50 - 2t) = 2t - 20$

integers in $t$ pairs, and

$t \geq 21 \implies t - 20 \geq 1 \implies 2t - 20 \geq t + 1 > t.$

Therefore, we wish to find the sum of all possible values of $N$ such that we can pair up at least $42$ of the numbers in $S$ such that each two elements of a pair have an absolute difference of $T$ .

Let's denote a succesful set of pairings of at least $21$ pairs for a certain $N$ by $S_N$ . For example,

$S_1 = \{ (1,2), (3,4), (5,6), (7,8), \dots, (41,42) \}.$

Let $V_{N,k}$ be the set of pairs

$(m + k \cdot 2N, m + N + k \cdot 2N) \quad \text{ with } 1 \leq m \leq N.$

For example,

$V_{3,0} = \{ (1,4), (2,5), (3,6) \}$

and

$V_{3,1} = \{ (7,10), (8,11), (9,12) \}.$

Note that $V_{3,0}$ contains $3$ pairs with the integers from $1$ to $6$ such that each pair consists of two integers with an absolute difference of $3$ . Similarly, $V_{3,1}$ contains $3$ pairs with the integers from $7$ to $12$ in that way.

In general, $V_{N,k}$ contains $N$ pairs with the integers from $1 + k \cdot 2N$ to $(k+1) \cdot 2N$ such that each pair consists of two integers with an absolute difference of $N$ .

Let

$W_N = V_{N,0} \cup V_{N,1} \cup V_{N,2} \cup \dots \cup V_{N,x} \quad \text{ with } x = \left\lceil \frac{21}{N} \right\rceil - 1.$

We know that $\lvert V_{N,k} \rvert = N$ for all $k$ , and that $V_{N,a}$ and $V_{N,b}$ are disjoint for all distinct integers $a,b$ , so

$\lvert W_N \rvert = \left\lceil \frac{21}{N} \right\rceil \cdot N \geq \frac{21}{N} \cdot N = 21.$

Note that the largest integer in any pair of $W_N$ is no more than $\lvert W_N \rvert \cdot 2$ . This implies that if $\lvert W_N \rvert \leq \frac{50}{2} = 25$ , then $S_N = W_N$ , because then the largest integer in $W_N$ does not exceed $25 \cdot 2 = 50$ , and as shown above, $W_N \geq 21$ .

If $26 \leq \lvert W_N \rvert \leq 29$ , then we obtain $S_N$ by taking $W_N$ and removing the $2 \cdot \lvert W_N \rvert - 50$ pairs that contain the $2 \cdot \lvert W_N \rvert - 50$ integers in $W_N$ exceeding $50$ , after which we're left with a set containing

$\lvert W_N \rvert - \left( 2 \cdot \lvert W_N \rvert - 50 \right) = 50 - \lvert W_N \rvert \geq 50 - 29 = 21$

pairs, satisfying $S_N \geq 21$ .

So,there exists a set $S_N$ for some $N$ as long as

$\lvert W_N \rvert \leq 29 \implies \left\lceil \frac{21}{N} \right\rceil \cdot N \leq 29 \implies \left\lceil \frac{21}{N} \right\rceil \leq \frac{29}{N}.$

If $N > 29$ , then

$\frac{29}{N} < 1 = \left\lceil \frac{21}{N} \right\rceil,$

so $N \leq 29$ . By simply checking each value, we obtain that

$N \in \{ 1,2,3,\dots,29 \} \setminus \{ 10,15,16,17,18,19,20 \}.$

To check that $N \not = 10$ , consider the set

$\{1,2,3,\dots,10, \quad 21,22,23,\dots,30, \quad 41,42,43,\dots,50 \},$

which contains $30$ integers of which there are no two with an absolute difference of $10$ .

To check that $15 \leq N \leq 20$ is also impossible, consider the set

$\{ 1,2,3,\dots,15, \quad 36,37,38,\dots,50 \},$

which contains $30$ integers of which the absolute difference of two of its elements is either less than $15$ or larger than $20$ .

So, the sum of all possible values of $N$ such that there exists a set $S_N$ and thus the conditions are satisfied is

$\begin{aligned} &(1 + 2 + 3 + \dots + 29) - (10 + 15 + 16 + 17 + 18 + 19 + 20) \\[1em] = &\frac{29 \cdot 30}{2} - 115 \\[1em] = &435-115 \\[1em] = &\boxed{320}. \end{aligned}$

Let $f(X)$ be the size of the largest possible set that has no two integers with difference $N$

We can divide the 50 integers up into $N$ buckets. Here's an example for $N=9$ : $\begin{aligned} 1,&10,19,28,37,46 \\ 2,&11,20,29,38,47\\ 3,&12,21,30,39,48\\ 4,&13,22,31,40,49\\ 5,&14,23,32,41,50\\ 6,&15,24,33,42\\ 7,&16,25,34,43\\ 8,&17,26,35,44\\ 9,&18,27,36,45\\ \end{aligned}$ If any bucket has at least $4$ members in the set, then two of them must be adjacent and therefore have difference $9$ . So, by the pigeonhole principle, $f(9) = 9*3$ .

Generalizing from this example, for each N we can divide it as $50 = qN + r$ , where $q$ is the number of complete columns, and $r$ is the number of rows in the last column.

Then if $q$ is odd, $f(N) = N{q+1 \over 2}$ . And if $q$ is even, $f(N) = N{q\over 2} + r$ .

Now, we want to find all $N$ so that $f(N) \ge 30$ . We can categorize these by considering values for $q$ in turn, remembering that $q = \lfloor{50\over N}\rfloor$ and $r < N$ :

$q=1, f(N) = N, N \in \{26, 27,...,50\}$ : 21 solutions $N \gt 30$

$q=3, f(N) = 2N, N \in \{13,14,15,16\}$ : 2 solutions $N=15, N=16$

$q=5, f(N) = 3N, N \in \{9, 10\}$ : 1 solution $N=10$

$q=7, f(N) = 4N, N = 7$ : no solutions

$q=9, f(N) = 5N$ : no solutions

$q=25, f(N) = 13N, N = 2$ : no solutions

$q=2, f(N) = N + r, N \in \{17,18,...,25\}$ : 4 solutions $N=17, N=18, N=19, N=20$

$q=4, f(N) = 2N + r, N \in \{11,12\}$ : no solutions

$q=6, f(N) = 3N + r, N = 8, r=2$ : no solutions

$q=8, f(N) = 4N + r, N = 6, r=2$ : no solutions

$q=10, f(N) = 5N + r, N =5, r=0$ : no solutions

$q=12, f(N) = 6N + r, N = 4, r=2$ : no solutions

$q=16, f(N) = 8N + r, N = 3, r=2$ : no solutions

The question is asking for all the values of $N$ which are not solutions, i.e. $1-9, 11-14, 21-29$ which add up to $\boxed{320}$ .

Following @Michael Tong solution, it's possible to find a general condition. Given the set of integers from $1$ to $M$ and a subset of size $S$ , there must exist 2 integers whose absolute difference is exactly $N$ , if

$\displaystyle F(N)<S$

where

$\displaystyle F(N)=\begin{cases} \displaystyle N \bigg\lceil\frac{1}{2} \bigg\lfloor \frac{M}{N} \bigg\rfloor \bigg\rceil + (M \mod{N}), & \text{if} \ \displaystyle \bigg\lfloor \frac{M}{N} \bigg\rfloor \equiv 0 \mod{2} \\[10pt] \displaystyle N \bigg\lceil\frac{1}{2} \bigg\lfloor \frac{M}{N} \bigg\rfloor \bigg\rceil, & \text{otherwise} \end{cases}$