Evolton

東京大学 1983年度 前期日程 第2次学力試験理系数学 第2問

数列 {an} において、a1=1 であり、n≧2 に対して an は、次の条件 (1)、(2) をみたす自然数のうち最小のものであるという。

(1) an は、a1,…,an−1 のどの項とも異なる。

(2) a1,…,an−1 のうちから重複なくどのように項を取り出しても、それらの和が an に等しくなることはない。

このとき、an を n で表し、その理由を述べよ。

難易度5/ 10計算量4/ 10目安16分

数列、整数 数学的帰納法、数え上げ、存在証明

方針

最初の n−1 項が 1,2,4,…,2n−2 なら、各項を使うか使わないかによって 0 から 2n−1−1 までの全整数が部分和として現れる。したがって、その次に許される最小値が 2n−1 になることを帰納法で示す。

解答

(1)
既出の項と異なること、ならびに
(2)
以前の項の部分和で表せないことを同時に確認する。結論はan=2n−1である。これを数学的帰納法で示す。

a1=1=20 である。ある n≧2 についてa1,a2,…,an−1=1,2,4,…,2n−2であると仮定する。各 2k を使うか使わないかを選べば、2進表示により0,1,2,…,2n−1−1のすべてが、以前の項を重複なく選んだ和として一意に表される。したがって 2n−1 より小さい自然数は条件を満たさない。

一方、以前の全項の和は1+2+4+⋯+2n−2=2n−1−1であるから、2n−1 は以前の項の和では表せず、既出の項でもない。よって条件を満たす最小の自然数は 2n−1 である。帰納法により、すべての n でan=2n−1が成り立つ。

既存項の部分和は 0 から「次の項の1つ前」までを埋める

別解

解法2(部分和区間の漸化式)

方針

最初の n 項から作れる部分和が、隙間のない区間 0,1,…,Sn になることに注目する。次の最小許容値は常に Sn+1 であり、それを加えると部分和区間がちょうど2倍に延びる。この和の漸化式を解く。

解答

(1)
既出項との相違と、
(2)
部分和で表せないことを、部分和区間を用いて同時に扱う。最初の n 項の和をSn=a1+a2+⋯+anとする。さらに、最初の n 項から作れる部分和が0,1,2,…,Snをすべて含むことを同時に示す。

n=1 では a1=1、S1=1 で、部分和は 0,1 である。いま 0 から Sn−1 までがすべて作れるとする。このとき 1,2,…,Sn−1 は次の項に選べない。一方、Sn−1+1 は以前の全項の和より大きいので作れず、既出でもない。したがってan=Sn−1+1.新しい項 an を使わない部分和は 0 から Sn−1、使う部分和はSn−1+1,Sn−1+2,…,2Sn−1+1となる。よって隙間なく 0 から Sn まで作れ、Sn=2Sn−1+1,S1=1.したがって Sn=2n−1 であり、an=Sn−Sn−1=2n−1を得る。

総評

条件 (2) を「既存項で作れる部分和の穴」と読み替える数列問題。目安時間は16分。候補が使えないことだけでなく、2n−1 が実際に使えることまで示して最小性を閉じる必要がある。2進表示と部分和区間の漸化式の2通りで一般項を確認した。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る東大の数列の問題で問題集を作る

出典: 東京大学 1983年度 第2次学力試験 数学。問題文はHTML表示のために再入力・数式組版しています。