村人の年齢 解答

December 20 [Thu], 2012, 21:57
【問題】全滅村の村人は年齢が全員正の整数であり、その和はちょうど2012である。

村人の年齢の積が最大になるとき、村人は全部で何人か。
---------------------------------------------------------------------
【解答】
村人の人数をnとし、村人の年齢をa1,a2,...,an (ただしa1≦a2≦...≦an)とする。a1+a2+…+an=2012である。また、そのときの年齢の積をX(a1,a2,...,an)と書くことにする。

X(a1,a2,…,an)が最大になるとき、次の補題@〜Dが成り立つことを示す。

補題@:各整数i(1≦i≦n)に対して、ai≧2が成り立つ。
補題A:各整数i(1≦i≦n)に対して、ai≦4が成り立つ。
補題B:ai=2となるような整数iは高々2つである。
補題C:ai=4となるような整数iは高々1つである。
補題D:1≦i,j≦n(i≠j)である整数i,jであって、ai=2かつaj=4となるものは存在しない。

補題@の証明
ある整数iであって、ai=1となるものが存在すると仮定する。このとき、a1=1である。年齢の和が2012であることから、n≧2である。整数の組(b2,b3,…,bn)を、次のように定める:

《b2=a2+1》
《3≦i≦nのとき、bi=ai

このとき、a1+a2+…+an=b2+b3+…+bn=2012であるが、
X(b2,b3,…,bn)-X(a1,a2,…,an)
=(b2-a1a2)X(a3,a4,…,an)
=(a2+1-a2)X(a3,a4,…,an)
=X(a3,a4,…,an)>0となって、X(a1,a2,…,an)が最大であることに矛盾。よって示された。


補題Aの証明
ある整数iであって、ai≧5となるものが存在すると仮定する。このとき、an≧5である。整数の組(b1,b2,…,bn,bn+1)を、次のように定める:

《bn=2,bn+1=an-2》
《1≦i<nのとき、bi=ai

このとき、a1+a2+…+an=b1+b2+…+bn+bn+1=2012であるが、
X(b1,b2,…,bn,bn+1)-X(a1,a2,…,an)
=(bnbn+1-an)X(a1,a2,…,an-1)
={2(an-2)-an}X(a1,a2,…,an-1)
=(an-4)X(a1,a2,…,an-1)>0 (∵ an≧5)となって、X(a1,a2,…,an)が最大であることに矛盾。よって示された。


補題Bの証明
ある整数i,j,k(i<j<k)であって、ai=aj=ak=2となるものが存在すると仮定する。補題@より、a1=a2=a3=2である。整数の組(b2,b3,…,bn)を、次のように定める:

《b2=b3=3》
《4≦i≦nのとき、bi=ai

このとき、a1+a2+…+an=b2+b3+…+bn=2012であるが、
X(b2,b3,…,bn)-X(a1,a2,…,an)
=(b2b3-a1a2a3)X(a4,a5,…,an)
=(9-8)X(a4,a5,…,an)
=X(a4,a5,…,an)>0となって、X(a1,a2,…,an)が最大であることに矛盾。よって示された。


補題Cの証明
ある整数i,j(i≠j)であって、ai=aj=4となるものが存在すると仮定する。補題Aより、an-1=an=4である。整数の組(b1,b2,…,bn,bn+1)を、次のように定める:

《bn-1=2,bn=bn+1=3》
《1≦i<n-1のとき、bi=ai

このとき、a1+a2+…+an=b1+b2+…+bn+bn+1=2012であるが、
X(b1,b2,…,bn,bn+1)-X(a1,a2,…,an)
=(bn-1bnbn+1-an-1an)X(a1,a2,…,an-2)
=(18-16)X(a1,a2,…,an-2)
=2X(a1,a2,…,an-2)>0となって、X(a1,a2,…,an)が最大であることに矛盾。よって示された。


補題Dの証明
ある整数i,j(i≠j)であって、ai=2,aj=4となるものが存在すると仮定する。補題@,Aより、a1=2,an=4である。整数の組(b1,b2,…,bn)を、次のように定める:

《b1=2,bn=4》
《2≦i<nのとき、bi=ai

このとき、a1+a2+…+an=b1+b2+…+bn=2012であるが、
X(b1,b2,…,bn)-X(a1,a2,…,an)
=(b1bn-a1an)X(a2,a3,…,an-1)
=(9-8)X(a2,a3,…,an-1)
=X(a2,a3,…,an-1)>0となって、X(a1,a2,…,an)が最大であることに矛盾。よって示された。


さて、補題@〜Dより、X(a1,a2,…,an)が最大になるようなa1,a2,…,anの組は、
(3,3,…,3,3)
(2,3,3,…,3,3)
(2,2,3,3,…,3,3)
(3,3,…,3,3,4)
のいずれかに限られることが分かる。このとき、a1+a2+…+anを3で割った余りは、順に0,2,1,1である。
一方、2012を3で割った余りは2であるから、a1+a2+…+an=2012となる組は(a1,a2,…,an)=(2,3,3,…,3,3)のみであり、このとき3の個数は(2012-2)/3=670である。よってX(a1,a2,…,an)の最大値は2・3^670であり、このときn=671である。

以上より、求める村人の人数は671人である。
プロフィール
  • プロフィール画像
  • アイコン画像 ニックネーム:ナガーシッカくん
読者になる
2012年12月
« 前の月  |  次の月 »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
最新コメント
ヤプミー!一覧
読者になる
P R
カテゴリアーカイブ
月別アーカイブ
http://yaplog.jp/b4ck8n30n2m1/index1_0.rdf