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$.

$\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.