トップ > 算数にチャレンジ!! > カードの数字の書き換え，2進法 /「算数にチャレンジ!!」第1188問

カードの数字の書き換え，2進法 /「算数にチャレンジ!!」第1188問

算数にチャレンジ!!

問題概略

以下のような法則で左から順にカードに数を記入して並べていくゲームをしています。

  • 1 番目のカードには 1 を記入する。
  • 偶数番目のカードには番号が半分のカードと同じ数を記入する。たとえば 10 番目のカードには 5 番目のカードと同じ数を記入する。
  • 奇数番目のカードにはその番号を 2 で割って 0.5 を引いたカード番号の数に 1 を加えて記入する。たとえば 11 番目のカードには 11\div 2-0.5=5 番目のカードに記入されている数に 1 を足した数を記入する。

このゲームをカード番号が 300 番になるまで続けたとき，カードに記入された数の最大値を求めてください。

http://www.sansu.org/used-html/index1188.html

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

漸化式を使って計算

まずは問題文の条件をそのまま漸化式にしてみました。
n が奇数のときは引数を n\to \frac{n}{2}-\frac{1}{2}=\frac{n-1}{2} に変えるので，次のようになります。

f(n)= f\left(\frac{n}{2}\right)\quad (\text{$n$が偶数のとき})

f(n)= f\left(\frac{n-1}{2}\right)+1\quad (\text{$n$が奇数のとき})

この漸化式を使って f(1) から f(300) まで計算したときの最大値が答えです。
mathematica で計算しました。答えは 8 です。

   In[]:= AbsoluteTiming[
      f[1] = 1;
      f[n_] := f[n] = If[EvenQ@n, f[n/2], f[(n - 1)/2] + 1];
      ans = Max[f /@ Range@300]]
     
   Out[]= {0.0009785, 8}

2 進法で考える

2 進法で考えると n\to\frac{n}{2}, n\to\frac{n-1}{2} は末尾を削る操作です。

2_{(10)}=10_{(2)}\to 1_{(2)},\, 3_{(10)}=11_{(2)}\to 1_{(2)}

1 を削るたびに f(n) が 1 増えるので，最大値を与える n は 2 進法であらわしたときにすべての桁が 1 になる数です。
300 以下だと 255=256-1 ですね。こう考えると最大値の 8 は暗算で求められます。

256-1=2^8-1={\overbrace{11\cdots 1}^{\text{8個}}}_{(2)}

同じ発想で一般の f(n) を求めることもできます。
f(n) を求める過程は n の 2 進法表記を右から見ていって 1 を数えるのと同じです。

f(n)=(\text{$n$を2進法であらわしたときの1の個数})

これは mathematica だと \texttt{DigitCount(n, 2, 1)} で求められます。
漸化式を使うよりこっちの方が速いです。

   In[]:= AbsoluteTiming[
      f[n_] := DigitCount[n, 2, 1];
      ans = Max[f /@ Range@300]]
     
   Out[]= {0.0002094, 8}


variee.hatenablog.com