カードと平方数

来年度からSEになるのですが，修論にばかり追われていても
何の為にもならないなと思ったため，

「プログラマ脳を鍛える数学パズル」　著者：増井敏克

を購入し，勉強することに．
来年度から一緒に働くであろうエンジニアチームの方々との食事会の時，トップの御方に

勉強するならJava一択！

と言われたため，Javaでコードを書いております．

今回の問題はこちら．

1~100までの番号が書かれた100枚のカードが順番に並べられている．
初め，全てのカードは裏返しの状態で置かれている．
ある人が２番のカードから１枚おきにカードを裏返していく．
次に，３番のカードから２枚おきにカードを裏返していく．
このとき，裏向きのカードは表を向き，表向きのカードは裏を向くこととなる．
このように，n番目のカードからn-1枚おきにカードを裏返す操作を，100枚目のカードまで繰り返す．
問）最終的に裏向きになっているカードの番号を全て答えよ．

この問いをjavaで考えてみると以下のようになる．

import java.util.Arrays;

class Work{
 public static void main(String args[]){

Boolean[] card = new Boolean[100];
Arrays.fill(card,false);

//100枚目まで裏返す
for(int i =2; i <= 100; i++){
 for(int k=0; k<= 99; k++){
   if((k+1)%i == 0){
     card[k] = !card[k];
   }
 }
}
for(int j = 0; j<=99; j++){
 if(card[j]==false){
   System.out.println(j+1);
 }
}
}
}

実行結果は以下．

1
4
9
16
25
36
49
64
81
100

お分かりのように平方数(ある整数を2乗した数)が答えとなった．

ここからは，数学的な考察(一応，中高で数学の教員をやっているので…笑)

なぜ答えが平方数となるのか？

目標は，「最終的に裏向きになっている数を探し当てたい．」ということ．

スタートは裏の状態からなので，
偶数回めくられれば，
元に戻り，裏の状態に戻る．

例えば，８という数が書かれたカードでは，
2,4,8の倍数のタイミングでカードがめくられる．

この2,4,8という数は，(1を除く) 8の約数である．
(1を除くのは，1の倍数ではカードを裏返さず，2の倍数からのスタートだから．)

つまり，偶数回めくられる必要があるということは，
約数が１を除いて偶数個あれば良い．

これを言い換えると，

1を含めた約数の個数が奇数になるものが，
偶数回めくられるカードと同義であり，
最終的に裏向きで置いてあるカード，として捉えることができる．

約数の個数の考え方としては，

上の写真を一言で表すならば，素因数分解した後，
それぞれの指数に1足したものを掛け合わせていくという考え方．

したがって、指数が一つでも奇数になってしまうと，それに1を足したものの掛け算が約数の個数となるので，偶数になってしまう．

(例えば，72を素因数分解すると，72＝(2の3乗)×(3の2乗)．
したがって，約数の個数は，(3+1)×(2+1)=12個となる．)

よって，素因数分解した素数にかかる指数が全て偶数となれば良いことが分かる。
(そうすると約数の個数は(偶数＋1)×(偶数+1)で，(奇数)×(奇数)の形にしかならない．)

素因数分解した後の指数が偶数で表せるものは，「(ある自然数)の２乗」の形ですべてを表すことができるため，平方数が今回の問題の答えとなることが分かる．

Javaの勉強もしながら，数学的にも考えを膨らませることができるなんて
素晴らしい教材すぎますね．

ただ，今回はそこまでJavaのコーディングが難しくはなかった．
まだまだ初心者だから，このレベルで丁度良い気もするけれど，
早く一人前になりたいから，修論の合間に引き続き勉強は進めていきます．