これって東大生はできるんですかね?
僕は少なくともできなかったです。(以下の解法を知らなかったということです。帰納法とか使う面倒な方法ならできたかもしれません。)
以下解法です。できるって方は続きを見ないで解いてからみてください。



Modの性質を使ったバージョン(定義しないでそのまま使って良いのかの不安が付きまとう)
整数mはすべてnを用いて3n,3n+1,3n+2で表せます
つまり、整数mは、m≡0mod3、m≡1mod3、m≡2mod3で表現できます。
modの性質より、m^2≡0mod3、m^2≡1mod3、m^2≡1mod3 なので。

Modの性質を使わないバージョン(安心して使える)
整数mはすべてnを用いて3n,3n+1,3n+2で表せます
(3n)^2,(3n+1)^2,(3n+2)^2のそれぞれを3で割ったあまりはそれぞれ0,1,1になるので。

これ後者のModを使わないバージョンが良いかもですねw。