【頭の体操クイズ】File.027:ビット演算の汎用性

頭の体操シリーズ上級編:上級編
プロファイル

頭の体操クイズ – File.027

タイトル:ビット演算の汎用性

難易度 :上級

タイプ :数学的論法

所要時間:20分

出題元 :apple社入社試験

問題

【頭の体操クイズ】File.027:ビット演算の汎用性

[問題]
100階建てのビルディングで、ある高さ以上で壊れてしまう電球を20個渡された場合、どのようにして効率よく電球が壊れる高さを特定しますか?

[補足]
・特になし

ヒント

丁度半分の50階から試していくと、50、±25と奇数階からの検証となってしまい、余分な試行回数が増えてしまい効率的ではないです。

半々に割っていく際に、途中で奇数階が発生してしまうと、以後、割る際に効率よく割ることができず、+1回の余計な試行が増えてしまいます。
途中で奇数が発生しないためには、パソコンの概念でもあるあるモノが利用できますね。

解答

[正解]
64階からスタートして、壊れるor壊れないの判定に基づき、さらに半分の階数分増減を繰り返していくことで、効率よく電球が壊れる階を見つけることができ、最高7回の試行で特定が可能。
(その他の解答もあるかと思います。)

[補足]
この考え方に慣れるまで苦労はします。。。File.015 – 毒入りワインの見分け方の類似系の問題となります。
100階の内、どの階以上で電球が割れるかを考える時に、100階を際限なく半数に割っていくにはどうすればよいかを考えていくと、より多くの「対象」と「非対象」を選別しながら特定していく事ができるため、効率良く作業ができます。
(100階を半分に割った50階から電球を落とした場合に割れないとしたら、電球が割れる高さが100~51階まで絞れて、50階~1階までが対象外になることが分かります。50回分の試行を省略できました。)
ここで重要になってくるのが「2の累乗数」です。2つに分けながらなので。。。
この2の累乗数に合わせて割っていく事ができれば、必ず半分ずつに割っていく事ができますし、2の累乗数に当てはまらなかった分は、当てはめるように割っていってあげれば、素数にぶち当たらない限り必ず半分に割ることができます。
今回の場合は、100階なので、2の累乗に該当しません。そのため、100を超えない2の累乗である「64」からスタートします。
これ以上書くとダラダラしますので、検証は個人で行っていただけると幸いです。
[補足]
この考え方でいくと、
①64階→割れない(+32階)
②96階→割れない(+16階)
の場合、102階となりますが、階数の上限を超えているため、残りの4つの階で2の累乗で割って計算していけばよいです。

次の問題へ進む

次の問題は「中級編:0生み出す矛盾」です。

数え上げる時は「1」から始まり、数え下げる時には「0」まで数える、そんな矛盾を感じた事はありませんか。この「0」により歪んだ数え方を正していく事で、答えを導く内容となっています。

■次の問題
File.028 – 中級編:0が生み出す矛盾

■前の問題
File.026 – 中級編:足元にご注意

頭の体操・論理クイズをさらに楽しむには

頭の体操になる論理クイズをさらに楽しむには、「共有」することが大切だと考えています。

共有することで、話題作りになるだけでなく、説明する力も付き、社会人生活を歩んでいくうえで、大きなアドバンテージを作るきっかけになりえます。

そうした魅力を携えることで、心に余裕を持てれば、生活が豊かになり、ストレス発散にも繋がり、寝ても眠い症状を吹き飛ばす原動力が生まれるかもしれません。

論理クイズは、知識と情報を広い視野で得るための訓練になりますので、ぜひ、本サイトで掲載している頭の体操クイズを有効に活用してみてください。

■関連記事
【頭の体操シリーズ】論理クイズの概要説明

プロフィール
ぺぴちに

IT企業でのSE・プロマネ経験を経て、現在は「人の心理」について研究をしています。
5年間のうつ病生活の実体験から得た知識を元に、「睡眠」「ストレス」に関する問題を解決するための情報を発信していきます。

[実績]
・保険機関・論文を含め200件以上の情報を解読。
・2021年に書籍化の話をいただく。

科学的に解明がされていない事が多い分野であるため、基本的には絶対的な方法より、可能性のある方法を提案することが重要であると考えています。

ぺぴちにをフォローする
上級編頭の体操
【スポンサーリンク】
寝ても寝ても眠い原因とあなたとわたしの事情