クイズ大陸



履歴 検索 最新 出題

No. 24≫ No.25 最新レスです
?vipper 2011/09/23 00:52
自分はこんな感じで解きましたかね。とは言えこういう証明をして答えを出した訳ではなく考えたことを数式表現に置き換えてる感じですが。あーあと証明書いててNが10の倍数だと成立しないことに気がついた (^^;) けどそのときは分配可能なことは自明だと思うので、Nが10の倍数でないときに分配可能か不可能かの証明ということで。(中学生以下の人も居るぽいので補足をしておくと、「Σ」は足し合わせるという意味(Sum)です。以下の文では Σa[i]=a[1]+a[2]+a[3]+…+a[10] という意味だと解釈して下さい。)


1つのケーキの大きさを1だと基準を定めて、分割して出来る2種のケーキの大きさをA及びBとする(A, Bは正の実数、A=Bであっても構わない)。また10個のケーキに1番から10番まで番号をつけ、i番目のケーキをAの大きさが△個とBの大きさが□個に分けるとき、a[i]=△, b[i]=□(a[i], b[i]は0以上の整数)と定義する。子どもの人数をN(Nは自然数)として、設問通りにケーキが分配可能な必要十分条件はそのNに対して、

A・a[i]+B・b[i]=1(1≦i≦10, iは整数)…@, Σa[i]=Σb[i]=N…A の全てを同時に満足するようなA, B, a[i](i=1〜10), b[i](i=1〜10)の組み合わせが存在する(以下、条件Pと書く)ことである。この条件Pは次の条件と同値である。s, tを0以上の整数、m, nを正整数、kを1≦k≦9の範囲の整数とし、子供の人数Nに対して 10s+k・m=10t+(10−k)n=N…B を満足するようなs, t, m, n, kの組み合わせが存在する(以下、条件Qと書く)。

ここから条件Pと条件Qが同値であることを証明する。まず、条件Pが真ならば条件Qも真であることを言う。@Aは成り立っているものとして、Ax+By=1 を満たす0以上の整数x, yの組み合わせのうち、最小であるxの値をa、またそのとき最大となっているyの値をbとする。当然 A・a+B・b=1 が成り立ち、これと式@の両辺を引き算すれば A(a[i]−a)+B(b[i]−b)=0 となる。a[i]≠a, b[i]≠b のとき、式を変形すれば (a[i]−a)/(b−b[i])=B/A=const(一定な有理数) であるから互いに素な正整数m, nを用いて、(a[i]−a)/(b−b[i])=m/n と書くことが出来る。とすると全ての a[i] 及び b[i] は z[i] を0以上の整数として、a[i]=a+m・z[i], b[i]=b−n・z[i] (a[i]=a, b[i]=b なら z[i]=0)と表現し得るはず。これを式Aに代入すると、

10a+mΣz[i]=10b−nΣz[i]=N となる。Σz[i]を10で割ったときの商と余りをそれぞれr, kと置いて式を変形すると 10a+m(10r+k)=10b−n(10r+k)=N と書ける。ここで s=a+m・r, t=b−n(r+1) と置き換えれば、これはBを満たしている (Nが10の倍数のときは除外して考えているから k=0 にはならない。t≧0 であることは、全てのiで b[i]≧0 であり最小のb[i]がt≧b[i]となっていることから判断出来るはず)。つまり@Aを満たすような22個の変数A, B, a[i], b[i]の組が存在すれば、Bを満たす5個の変数s, t, m, n, kを上記のように定めることが出来るから、条件Pが真ならば条件Qも真であることが言える。

次に条件Qが真であれば条件Pも真であることを言う。Bを満足するs, t, m, n, kの値に対して、A=n/(sn+tm+nm), B=m/(sn+tm+nm), a[i]=s+m (i=1〜k), b[i]=t (i=1〜k), a[i]=s (i=k+1〜10), b[i]=t+n (i=k+1〜10) と定めれば、これは@Aを満たしている。従って「条件P:真 ⇒ 条件Q:真」かつ「条件Q:真 ⇒ 条件P:真」が言えるから、条件Pと条件Qは同値である。


あー面倒ですねーこれ、もっとスッキリした数学的証明があるなら僕も教えてほしいです。要は何が言いたいのかとゆーと 『s, tを0以上の整数、m, nを正整数、kを1≦k≦9の範囲の整数とし、子供の人数Nに対して 10s+k・m=10t+(10−k)n=N を満足するようなs, t, m, n, kの組み合わせが存在する。』 ことが(10の倍数でない)N人に分配可能なための必要かつ十分な条件である訳です。またsとt、mとnを入れ替えても同じだから、kは 1≦k≦5 の範囲で考えて良い。 従って53人の場合に分配不可能であることは、N=53, k=1〜5 について調べ上記条件が偽であることを言えば良く、

k=1 のとき、10s+m=10t+9n=53 でこれを満たすt, nの組はない。k=2 のとき、10s+2m=10t+8n=53 で 偶数=53 となるから解なし。k=3 のとき、10s+3m=10t+7n=53 これを満たすt, nの組なし。k=4 のとき、偶数=53 となって解なし。k=5 のとき、5の倍数=53 となって解なし。なので53人では条件を満たすs, t, m, n, kの存在がないため分配不可能であることが言えます。またN人で分配可能であれば、N+10人でも分配可能ということも条件式から判断出来て(N→N+10, s→s+1, t→t+1と置き換えれば良い)、N=21,12,63,24,5,16,27,8,9 は条件を満たせる(いずれもs=t=0で容易に見つかる)ので、これらに10ずつ足してった人数も分配可能だから53人より大きい人数では分配可能だということも解ります。
返信 編集
感服・目からウロコ?宇奈月
ありがとうございます (^^)
やはり簡単にはできないようですね。
細かいところまでは確認できてませんがこれで大丈夫だと思います。
私の証明も似たようなものですが後で書き込んでおきます。