一旦理屈をすっ飛ばしますが、
n=p、p は 5 以上の素数、Z/pZ で 2 が原始根、p≡1 (mod 3) で k=0 のとき、
とりあえず以下の方法で検証できることが分かりました。

(1) 縦２マス横 (p-1)/2 マスのマス目を考え、図のように３色で塗り分ける。
https://i.imgur.com/D3N6fXO.jpg

(2) Z/pZ における数列 {a[n]} を
a[1]=(2p+1)/3
a[n+1]=4a[n]+1　(n≧2)
で定義し、図のようにマス目に添える。
https://i.imgur.com/3goOSBZ.jpg

※ {a[n]} の一般項は ((2p+2)4^(n-1)-1)/3 である。

※ a[n+(p-1)/2] ≡ a[n] (mod p) が成り立ち、周期的な数列となる。

(3) a[i] が Z/pZ で平方数であればその列の下側のマスに印をつける。
そうでなければ上側のマスに印をつける。
https://i.imgur.com/5H1VKGX.jpg

(4) ３色とも少なくとも１つのマスに印がついていれば予想が成り立つ。