**Motivation.** [Swiss license plates](https://en.wikipedia.org/wiki/Vehicle_registration_plates_of_Switzerland) consist of $2$ letters indicating the region, followed by a number, such that the pairing (region, number) is unique by car. In the small town where I live, I saw two cars today, both from my region, having license plate numbers differing by $1$. This motivated the following.


**Question.** Let $n\geq 2$ be an integer. We say that $S\subseteq \{1,\ldots,n\}$ *contains neighbors* if there is $k\in S$ such that $k+1\in S$. Let $M(n)$ denote the minimum integer $\leq n$ such that at least half of the sets $S\subseteq \{1,\ldots, n\}$ with $|S| = M(n)$ contain neighbours. What is the value of $$\lim\inf\_{n\to\infty}\frac{M(n)}{n}?$$



Probability of picking neighbors in $\{1,\ldots, n\}$
**Claim** The number of sets $S$ of cardinality $m$ with no neighbors is precisely $\binom{n+1-m}{m}$.


**Proof** Encode a subset $S$ of $[n]$ as a binary string $x\_0 x\_1 \ldots x\_n$ where $x\_0=0$ and $x\_j = 1$ if and only if $j \in S$. Then the sets we want correspond to strings with $m$ ones and no consecutive $11$'s, starting with $0$. A string starting with $0$ has no $11$'s if and only if it is a concatenation of $0$'s and $01$'s. If $x\_0 x\_1 \ldots x\_n$ has $m$ ones then it must be made of $m$ copies of $01$ and $n+1-2m$ copies of $0$; the number of ways to order these is $\binom{n+1-m}{m}$. $\square$


We want to understand when $\binom{n+1-m}{m} \geq \tfrac{1}{2} \binom{n}{m}$. Dividing both sides by $\tfrac{n^m}{m!}$, we want
$$\prod\_{j=m-1}^{2m-2} (1-j/n) \geq \tfrac{1}{2} \prod\_{k=0}^{m-1} (1-k/n)$$
or
$$\sum\_{j=m-1}^{2m-2} \log (1-j/n) \geq - \log 2 - \sum\_{k=0}^{m-1} \log (1-k/n)$$
$$ - \left( \tfrac{3m^2}{2} + O(m) \right) \tfrac{1}{n} + O(m^3/n^2) \geq - \log 2- \left( \tfrac{m^2}{2} + O(m) \right) \tfrac{1}{n} + O(m^3/n^2).$$
So
$$m^2/n = \log 2 + O(m/n) + O(m^3/n^2)$$
and the threshold is at $m = \sqrt{(\log 2) n}$.




---


This makes sense intuitively: If we choose a random set of size $m \approx \sqrt{(\log 2) n}$, then the probability that it contains $k$ and $k+1$ is $\approx \sqrt{(\log 2) n}^2/n^2 \approx (\log 2)/n$. Nonrigourously, the probability that $S$ does not contain $k$ and $k+1$ for any $k$ should be about $(1-(\log 2)/n)^{n-1} \approx e^{- \log 2} = 1/2$.


