慶應SFC　環境情報学部　情報入試　2019年　大問Ⅴ　過去問解説

(ア)
示された通りに計算する。答えは36。

(イ)
結果として,,…,の値を出力する、との文章からがハミング数となることが分かる。
(ア)で示されている処理手順を条件として当てはめていけばいい。

まず容易に分かるように、である。

nの値を1増やすと2である。
2×=2
3×=3
5×=5
である。
したがって。

このとき、2は斜線を引かれる。つまり消される。2×が消されるということである。
つまり、
=2×
のとき消されている。

このときのnとpの値を考え、

のとき消される、つまりpを1増やす、と考える。

次にpの値を増やす（消す）のは、xを10000以下の任意の自然数として、

となったときである。

これはn=10000となるまで続く。

同様のことが、q,rについても言える。

よって答えは(1)。

(ウ)
これは背理法という数学の証明方法の一つを用いている。

=1なので、

であることは容易に分かる。

i>0の場合について証明するとは、

の場合について考えればよい。

である
との記述より
iが1少ないときを仮定する
と考えられる。
したがって

である。

の場合は、p=sになるときがある。このときj,kを適当に選び、とおくと

となるs’が存在する。
なぜならsは最小でも1であり、s=1のときはのときだからである。（このときはh’となる）

と書ける。
このとき

となる。
が出現している。

の場合は、
10000回目の実行として考える。

が最小の場合とは、

の場合である。

命令Cでpが1増えるので、となる。

である。

となる。

が最小でなかった場合とは、
がか
であり、

である。
このときも

となる。

これらの数式により問題文の証明は完成される。