Let $p > 3$ be a given prime number. For a set $S \subseteq \mathbb{Z}$ and $a \in \mathbb{N}$ , define $S_a = \{ x \in \{ 0,1, 2,...,p-1 \}$ | $(\exists_s \in S) x \equiv_p a \cdot s \}$ . $(a)$ How many sets $S \subseteq \{ 1, 2,...,p-1 \} $ are there for which the sequence $S_1 , S_2 , ..., S_{p-1}$ contains exactly two distinct terms? $(b)$ Determine all numbers $k \in \mathbb{N}$ for which there is a set $ S \subseteq \{ 1, 2,...,p-1 \} $ such that the sequence $S_1 , S_2 , ..., S_{p-1} $ contains exactly $k$ distinct terms. Proposed by Milan Basic and Milos Milosavljevic
Problem
Source:
Tags: Subsets, TST, algebra
28.05.2015 16:06
Solution?
02.06.2015 07:56
My solution: Suppose that $S=\{a_1,a_2,...,a_t\}$ and $S \subseteq \{1,2,3,...,p-1\}$ suppose that $g$ is the primitive root of $p$ and there exists $b_1,b_2,...,b_t$ such that $g^{b_i} \equiv a_i \pmod{p}$ (since $g$ is primitive root) Then, we have $S_{i}=\{i.a_1,i.a_2,...,i.a_t\} \pmod {p}$ or $S_i=\{g^{b_1+j},g^{b_2+j},...,g^{b_t+j}\}$ where $g^j \equiv i \pmod {p}$, and let $\{b_1+j,b_2+j,...,b_t+j\}=M_j$ Now, the number of different sets in $S_1,S_2,...,S_{p-1}$ becomes the number of different sets in $M_{1},M_{2},...,M_{p-1}$ (since $\{1,2,..,p-1\} = \{g^1,g^2,...,g^{p-1}\} \pmod {p}$) Now we only consider the sets $M_{1},M_{2},...,M_{p-1}$ (now every thing in $M_{1},M_{2},...,M_{p-1}$ will be considered in modulo $p-1$) For part a) There are exactly 2 distinct elements in $M_{1},M_{2},...,M_{p-1}$, also $M_j=\{b_1+j,b_2+j,...,b_t+j\}$, then if $t=p-1$, we have $S={1,2,...,p-1}$ then $S_1=S_2=...=S_{p-1}$ a contradiction, then $t$ is different from $p-1$ So, $M_i,M_{i+1}$ are different because if $M_i=M_{i+1} \rightarrow \{b_1+i,...,b_t+i\}=\{b_1+i+1,...,b_t+i+1\} \rightarrow (b_1+i)+...+(b_t+i)\equiv (b_1+i+1)+...+(b_t+i+1) \pmod {p-1} \rightarrow i.t\equiv (i+1).t \pmod {p-1} \rightarrow t\equiv 0 \pmod{p-1} \rightarrow t=p-1$ this is a contradiction since $t$ is different from $p-1$, now we can conclude that $M_i,M_{i+1}$ are different or more details, $M_1=M_3=...=M_{p-2}$ and $M_2=M_4=...=M_{p-1}$ Also we have $M_1=M_3=...=M_{p-2}$ but $b_1+1,b_1+3,...,b_1+p-2$ are different in modulo $p-1$ so $M_1=M_3=...=M_{p-2}= \{x,x+2,...,x+2.(t-1)\}$ all are in modulo $p-1$ Now, we see that if we write the number $\{x,x+2,...,x+2.(t-1)\}$ on the circle and put a pinpoint on an one arbitrary position of $t$ positions and constants that position, then rotate the circle we will gain at most $t$ different sets, but we have in total $\dfrac{p-1}{2}$ sets, they are $M_1,M_3,...,M_{p-2}$, so $t=\dfrac{p-1}{2}$ or $M_1=M_3=...=M_{p-2}=\{1,3,5,...,p-2\}$ and $M_2=M_4=...=M_{p-1}=\{2,4,6,...,p-1\}$ or $M_1=M_3=...=M_{p-2}=\{2,4,6,...,p-1\}$ and $M_2=M_4=...=M_{p-1}\{1,3,5,...,p-2\}$ Hence the answer for this part is $2$ For part b) Same as the above argument, there are exactly $k$ distinct sets in $M_{1},M_{2},...,M_{p-1}$ now we partition $M_{1},M_{2},...,M_{p-1}$ into $k$ groups, they are $G_1,G_2,...,G_k$ such that $M_i,M_j \in G_l$ then $M_i=M_j$ and if $M_i \in G_l,M_j \in G_h$ and $l,h$ are different, then $M_i$ is different from $M_j$ (1) Let $c$ be a number in $[1,p-1]$ such that $(c,p-1)=1$ Now we make maps: For all $M_{i_1} \in G_1$ define $f: M_{i_1} \rightarrow M_{i_1}+c*r$ for $r=\overline{1,p-2}$ with connotation that $M_i+c*r = \{b_1+i+c*r,b_2+i+c*r,...,b_{t}+i+c*r\}$ Now, since $(c,p-1)=1$ then $c*r$ will make a complete resdue $\pmod{p-1}$ So, we finished making maps $f: G_1 \rightarrow G_i$ for all $i=2,3,..,k$, it's easy to see that $f$ is injective, so $|G_1|\le |G_i|$ for all $i=2,3,..,k$, now we change the role between $G_1,G_2,...,G_{k}$ or $|G_1|=|G_2|=...=|G_k|$, on the other hand $|G_1|+|G_2|+...+|G_k|=p-1$ (see (1)) thus $k|p-1$ Now for all $k|p-1$ and $p-1=kd$, it remains to us to figure out one case that satisfies the condition, we only have to choose $t=d$ and $\{b_1,b_2,...,b_d\}$ such that $b_1 \equiv b_2 \equiv ... \equiv b_d \equiv 1 \pmod {k}$ and it's easy to examine that this satisfies all conditions