ひたすら受験問題を解説していくブログ
灘中学校2016年算数第2日目第1問
nada_2016_math2_1q.png

解説

参考にあるように2進数の問題ですが,規則をしっかりとらえていけば具体的なものに関してはどうにかなるかと思います。ルールが2個ずつであるところから偶奇がかかわってくることを読み取って欲しいです。

(1)
1周目は偶数だけ残って奇数が取り除かれていく事になります。2016÷2=1008なので,1周目は終わります。割り切れているので,2016が残って2の倍数が小さい順に並んだところからスタートです。したがって,2が除かれます。

(2)
1008回目の操作で2の倍数が小さい順に並んでおり,2周目は2の倍数だけど4の倍数ではないものが取り除かれていきます。操作枠がズレない限り(1,2,3,4,5だったら5は2で割りきれないので,1周目と2周目の境界で5,2,4に操作して2周目の奇数番目が残るように操作する枠がズレます),周数が上がるごとに残っていくものが割れる2の回数が増えていきます。
2016÷2=1008
1008÷2=504
504÷2=252
252÷2=126
126÷2=63
となっており,5周目までは2016が残されるため,操作枠のズレはありません。

1000=125×23なので(上の数字でかける回数を表します。2が3回かかっています),第4周目の125÷2=62・・・1つまり,63回目に除去されます。したがって,1008+504+252+63=1827回目に除去されます。

(3)
(2)と同様にいくと,2016は6周目の最後です。63÷2=31・・・1なので,1008+504+252+126+63+31=1827+126+32=1985回目となります。

(4)
6周目(1985回目)の操作で26で割れるものしか残っていなくなりますが,読み取り枠のズレが起こり,7周目では27で割れるものが除去されてしまいます。1985回目で26が残されており,もともと26から2016-25=1984=31×26が最後なので,7周目は15回の操作でピッタリ操作が1984を残すことで終わります。
つまり,64で割れるけど128で割れないもののみが7周目の操作で残っているので,①128,②64が答えです。

(5)
もはや残っているカードは26で割って,1,3,・・・,31としてもよいでしょう,更に詰めて1,2・・・,16としても同じです。16は24なので,最後まで残ります。したがって,これはもともと31×26=1984だったはずです。

【参考】2進数による一般解(高校生以上向け)
本問は2進数表記の一桁ずつを0か1か判別して除去していく問題です。初めは
1,10,11,・・・・,11111011111,11111100000
から一番右の位が1のものを除去していきます。
10,100,・・・・,11111011110,11111100000
となりますが,一桁移動してやれば,
1,10,・・・・,1111101111,1111110000
というようにまた連続した数の列として捉えることができるようになります。続けていくと,
1,10,・・・・,111110,111111
のようになり,ここで最後のものが取り除かれてしまい,操作枠が一つずれるので,のこった,
100,・・・・,111100,111110,10
こと
10,・・・・,11110,11111,1
からは末尾が0のものが除去されていきます。
1,11,101,・・・11101,11111
が残るので,1足して一桁移動してやれば
1,10,・・・,1111,10000
となり10000が最後に取り除かれることがわかります。

さて,ここで一般の場合に最後が何になるのか考えていきましょう。求めたいカードの数をmとする時,漸化式的に行けば,m=2kの時は(2aを二進数表記でa0のようにaになる二進数に0をひとつ加えたもののように表記するとします),
1,10,・・・,(k-1)1,k0
から一周取り除くと,
10,110,・・・(k-1)0,k0
となります。これは,m=kのカード列の全部を2倍しただけなので,最後のカードを求める関数をfとすると,f(2k)=2f(k)になります。

一方,m=2k+1の時は,
1,10,・・・,(k-1)1,k0,k1
なので,一周取り除くと,
110,・・・(k-1)0,k0,10
となります。これをひとつ0を取り除いて考えれば,
11,・・・(k-1),k,1
であり,k枚のカードで開始がずれているだけです。したがって,f(2k+1)=2 (f(k)=k),2f(k)+2 (f(k)≠k)となります。

f(k)=kを満たすのは,最後に自身が取り除かれるので,2で割り続けても最後にしか奇数にならないことになるので,2の累乗系統です。

以上より,例えば2016=25×(25+24+・・・+1)なので,f(2k+1)=2f(k)+2の漸化式を解いて,25×(26-2)=1984と求められます。
もっと一般的には,2進数の右の桁から処理してあげて,0なら2倍,1なら+2をして2倍なので,11010なら,
2f(1101)=2(2f(110)+2)=2(2・2f(11)+2)=2(2・2・2+2)=20
となります。左端の1と左端から2番目の1の処理のところで二つまとめて左端から2番目の位置で2,つまり左端から二番目を右端から数えた位置が2の指数部分になってしまうことに注意し(f(2k+1)=2 (f(k)=k)のことです),それ以外の1は出てきた位置が右端から何番目であるかが2の指数部分になります。

したがって,1が2以上ある場合は左端の1をとって2倍すなわち0を右端に足す。
1が1つのみならそれが最後なので,そのままが答えになります。

この結果を改めて2016=11111100000に用いれば,11111000000=1984が答えになることがわかります。

灘中学校2016年算数に戻る
スポンサーサイト

テーマ:中学受験 - ジャンル:学校・教育

コメント
コメント
コメントの投稿
URL:
本文:
パスワード:
非公開コメント: 管理者にだけ表示を許可する
 
トラックバック
トラックバック URL
http://jukenkaisetsu.blog.fc2.com/tb.php/612-0b72dfde
この記事にトラックバックする(FC2ブログユーザー)
トラックバック