Let $k \in \mathbb{N},$ $S_k = \{(a, b) | a, b = 1, 2, \ldots, k \}.$ Any two elements $(a, b)$, $(c, d)$ $\in S_k$ are called "undistinguishing" in $S_k$ if $a - c \equiv 0$ or $\pm 1 \pmod{k}$ and $b - d \equiv 0$ or $\pm 1 \pmod{k}$; otherwise, we call them "distinguishing". For example, $(1, 1)$ and $(2, 5)$ are undistinguishing in $S_5$. Considering the subset $A$ of $S_k$ such that the elements of $A$ are pairwise distinguishing. Let $r_k$ be the maximum possible number of elements of $A$. (i) Find $r_5$. (ii) Find $r_7$. (iii) Find $r_k$ for $k \in \mathbb{N}$.
Problem
Source: China TST 1988, problem 4
Tags: modular arithmetic, floor function, combinatorics unsolved, combinatorics
29.12.2005 04:43
Solution:When $k=1,2,3$, it's easy to know that $r_k=1$. If $k\geq4$,we assume that $A_i=\{(i,b)|b=1,2,\ldots,k\}(i=1,2,\ldots,k)$,$B_i=A_i\cup A_{i+1}(i=1,2,\ldots,k,A_{k+1}=A_k$. First we show that $|A\cap B_i|\leq\lfloor\frac{k}{2}\rfloor$ Just consider $B_1$,It's obvious that $(1,b),(2,b),(1,b+1),(2,b+1)$ are pairwise undistinguishing,so the elements of $A$ have at most $\lfloor\frac{k}{2}\rfloor$ different $b$,for each $b$,there is at most one $a=1 \mbox{or} 2$.So $|A\cap B_i|\leq\lfloor\frac{k}{2}\rfloor$ Then if we have $|A|=r_k$,then consider $\sum_{i=1}^k|A\cap B_i|=\sum_{i=1}^k|A\cap A_i|+|A\cap A_{i+1}|=2\sum_{i=1}^k|A\cap A_i|=2|A\cap S_k|=2r_k\leq k\lfloor\frac{k}{2}\rfloor$ So we have $r_k\leq\lfloor\frac{k}{2}\lfloor\frac{k}{2}\rfloor\rfloor$ Next we show that $r_k=\lfloor\frac{k}{2}\lfloor\frac{k}{2}\rfloor\rfloor$ In the next part,all number is in $\mod k$.$|b-d|>2$ means $b-d\not\equiv0\mbox{or}\pm1\pmod{k}$. If $k$ is even.Suppose $k=2m(m\geq2)$,then $\lfloor\frac{k}{2}\lfloor\frac{k}{2}\rfloor\rfloor=m^2$. Let $A=\{(a,b)|a,b\equiv1\pmod{2},(a,b)\in S_k\}$,then it's easy to see $|A|=m^2$, and for different $(a,b),(c,d)$ at least one of $|a-c|,|b-d|>2$,so they are distinguishing. If $k\equiv1\pmod{4}$,$k=4t+1(t\geq1)$,$\lfloor\frac{k}{2}\lfloor\frac{k}{2}\rfloor\rfloor=t(4t+1)$ Let $A\cap A_{2p+1}=\{(2p+1,b)|b=p+1,p+3,\ldots,2t+p-1\}(p=0,1,\ldots,4t)$ It's easy to know $|A\cap A_{2p+1}|=t$,so $|A|=t(4t+1)$. And $A\cap A_{2p}=A_{2(p+2t)+1}=\{(2p,b)|b=p+2t+1,p+2t+3,\ldots,p+4t-1=p-2\}$. And it's east to see for any two elements $(a,b),(c,d)$ in $A\cap A_{2p+1}$,$|b-d|>2$; and $(a,b)\in A\cap A_{2p+1},(c,d)\in A\cap A_{2p}$,$|b-d|>2$. So any different elements $(a,b),(c,d)\in A$ are distinguishing. If $k\equiv3\pmod{4}$,$k=4t+3(t\geq1)$,$\lfloor\frac{k}{2}\lfloor\frac{k}{2}\rfloor\rfloor=4t^2+5t+1$. Let $A\cap A_{2p+1}=\{(2p+1,b)|b=p+1,p+3,\ldots,2t+p-1\}(p=0,1,\ldots,2t+1)$ and $A\cap A_{2p}=\{(2p+1,b)|b=p+2t+1,p+2t+3,\ldots,p+4t+1=p-2\}(p=1,2,\ldots,2t+1)$ Likewise we can show $|A|=t(2t+2)+(t+1)(2t+1)=4t^2+5t+1$, and any different elements $(a,b),(c,d)\in A$ are distinguishing. So $r_k\leq\lfloor\frac{k}{2}\lfloor\frac{k}{2}\rfloor\rfloor$ And $r_5=5,r_7=10$.
31.07.2018 20:26
$\sum_{i=1}^k|A\cap A_i|+|A\cap A_{i+1}|=2\sum_{i=1}^k|A\cap A_i|$ i think it is incorrect because you have only one A intersection A1 and only one intersection A with Ak.