 pc ( No.24 ) |
- 日時： 2011/09/21 17:42
- 名前： 宇奈月
- 正解を発表します。
最大値は53人です。
まずは候補を有限個に絞り込んでみます。
子供の人数をn人とし、元のケーキ一つの大きさをnとします。
大きさ9のケーキと大きさ1のケーキの2種類のみで切り分けることを考えます。
nを9で割ったときの商をm、余りをrとします。n=9m+rです。
1個のケーキを、r個の大きさ9のケーキと(9m-8r)個の大きさ1のケーキに分割します。
9個のケーキを、m個の大きさ9のケーキとr個の大きさ1のケーキに分割します。
このとき、大きさ9のケーキも大きさ1のケーキもn個ずつできますので分配可能です。
但し、9m-8r≧0であることに注意します。
n=9m+r=9m-8r+9r≧9rですので、n≧9r+r=10rです。
各rについて分配可能と分かっていないnを調べてみます。
r=0の場合はなし
r=1の場合n＜10なので、n=1
r=2の場合n＜20なので、n=2,11
r=3の場合n＜30なので、n=3,12,21
r=4の場合n＜40なので、n=4,13,22,31
r=5の場合n＜50なので、n=5,14,23,32,41
r=6の場合n＜60なので、n=6,15,24,33,42,51
r=7の場合n＜70なので、n=7,16,25,34,43,52,61
r=8の場合n＜80なので、n=8,17,26,35,44,53,62,71
大きい順に調べていきます。
71人の場合は分配可能です。
3個のケーキを、5個の大きさ7のケーキと12個の大きさ3のケーキに分割します。
7個のケーキを、8個の大きさ7のケーキと5個の大きさ3のケーキに分割します。
62人の場合は分配可能です。
4個のケーキを、8個の大きさ7のケーキと2個の大きさ3のケーキに分割します。
6個のケーキを、5個の大きさ7のケーキと9個の大きさ3のケーキに分割します。
61人の場合は分配可能です。
7個のケーキを、7個の大きさ7のケーキと4個の大きさ3のケーキに分割します。
3個のケーキを、4個の大きさ7のケーキと11個の大きさ3のケーキに分割します。
53人の場合は分配不可能ですので53人が最大値となります。
ちなみに分配不可能な人数は1,2,3,4,6,7,11,13,14,17,23,33,43,53の14個です。
53人の場合に分配不可能なことは簡単に証明できると思っていたのですが、いざ取り組んでみたら予想以上に手ごわかったです。
何とか証明できましたが、かなり長くなってしまいました。
後日書き込みますが、簡単にできるという方がいましたら是非証明お願いします。
囁き欄はなくしておきますので、直接コメント欄にどうぞ。
|
|
FAQ
RSS