このクイズのヒント
-
ヒント知らないよ
このクイズの参加者(12人)
広告

広告
広告
広告
クイズ大陸関連書籍
![]() ![]() |
![]() |
![]() |
![]()
宇奈月
人数が素数のときでも分配可能な場合はありますよ。
というかできない場合は有限個しかありません。 分割の仕方を色々考えてみましょう。 ![]()
宇奈月
ボケ解答は募集してないんですけどー
![]() 最大値はもっと大きいですよー ![]()
宇奈月
答えを思いつきましたらまたどうぞ
![]() ![]()
宇奈月
その人数の場合は分配可能です。
13人は不可能ですが、19人なら可能です。 ![]()
宇奈月
最大値は有限の値です。
それより多い人数のときはいつでも分配可能になります。 ![]()
宇奈月
最小値は1ですね。1人に10個。
現実的には1億人に分配するのは無理ですが、理論的には可能です。 ![]()
宇奈月
かなりおしいです
![]() その人数の場合は分配可能です。 ○○以上のときには可能ということは言えても、○○未満のときに不可能ということは言えてませんので、もう少しチェックが必要です。 ケーキの大きさをNとすると分数を使わなくていいので楽ですよー ![]()
宇奈月
11人の場合も不可能です
![]() ![]()
宇奈月
もしかして問題を取り違えてます?
分配可能な人数の最大値ではなく分配不可能な人数の最大値を求めてほしいのです。 ![]()
宇奈月
ついにでました!
正解者お一人目! ![]() ![]()
宇奈月
完璧ですね!
![]() 証明もその方法で簡単にできると思います。 ![]()
宇奈月
たぬきおやぢさんと同じお答え!
![]() その人数の場合は分配可能なのです。 もう少し考える必要があります。 ![]()
宇奈月
はい、これが最大値です
![]() 分配不可能な人数も全て書いていただきました。 人数がある数以上のときはいつでも分配可能となることは証明できていると思います。 あとは有限個なので一個一個調べればいいと思います。 ![]()
宇奈月
はい、それが最大値です
![]() その人数では分配不可能なことは割と簡単に証明できます。 11人はアウトでしょう。
![]() ![]() ![]()
宇奈月
アウトとはどういう意味でしょうか?
ルールが守れていないということでしょうか。 ルールを守って分配することが不可能な場合について考えているのですから、ルールが守れてないのは当たり前です ![]() 何にしても、もっと分かりやすい言葉で書いていただきたいですね。 ![]()
宇奈月
81人の場合も分配可能です。
9個のケーキを9等分し、1個のケーキを81等分すると、2種類のケーキが81個ずつできます。 ![]()
宇奈月
即座に答えが分かるような簡単な問題ではありませんので、じっくりお考えください
![]() ![]()
宇奈月
その人数の場合も分配可能です。
チェックがあまーい!ケーキだけに!? ![]() ![]()
宇奈月
「たとえば○○人のとき」は確かにその方法で分配可能です
![]() ですが、それより4人多いときは分配不可能だと思います。 確認してみてください。 ![]()
宇奈月
71人の場合は分配可能です。
元のケーキ1個の大きさを71とします。 7個のケーキを、大きさ7を8個と大きさ3を5個に切り分けます。 3個のケーキを、大きさ7を5個と大きさ3を12個に切り分けます。 これで大きさ7のケーキと大きさ3のケーキがそれぞれ71個できます。 ![]() ![]() 正解を発表します。
最大値は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人の場合に分配不可能なことは簡単に証明できると思っていたのですが、いざ取り組んでみたら予想以上に手ごわかったです。 何とか証明できましたが、かなり長くなってしまいました。 後日書き込みますが、簡単にできるという方がいましたら是非証明お願いします。 囁き欄はなくしておきますので、直接コメント欄にどうぞ。 ![]() ![]() 自分はこんな感じで解きましたかね。とは言えこういう証明をして答えを出した訳ではなく考えたことを数式表現に置き換えてる感じですが。あーあと証明書いててNが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人より大きい人数では分配可能だということも解ります。 ![]()
宇奈月
ありがとうございます
![]() やはり簡単にはできないようですね。 細かいところまでは確認できてませんがこれで大丈夫だと思います。 私の証明も似たようなものですが後で書き込んでおきます。 ![]() ![]() 私の考えた証明を発表しておきます。
53人で分配不可能なことの証明です。 53は10の倍数ではないので、1種類のケーキでは分配不可能です。 2種類のケーキで分配可能と仮定します。 元々のケーキ1個の大きさを1とし、2種類のケーキの大きさをa,bとします。 1個のケーキから得られるa,bの個数が10個についてすべて等しいと個数が10の倍数になりますので、異なるものがあります。 非負整数s,tを使って、1=a*s+b*tと2通り以上に書けるということです。 1=a*s1+b*t1=a*s2+b*t2とすると、a=(t2-t1)/(s1*t2-s2*t1),b=(s1-s2)/(s1*t2-s2*t1) 自然数p,q,mを使って、a=p/m,b=q/mと書けます。 m=p*s1+q*t1ですので、mはp,qの最大公約数で割り切れます。 p,qが互いに素でないときにはp/m,q/mは約分できることになりますので、p,qは互いに素としてよいです。 m=p*s1+q*t1=p*s2+q*t2ですので、p*(s1-s2)+q*(t1-t2)=0です。 s1-s2とt1-t2の正負は異なります。 p*(s1-s2)=q*(t2-t1)=uとするとs1-s2=q*u/pq,t1-t2=p*u/pq uがpqで割り切れるのは明らかですので、u/pqは自然数です。 つまりs1-s2はpの倍数で、t2-t1はqの倍数、それぞれのp,qの係数は一致します。 10個のケーキをそれぞれa*s+b*tという形に分割しますが、その分割の仕方は全部で2通りで可能ということを示します。 分割の仕方が3通り以上あったとします。 m=p*s1+q*t1=p*s2+q*t2=p*s3+q*t3とします。 p,qは互いに素ですので、両方奇数か片方だけ奇数のどちらかです。 両方奇数の場合 s1,s2,s3の中には偶奇が一致するものが必ずあります。 s1,s2の偶奇が等しいとしてよいです。 p,qがともに奇数ですので、s1-s2とt1-t2の偶奇は一致するはずで、偶数になると分かります。 するとt1とt2の偶奇も一致することが分かります。 片方だけ奇数の場合 仮にpが偶数とするとs1,s2,s3の偶奇はすべて一致します。 t1,t2,t3の中には偶奇が一致するものが必ずあります。 t1,t2の偶奇が等しいとしてよいです。 p,qが両方奇数、片方だけ奇数のどちらの場合もs1とs2,t1とt2の偶奇が一致するとしてよいことが分かりました。 このとき、2m=p*(s1+s2)+q*(t1+t2)です。 s4=(s1+s2)/2,t4=(t1+t2)/2とすると、s4,t4は非負整数で、m=p*s4+q*t4となります。 つまり、s1,t1,s2,t2による分割をs4,t4による分割2つに置き換えることができます。 分割の仕方が3通り以上ある場合はこのように1つ減らすことができますので、これを繰り返すことによって最終的に2通りにすることができます。 1=a*s1+b*t1=a*s2+b*t2と2通りのみに分割されているとします。 一つ目の分割をk個、二つ目の分割を10-k個行うとします。 このときaの個数は、k*s1+(10-k)*s2 bの個数はk*t1+(10-k)*t2 これらが53に等しくならなくてはいけません。 k,s1,s2は非負整数で、k≦5の場合についてのみ調べれば十分です。 k=0のとき、0*s1+10*s2は10の倍数ですので53になることはありません。 k=1のとき、1*s1+9*s2=53 s2が最大となるのは(s1,s2)=(8,5)のときで、他の場合もs1>s2です。 t1,t2についても全く同じことが言えますので、t1>t2です。 s1-s2とt1-t2の正負は異なるはずですので条件を満たすことはありません。 k=2のとき、2*s1+8*s2*8は偶数なので53になることはありません。 k=3のとき、常にs1>s2となるので不適です。 k=4のとき、4*s1+6*s2は偶数なので53になることはありません。 k=5とき、5*s1+5*s2は5の倍数ですので53になることはありません。 以上より53人の場合は分配不可能であることが示されました。 ![]() ![]() 53人のときに不可能なことを言うだけであれば
元のケーキの大きさをN,二種類のケーキの大きさをA,B(A,B,N:自然数) A,Bは互いに素としてよい. 53(A+B)=10N 左辺に53の因数があるのでN=53nとおけて A+B=10n@ A,B互いに素ゆえA,nも互いに素. 二種類のケーキを幾つかずつ集めて元のケーキに戻せる. 非負整数i,jを用いて iA+jB=N=53nA i≧jとなるような元のケーキがないとBのケーキの方が多くなって分配不可能. 少なくとも一つはi≧jなるケーキがあり,そのようなi,jに対して@Aより (i-j)A=n(53-10j) 左辺非負で53-10j≧0 53-10j=3,13,23,33,43,53 A,n互いに素ゆえAは53-10jの約数. 同様のことはBにも言え,A,Bがとりうる値の一の位は1,3のいずれかだが@よりA+Bの一の位が0で矛盾. ![]()
宇奈月
なるほど!
最初にA,Bが有理数になることを示す必要があると思いますが、なかなかシンプルでいいですね ![]() ありがとうございました。 ![]() ![]() >黒飴様
すみません先程ケーキの大きさをNとしたときにAとBが互いに素な整数にならない場合があるなどと良く考えもせず書き込んでしまいましたが、そんなことはありませんでした大変失礼致しました(自分は子供の人数をNとしていたので混同していました)、お詫びに今から海に行って泳いできますおやすみなさい。 >宇奈月様 どれだけ10個のケーキをバラバラに切ろうがそれが設問通りに分けられているなら、このバラバラのケーキはたかだか2通りの切り方に再編成することが出来る。よってその対偶も正しく、2通りの切り方のみで分配出来ないのであれば、どう頑張って切り分けようとしても条件を満たすことは出来ないと、そういうことに気づいてしまえば答えが53人以外に成り得ないことは割とあっさり求められたと思います。 でもそれを説明しようとすると難しいですよね、宇奈月様のNo.26の証明も私のNo.25も 「たかだか2通りの切り方に再編成することが出来る。」 ことを言うのに苦労している点では同じはずです。で、そういう考えが先に頭の中にあるとNo.27みたいな証明が思いつかないもんなんですよねぇ不思議なことに。などと言っておけば簡単な証明が思い付かなったことに言い訳出来る気がします ![]() ![]()
宇奈月
そうですね。一つ思いつくとなかなか他のものが思いつかないものです。
>たかだか2通りの切り方に再編成することが出来る 私たちの証明はむしろこれがメインで分配不可能性はおまけですね ![]() これはこれで有意義な結果ですので悲観することはないと思います。 |