Extensions of Ramsey's theorem: monochromatic but diverse As a follow-up of my previous question, which was resolved by Hsien-Chih Chang, here is another attempt to find an appropriate generalisation of Ramsey's theorem. (You don't need to read the previous question; this post is self-contained.)



Parameters: integers $1 \ll d \ll k \ll n$ are given, and then $N$ is chosen to be sufficiently large. Terminology: an $m$-subset is a subset of size $m$.

Let $B = \{1,2,...,N\}$. For each $k$-subset $S \subset B$, assign a colour $f(S) \in \{0,1\}$.

Definitions:


$X \subset B$ is monochromatic if $f(S) = f(S')$ for all $k$-subsets $S \subset X$ and $S' \subset X$.
$X \subset B$ is diverse if $X = \{ x_1, x_2, ..., x_n \}$ such that $x_i &lt; x_{i+1}$ and $x_i\,\not\equiv x_{i+1} \text{ mod } d$ for all $i$.


For example, if $d = 10$, then $\{ 12, 15, 23, 32, 39 \}$ is diverse but $\{ 12, 15, 25, 32, 39 \}$ is not. Note that a subset of a diverse set is not necessarily diverse.

Now Ramsey's theorem says that no matter how we choose $f$, there is a monochromatic $n$-subset $X \subset B$. And obviously it is trivial to find a diverse $n$-subset $X \subset B$.

Question: is there always a diverse and monochromatic $n$-subset $X \subset B$?



Edit: Hsien-Chih Chang shows that the claim is false for a prime $d$, but what about composite $d$? In my applications, I will have a lot of freedom in choosing the exact values of $d \ll k \ll n$, as long as I can make them arbitrarily large. They can be powers of primes, products of prime numbers, or whatever is necessary to make the claim true.
First I have to say: this problem is really interesting!! And here I briefly describe why my previous approaches failed, as suggested in this meta post about incorrect answers.


My first attempt was trying to construct a coloring related to the sumset of the k-subset which makes all n-subset non-monochromatic. Lemma 1 is still available; but Lemma 2 was wrong, by observing that if k and d are related prime, then an n-subset $\{1,3,1,3, \ldots\}$ in module d suggested by @Jukka is a counter-example.
The second try was a proof to the theorem; by counting the ratio of diverse and monochromatic $n$-subsets, we hope that the number of monochromatic ones will surpasses those of non-diverse ones. But the is an error in my calculations, observed by @domotorp: the ratio of being non-diverse will not approaches zero; it converges to about $n/d$, which is clearly larger than $R(n,n;k)^{-n}$.
The third one goes back to the first method, and it shows that for a uber-weak parameter set ($n &gt; k+d-1$ and $d \mid k$), the theorem is false. We used a famous lemma in additive combinatorics: the EGZ-theorem.




The fourth try is due to the answer by @domotorp; it is both clever and inspiring, and I'll try to modify his proof to deal with all the parameters. But still his method is elegant, and I totally appreciate this simple approach.

A diverse n-set contains at least one k-subset with at least $k-1$ "switches between mod classes"; precisely, let $X = x_1,\ldots,x_n$ be a diverse n-set, and let $S^* = x_1,\ldots,x_k$, a switch is defined if $x_i$ and $x_{i+1}$ are in different mod-d classes. We have k-1 switches for $S^*$.

Let a k-subset $S$ be red if $S$ has at most k-2 switches; otherwise it is blue. By the previous paragraph we already had a blue one, now we prove that for $n &gt; k+d+1$, there is an red $S$ in any n-set $X$. Since $n &gt; d$, there are two numbers $x_i,x_j$ in the same mod-d class and $j-i \leq d-1$; and since $n &gt; k+d+1$, there are at least k-2 elements $x_k$ in $X$ with $k&lt;i$ or $k&gt;j$. And we can construct a k-subset $S$ with $x_i$ next to $x_j$, which only switches at most k-2 times. Thus $S$ is a red k-subset.