問題

ある人が、豆を何粒か持っています。これらの豆粒を、
@偶数個持っていたら半分を他人にあげる
A奇数個持っていたら、持っている数に1を足した数の半分を他人にあげる
という操作を繰り返したら、7回操作を繰り返したところで持っていた豆がなくなりました。
この人が持っていた豆の数として考えられるのは(  )粒以上(  )粒以下です。  (武蔵中)


操作の状況を理解するために、まずは具体的な数で実験してみましょう!

たとえば、、

18個(偶数個)なら、18÷2=9個になるので、1回の操作で半分になります。
19個(奇数個)なら、(19+1)÷2=10個減って9個になるので、1回の操作で1を引いて半分にした数になります。

はじめ持っていた数が18個なら、18→9→4→2→1→0で、5回の操作でなくなります。
はじめ持っていた数が19個なら、19→9→4→2→1→0で、5回の操作でなくなります。

ということは、7回の操作で豆がなくなるような状況を、
はじめ持っていた数が偶数個の場合と奇数個の場合で場合分けをして考える必要があって大変です。


そこで、2進法を使って考えると、かなり楽になります。どういうことか説明します!

18、9、19を2進法で表すと、



18=10010(2)、9=1001(2)、19=10011(2)
となって、偶数を2進法で表すと末尾が0になって、それを2で割った数は末尾の0が消えます。
奇数を2進法で表すと末尾が1になって、これから1を引くと末尾は0になって、さらに2で割るのでやはり末尾の0が消えます。

このように、2進法で考えると、1回の操作で末尾の数が消えることになります。 ・・・☆
だから、はじめ持っていた数が偶数個の場合と奇数個の場合で場合分けをして考える必要がありません。


------------結局これだけ↓------------

☆より、7回の操作で豆がなくなるようにするには、
はじめ持っていた豆の数は2進法だと7桁であればいい(1回の操作で末尾の1桁が消えるので)ことになります。

だから、1000000(2)〜1111111(2)の範囲。

1000000(2)を10進法に戻すと、1×64=64
1111111(2)を10進法に戻すと、1×64+1×32+1×16+1×8+1×4+1×2+1=127

となって、、はじめ持っていた豆の数は64粒以上127粒以下が答え。


[←戻る]