19/07/23 20:51:37.10 UZooJXBr.net
前>>554あ、答えかぶったくさい。
問題>>561
n=9のとき、
一回目、9枚の金貨のうち3枚ずつを天秤に載せ釣りあった⇒載せなんだ3枚の金貨のうちのどれかが軽い金貨
一回目、9枚の金貨のうちの3枚ずつを天秤に載せ釣りあわなんだ⇒上がったほうの3枚の金貨のうちのどれかが軽い金貨
二回目、3枚の金貨のうちのどれかとどれかを天秤に載せ釣りあった⇒載せなんだ金貨が軽い金貨
3枚の金貨のうちどれかとどれかを天秤に載せ釣りあわなんだ⇒上がったほうの金貨が軽い金貨
n=9のときは二回目までに特定できる。
∴n=27
601:１３２人目の素数さん
19/07/23 21:09:52.16 aPs+SafE.net
残り3枚は1回で調査できるから3回で調査できる
最大のnは
∴３^3=２７
602:１３２人目の素数さん
19/07/23 23:46:35.35 lBSiFsc1.net
壁にドン
……………黙れよ
603:１３２人目の素数さん
19/07/24 07:16:49.21 br6alVJ1.net
>>555
(n,1) と (5,2)
604:１３２人目の素数さん
19/07/24 07:35:19.55 br6alVJ1.net
>>570
k_max = [ (n-t)/p ], (t=0,1,…,p-1)
定義から
(1+α^s)^n = Σ[t=0,p-1] f_t(n) α^(st), (s=0,1,…,p-1)
α≠1 は１のp乗根だから
Σ[s=0,p-1] α^s = 0,
(1/p)Σ[s=0,p-1] α^{s(t-t')} = δ_{t,t'}
これを使うと
f_t(n) = (1/p)Σ(s=0,p-1) α^(-st) (1+α^s)^n,
本問では p=5.
605:１３２人目の素数さん
19/07/24 14:06:55.87 Pp2BbEe+.net
■正式なお題
n枚の金貨がある(n≧3).
この金貨の中に1枚だけ重さの軽いものが混ざっているが,
それは他のものと見分けがつかない.
天秤を3回使っても, 重さの軽い金貨を特定出来ないという.
このときnの最小値を求めよ.
606:残り3枚は1回で調査できるから3回で調査できる 最大のnは3^3=27 重さの軽い金貨を特定出来ないnの最小値は28. 重いのか軽いのか判定できない金貨が 1枚混入している場合は特定するのに軽い時のみの 2倍の難易度になると思われるので 特定出来ないnの最小値は14.（モーダスポネンス）
607:１３２人目の素数さん
19/07/24 16:51:15.76 LONbBTCB.net
>>514
1回目に右に5枚ABCDE、左に5枚FGHEJで比べるとて右に傾いた場合、
ABCDEのどれかが重い金貨か、FGHIJのどれかが軽い金貨かのため、どれが重さが違う金貨かは10通りの場合がある
天秤1回の比較では、右に傾く、左に傾く、釣り合うの3通りの情報しか得られず、
残り2回の比較では3＾2=9通りの情報しか得られない為、最初に5枚ずつでは3回で特定できない
最初に4枚ずつ比較して傾いた場合は、>>557の通り比較した8枚の中から残り2回で特定できる
最初に4枚ずつ比較して釣り合った場合は、8枚の正常な金貨を使って何枚の不明の金貨から残り2回の比較で特定できるかの話になる
天秤に不明の金貨を4枚と何枚かの正しい金貨を載せて比較して傾いた場合、上で10通りになった時と同様、4通りの場合が考えられ、残り1回の比較では特定できない
よって1回目に釣り合った場合、2回目の比較では3枚まで不明の金貨を載せられる（右に不明3枚、左に正常3枚等）
2回目に3枚載せて釣り合った場合、天秤に不明の金貨2枚を載せると、1回の比較ではどちらが重さが異なる金貨か特定できない
よって1回目、2回目で釣り合った場合は、1枚だけ不明の金貨を載せられる
この時最後まで載せない金貨は1枚までなら特定できるから、3回の比較で特定できる枚数は多くても、
8+3+1+1=13枚
13枚の特定方法は存在>>548するから特定できないnの最小値は14
長いし、不備もあるかな
608:１３２人目の素数さん
19/07/24 19:25:54.11 KD7gjjkL.net
>>548にコメントいただいけましたので、主にコテハンさんをターゲットに、少々補足と、コメントを。
>>577 >>残り2回の比較では3＾2=9通りの情報しか得られない為、最初に5枚ずつでは3回で特定できない
【 10通りの可能性が残った。 天秤は、釣り合う、右に下がる、左に下がるの三通りの結果を引き出せる。 】
【 乗せ方をどのように工夫しようとも、天秤二回の使用では、得られる結果は、三通りの二乗=9通りしかあり得ないので、 】
【 10通りすべてを見極めることなど不可能というもの。 】
この問題では将にこのような視点が重要。
>>548では似たようなケースが途中で発生しています。
最初の天秤使用で釣り合った場合、残り五個のコインから軽重不明の不明のコインを見いださなければならなくなっています。
「上と同様、10通りの可能性を、二回の天秤使用で見極める問題となっているのでは？」
という疑問が発生するかもしれませんが、．．．実は違うのです。
>>548は、「Aが重い、Aが軽い、...、Dが軽い、Eが不明」と、Eのコインについては、軽重を判別していないため、9通り
で済んでいるのです。Eは最後まで、天秤に乗せられずに、「おまえが不正なコインだ」と結論されているのです。
このようなことが可能なのはせいぜい一つ。従って軽重不明コインを天秤 k 回使用で見極められるのは、
(3^k+1)/2が上限だと言うことになります。
じゃ、天秤三回なら、14なのでは？ そうです。ただし、この式が当てはまるのは、本物のコインが十分用意されていることが条件です。
他から持ってきた本物のコイン９枚と、ターゲット１４枚の中から選んだ９枚のコインを比較。
この結果、９枚のコインの中から軽重判明済みの偽コインを探す、か、５枚のコインから軽重不明の偽コインを探す問題に変化します。
これが解決可能なのは、もう説明を加える必要は無いでしょう。キーは別枠で用意されている本物のコインのが有るか無いかです。
609:１３２人目の素数さん
19/07/24 21:00:52.34 KD7gjjkL.net
天秤つながりで、似た問題をお一つ。
初見の方は結構楽しめると思います。
まぁまぁ有名だと思うので、「探せ」ば見つかると思いますが、考えることこそが「面白い」のだと思うので、
ご存じの方、あるいは、探して答えを見つけた方は、この辺ご配慮いただければと思います。
５個の重さの異なる「重り」があります。これを天秤を使って重い順に並べたいと思います。
さて、確実に並べ替えるには、天秤は最低何回使用する必要があるでしょうか？
具体的な手順を思い浮かべながら考える方は「８回？」、理論から考える方は「７回！」と答えるのではないか
と思いますが、さてどうでしょう？
回数と具体的な手順、両方をお考えください。
ちなみに、４個の重りなら、トーナメント方式で、一番重いのを３回で特定し、次に一回戦負け同士を比べて
一番軽い物を特定し、残った物を比べて２位、３位を特定、のように、５回で可能です。
610:１３２人目の素数さん
19/07/24 21:04:57.43 KD7gjjkL.net
ちょっと、訂正します。
前：確実に並べ替えるには、天秤は最低何回使用する必要があるでしょうか？
後：最低何回の天秤使用で、確実に並べ替えられるでしょう。
611:イナ
19/07/24 23:13:27.02 ynJyBfLZ.net
前>>571
問題>>580
一回目、5つの重りのうち1つずつを天秤に載せ、重い重りH(heavy)と軽い重りL(light)を特定すると、
H＞L
二回目、同様に重い重りのH2と軽い重りのL2を特定すると、
H2＞L2
三回目～六回目、もう1つの重りA(another)をH、H2、L、L2のどれかと天秤にかけ、Aの重りの重い順を探るのに最大4回かかり、
H＞A、H2＞A、L＞A、L2＞A
七回目、HとH2を天秤に載せ、
H＞H2
八回目、LとL2を天秤に載せ、
L2＞L
重りの重い順は特定でき、
H＞H2＞L2＞L＞A
最大8回の計量が必要。
三回目～六回目で、
たとえばA＞Lなら、
七回目の計量は不要で、
合計7回の計量でよい。
∴最大8回の計量が必要で、少なくとも7回の計量が必要。
612:イナ
19/07/24 23:20:43.65 ynJyBfLZ.net
前>>581結論の直前を微訂正。
問題>>580
一回目、5つの重りのうち1つずつを天秤に載せ、重い重りH(heavy)と軽い重りL(light)を特定すると、
H＞L
二回目、同様に重い重りのH2と軽い重りのL2を特定すると、
H2＞L2
三回目～六回目、もう1つの重りA(another)をH、H2、L、L2のどれかと天秤にかけ、Aの重りの重い順を探るのに最大4回かかり、
H＞A、H2＞A、L＞A、L2＞A
七回目、HとH2を天秤に載せ、
H＞H2
八回目、LとL2を天秤に載せ、
L2＞L
重りの重い順は特定でき、
H＞H2＞L2＞L＞A
最大8回の計量が必要。
三回目～六回目で、
たとえばA＞Lなら、
八回目の計量は不要で、
H＞H2＞L2＞A＞L
合計7回の計量でよい。
∴最大8回の計量が必要で、少なくとも7回の計量が必要。
613:１３２人目の素数さん
19/07/24 23:45:23.76 KD7gjjkL.net
ある手順書に従ってソートすると、「運がよければ４回だけど、悪ければ１０回必要」ということがあるかもしれません。
また別の手順書に従ってソートすると、「運がよければ５回だけど、悪ければ９回必要」
．．．
等といういう事があるかもしれません。
問題では、「確実に並べ替える」ことを条件にしてます。
運が悪くても、これこれの回数の使用権さえあれば、ソートを必ず完遂できる、という、その最小の回数と、手順書の中身を問うています。
従って、文頭の「ある手順書」のそれは１０回、「別の手順書」は９回ということになります。
これらはもちろん不正解の値です。
>>581、>>582
８回と言うことですが、正解ではありません。
『理論から考える方は「７回！」』と書いた理由を考えてみてください。
別の視点で眺めてみてください。
614:１３２人目の素数さん
19/07/26 15:49:39.73 y+f8ikS+.net
はたしてミスがあるか
615:１３２人目の素数さん
19/07/26 16:01:11.74 y+f8ikS+.net
『n枚の金貨がある(n≧2).
この金貨の中に1枚だけ重さの違うものが混ざっているが,
それは他のものと見分けがつかない.
天秤を3回使っても, 重さの違う金貨を特定出来ないという.
このときnの最小値を求めよ』
■重さの違う金貨を特定出来る最大値は13
天秤に1枚づつ以上載せて釣り合えばその金貨は
正式な金貨であることが確定する
最初に4枚づつ載せて釣り合えばこの8枚は正式が確定
残り5枚の中にニセ金貨がある
傾けばこの8枚の中にニセ金貨がある
ニセを含む5枚の内、3枚と正式な金貨3枚を比べる
釣り合えば残り2枚の内の1枚を情報が確定している
正式な金貨と比べればどの金貨がニセかが確定する
釣り合わなければ、『重いか軽いかが確定している3枚』と
なるので次の一回で確定する
4枚づつ計8枚が傾けば、どちらかに
重いか軽いかの金貨がある
この場合、互いの4枚から1枚づつをエクスチェンジする
そこに情報確定済みの正式な金貨を片側に3枚加えて
4枚づつを計る
釣り合えば正式な金貨3枚の代わりに取り除いた
3枚の金貨が『重いか軽いかが確定している3枚』となるので
次の一回で確定する
傾きが逆になったときはエクスチェンジした金貨がニセ
この二つの金貨のうちどちらかを正式な金貨と比べれば
616: 情報が確定 傾が変化しなければエクスチェンジしなかった3枚の金貨が 『重いか軽いかが確定している3枚』となる これらの時、ニセ金貨が重いか軽いかも自動判定される 金貨14枚だとさらに1回の調査が必要になる 以上により、 重さの違う金貨を特定出来ないnの最小値は14.
617:１３２人目の素数さん
19/07/26 16:37:22.35 99q/BPu9.net
それでは金貨14枚だと出来ないことを示せていると言えないんじゃないかな
全然別の方法で可能かも知れない
別の方法であろうと出来ないことを示す必要があるけどかなり面倒くさい
14枚以上だと出来ないことを示すのは重いか軽いかまで特定することが求められている問題の方がずっと簡単だね
（13枚でも出来ないけどこれを示すのはちょっとだけ面倒）
618:１３２人目の素数さん
19/07/26 19:47:17.79 4Ej4vPb0.net
検証対象の１４枚しかなければ、天秤に載せる枚数により、次のような分岐が発生します。
７：７：０ → 重重重重重重重 軽軽軽軽軽軽軽 （14通り）
６：６：２ → 重重重重重重 軽軽軽軽軽軽 本本 (12通り)／ 本本本本本本本本本本本本 不不 （4または3通り）
５：５：４ → 重重重重重 軽軽軽軽軽 本本本本 (10通り)／ 本本本本本本本本本本 不不不不 （8または7通り）
４：４：６ → 重重重重 軽軽軽軽 本本本本本本 (8通り)／ 本本本本本本本本 不不不不不不 （12または11通り）
いずれの手を取ろうとも、必ず、9通り以下に分岐するような手順は存在しません。
しかし、本物のコインが一枚でも有れば、可能です。（前回は簡便のため９枚を使いましたが、１枚でもok）
本物１枚とターゲットの４枚を合わせた５枚と、ターゲット５枚を比べると、
[本]重重重重 軽軽軽軽軽 本本本本本 (9通り) ／ [本]本本本本本本本本本 不不不不不 (10または9通り)
（軽と重を逆にした物もあるが、本質的な差はないので省略）
のように分岐します。どちらになろうとも9通りです。傾いた場合の次の手は
重重重軽軽軽 と [本]本本本本本
重軽混合側が下がれ／上がれば、三つの重／軽のいずれか、釣り合えば、今天秤に載せていない、重軽軽のどれかが偽物です。
つまり、１４枚での可否は、別枠で本物のコインが用意されているかどうかに依ります。
不：重い偽物、軽い偽物、本物、いずれの可能性もある状態
重：重い偽物か本物であることが確定している状態
軽：軽い偽物か本物であることが確定している状態
本：本物と確定している状態
619:イナ
19/07/27 20:46:36.70 W9txtZbT.net
前>>582
>>585
n=14のとき、
一回目、5枚ずつを天秤に載せ、釣りあったら、載せなんだ4枚の中に重さの違う金貨がある。
二回目、残り4枚のうち1枚ずつを天秤に載せ、釣りあったら、載せなんだ2枚のうちのどっちかが重さの違う金貨だとわかる。
三回目、載せなんだ2枚のうちの1枚を天秤に載せ、載せなんだ2枚以外の金貨を1枚もう一方の天秤に載せ、釣りあったら、
載せなんだ2枚のうち、三回目も載せなんだほうの金貨が重さの違う金貨だと特定できる。
三回目、載せなんだ2枚のうちの1枚を天秤に載せ、載せなんだ2枚以外の金貨を1枚もう一方の天秤に載せ、釣りあわなんだら、
載せなんだ2枚のうち、三回目は載せたほうの金貨が重さの違う金貨だと特定できる。
一回目、5枚ずつを天秤に載せ、釣りあわなんだら、載せた10枚の中に重さの違う金貨がある。
二回目、片方の5枚のうち2枚ずつを天秤に載せ、釣りあったら、外した1枚が重さの違う金貨だと特定できる。
二回目、片方の5枚のうち2枚ずつを天秤に載せ、釣りあわなんだら、載せた4枚の中に重さの違う金貨がある。
三回目、4枚のうち1枚ずつを天秤に載せ、釣りあったら、載せなんだ2枚のうちのどっちかが重さの違う金貨だが、どっちか特定できない。―①
三回目、4枚のうち1枚ずつを天秤に載せ、釣りあわなんだら、載せた2枚のうちのどっちかが重さの違う金貨だと特定できる。
①のように三回目までにかならず特定できるとはかぎらない。
∴n＜14
（n=13も怪しいけど）
620:１３２人目の素数さん
19/07/27 21:37:30.68 AFDTz7Zf.net
>>588
それだと答えとしてはバツだよ
> 一回目、5枚ずつを天秤に載せ、釣りあったら、載せなんだ4枚の中に重さの違う金貨がある。
> 二回目、残り4枚のうち1枚ずつを天秤に載せ、釣りあったら、載せなんだ2枚のうちのどっちかが重さの違う金貨だとわかる。
…
> 三回目、4枚のうち1枚ずつを天秤に載せ、釣りあったら、載せなんだ2枚のうちのどっちかが重さの違う金貨だが、どっちか特定できない。―①
> 三回目、4枚のうち1枚ずつを天秤に載せ、釣りあわなんだら、載せた2枚のうちのどっちかが重さの違う金貨だと特定できる。
の方法では3回で特定できない、ということを示しただけで、
3回で特定できる他の方法がある可能性を否定できず、
> ∴n＜14
と結論付けられない
ついで
> ①のように三回目までにかならず特定できるとはかぎらない。
この問題では、「三回目までにかならず特定できるとはかぎらない」ということを「三回目で特定できない」と言っているからね
621:イナ
19/07/27 22:35:09.85 W9txtZbT.net
前>>588
>>585
n=13のとき、
一回目、5枚ずつを天秤に載せ、釣りあったら、載せなんだ3枚の中に重さの違う金貨がある。
二回目、残り3枚のうち1枚ずつを天秤に載せ、釣りあったら、載せなんだ1枚が重さの違う金貨だとわかる。
二回目、残り3枚のうち1枚ずつを天秤に載せ、釣りあわなんだら、載せた2枚のうちのどっちかが重さの違う金貨だとわかる。
三回目、載せた片方を載せなんだ1枚の金貨と交換し、釣りあったら、二回目載せて三回目載せなんだ1枚が重さの違う金貨だと特定できる。
一回目、5枚ずつを天秤に載せ、釣りあわなんだら、載せた10枚の中に重さの違う金貨がある。
二回目、片方の5枚のうちの2枚ずつを天秤に載せ、釣りあったら、載せなんだ1枚かもう一方の5枚の計6枚の中に違った重さの金貨がある。
三回目、6枚のうちの2枚ずつを天秤に載せ、釣りあったら、載せなんだ2枚のうちの1枚が重さの違う金貨だとわかるがどっちが重さの違う金貨かは特定できない。―①
二回目、5枚のうちの片方のうちの2枚ずつを天秤に載せ、釣りあわなんだら、載せた4枚の中に重さの違う金貨がある。
三回目、4枚のうちの1枚ずつを天秤に載せ、釣りあったら、載せなんだ2枚のうちのどっちかが重さの違う金貨だが、どっちが重さの違う金貨かは特定できない。―②
三回目、4枚のうちの1枚ずつを天秤に載せ、釣りあわなんだら、載せた2枚のうちのどっちかが重さの違う金貨だが、どっちが重さの違う金貨かは特定できない。―③
①②③より、計量の結果いかんによっては特定できないことがある。
622:１３２人目の素数さん
19/07/27 22:45:21.77 AFDTz7Zf.net
>>590
だからぁ、
特定できないことがある手順を一つ書いたって、何の意味もないんだって
意味があるのは、
必ず特定できる手順を一つでも示すか、
必ず特定できる手順が「一つも存在しない」ことを示すか、
のどちらか
ついでに、
1回目に5枚ずつ天秤に乗せると3回では特定できなくなることは、上で書かれているよ
623:１３２人目の素数さん
19/07/27 22:57:17.98 lY/3MUd+.net
相手しない方がいいと思うよ
624:１３２人目の素数さん
19/07/27 23:41:15.88 YoK4P1y1.net
誰とは言わないけど、あたかも
「具体例や値の評価など、少しでも新たな進捗が出せたらそれは目覚ましい結果である」であるかのような文脈で、
ここに出題される全ての問題、それもほとんどが答えがはっきりしてるようなものに対して回答や考察を垂れ流し続けるってのは、
あまりにも一つの問題を買い被りすぎというか、そこまで理解するための知識は備わってても使いこなす頭がないだけなのかはわからんけど
限度を越したら荒らしになるってことは理解してほしい
一回や二回ならまだしも、ここまで続いてるのを見るとどうもそのレベルのことも理解できてないみたいだし
もっと難しい問題で撥ねるか、おとなしくＮＧするのがいいんかなあって気はするけど…
625:１３２人目の素数さん
19/07/27 23:55:49.72 GqDYCZct.net
みんな優しいんだね。はっきりと
「イナとかいうコテハンは何も理解していないバカタレである」
と言えばいいのに。
626:１３２人目の素数さん
19/07/27 23:59:13.74 YoK4P1y1.net
言い出しっぺの法則なんで、幻となった今年のMathpowerの数学の決闘用に用意してた問題から一つ
二進法表記した時に１が奇数個現れるような非負整数のことをオディアスと呼ぶ。
次を満たす一変数実多項式 f が存在することを示せ：
任意の正の整数 n について、kn がオディアスになるような f(n) 以下の正の整数 k が存在する。
627:１３２人目の素数さん
19/07/28 01:30:13.77 0iorfM2k.net
>>595
f(n) = 9n が条件を満たす。
∵) n は奇数としてよい。
n または 3n のいずれかの末尾桁が01となる。
その数をmとし、mと同じ桁数で先頭桁と末尾桁のみ1で他の桁は0である自然数をlとすればlmはオディアスである。
さらにk = lm/n は9n以下の整数である。
628:１３２人目の素数さん
19/07/28 08:30:07.86 CY0YOq6P.net
>>596
うわめっちゃシンプル…思いつかんかった…
正解です
629:１３２人目の素数さん
19/07/28 12:11:11.58 sVd3nKsH.net
コテ付けてくれてるんだからNGすればいい。邪魔なだけで無害
むしろコテのない出題ガイジが邪悪だ
630:１３２人目の素数さん
19/07/28 16:58:55.97 i2F+0TFg.net
■重さの違う金貨を特定出来る最大値は13
631:イナ
19/07/28 17:02:42.71 g3P0hKPa.net
前>>590問題>>514>>585
n=9のとき>>544>>549どうしても特定できない。
n=8のとき、
一回目、3枚ずつを天秤に載せ、釣りあったら、残り2枚のうちのどっちかの金貨が重さの違う金貨だとわかる。
二回目、残り2枚のうちの 1枚を片方の天秤に載せ、もう一方の天秤に残り1枚以外の金貨を載せ、釣りあったら、残り2枚のうちのもう1枚が重さの違う金貨だと特定できる。
一回目、3枚ずつを天秤に載せ、釣りあわなんだら、載せた6枚の中に重さの違う金貨がある。
二回目、6枚のうちの2枚を片方の天秤に載せ、もう一方の天秤に6枚のうちの別の2枚を載せ、釣りあったら、載せなんだ2枚の中に重さの違う金貨がある。
二回目、6枚のうちの2枚を片方の天秤に載せ、もう一方の天秤に6枚のうちの別の2枚を載せ、釣りあわなんだら、載せた4枚の中に重さの違う金貨がある。
三回目、載せなんだ2枚のうちの1枚を片方の天秤に載せ、もう一方の天秤に載せなんだ2枚のうちのもう1枚以外の金貨を載せ、釣りあったら、載せなんだ2枚のうちのもう1枚が重さの違う金貨だと特定できる。
三回目、載せなんだ2枚のうちの1枚を片方の天秤に載せ、もう一方の天秤に載せなんだ2枚のうちのもう1枚以外の金貨を載せ、釣りあわなんだら、二回目で載せなんだ2枚のうちの三回目で載せた1枚が重さの違う金貨だと特定できる。
n=7のとき、>>538
n=6のとき、>>537
n=5のとき、>>536
632:イナ
19/07/28 17:04:43.58 g3P0hKPa.net
前>>600後半。
n=4のとき、(つづき)
一回目、4枚のうちの1枚を片方の天秤に載せ、4枚のうちの別の1枚をもう一方の天秤に載せ、釣りあったら、載せなんだ2枚のうちのどっちかが重さの違う金貨だとわかる。
一回目、4枚のうちの1枚を片方の天秤に載せ、4枚のうちの別の1枚をもう一方の天秤に載せ、釣りあわなんだら、載せた2枚のうちのどっちかが重さの違う金貨だとわかる。
二回目、載せなんだ2枚か載せた2枚かどっちの2枚にしろ2枚のうちの1枚を片方の天秤に載せ、もう一方の天秤に2枚のうちの1枚以外の金貨を載せ、釣りあったら、2枚のうちの載せなんだほうの1枚が重さの違う金貨だと特定できる。
二回目、載せなんだ2枚か載せた2枚かどっちの2枚にしろ2枚のうちの1枚を片方の天秤に載せ、もう一方の天秤に2枚のうちの1枚以外の金貨を載せ、釣りあわなんだら、2枚のうちの載せた1枚が重さの違う金貨だと特定できる。
n=3のとき、
一回目、3枚のうちの1枚を片方の天秤に載せ、もう一方の天秤に別の1枚を載せ、釣りあったら、載せなんだ1枚が重さの違う金貨だと特定できる。
一回目、3枚のうちの1枚を片方の天秤に載せ、もう一方の天秤に別の1枚を載せ、釣りあ�
633:墲ﾈんだら、載せた2枚のうちのどっちかが重さの違う金貨だとわかる。 二回目、2枚のうちの1枚を片方の天秤に載せ、もう一方の天秤に載せなんだ1枚を載せ、釣りあったら、2枚のうちの一回目に載せ、二回目は載せなんだほうの1枚が重さの違う金貨だと特定できる。 二回目、2枚のうちの1枚を片方の天秤に載せ、もう一方の天秤に載せなんだ1枚を載せ、釣りあわなんだら、2枚のうちの一回目に載せ、二回目も載せた金貨が重さの違う金貨だと特定できる。 n=2のときは、2つの重さの違う金貨があるだけでどっちの金貨が重さの違う金貨かは特定できない。 以上により、n≧3とするなら、nの最小値は、n=9
634:１３２人目の素数さん
19/07/28 17:22:03.77 i2F+0TFg.net
1回で調査可能な最大数は3
2回で調査可能な最大数は8
3回で調査可能な最大数は13
4回で調査可能な最大数は21
0, 3, 8, 13, 21, 34, 47, 64, 84, 105, ...
635:１３２人目の素数さん
19/07/28 18:29:23.47 O7zgaRnw.net
少なくとも(3^n-1)/2で可能である解は見つけた事あるな。
それが最大の証明は知らないけど。
636:１３２人目の素数さん
19/07/28 22:32:25.50 f0Sq6OzI.net
>>600
> n=9のとき>>544>>549どうしても特定できない。
> 以上により、n≧3とするなら、nの最小値は、n=9
あなたが特定出来なかったからといって、n=9では特定することが不可能だとは言えない
> 一回目、3枚ずつを天秤に載せ、釣りあったら、残り2枚のうちのどっちかの金貨が重さの違う金貨だとわかる。
1回目に3枚ずつ乗せると9枚以上を特定することは出来なくなる
これは1枚ずつ、2枚ずつも同じ
637:１３２人目の素数さん
19/07/28 22:34:57.91 5KI+Tx/u.net
>>602
ん？一回で３つから偽物特定するのは無理では？
２つを比べて傾いた時に、どちらが偽物なのかが判別できないから…
>>603 の通り 1, 4, 13, 40, … (3^n-1)/2 が正しい数列かと
証明の途中まではおそらくこんな感じ
もしN個の調査中に一回でも傾いたら、
最終的に得られる「どのおもりが偽物か」という情報と合わせて
「偽物が本物と比べて重いか軽いか」までわかるから、
偽物が本物より重いか軽いかを知る必要が無く偽物が判明するただ一つの場合、すなわち
「n回全ての比較で傾かない」
場合と合わせれば、n回の比較で少なくとも (N-1)*2+1 回の場合を区別できる必要がある。
従って (N-1)*2+1 ≦ 3^n より N≦(3^n+1)/2.
あとは、最初に何個ずつ比較したとしても、傾いた場合に区別すべき場合の数が偶数になるため、
情報の余りが生じてしまうことから等号が成立することはない、みたいに
638:604
19/07/29 01:15:35.61 yO1OPJ8K.net
>>604
> 1回目に3枚ずつ乗せると9枚以上を特定することは出来なくなる
> これは1枚ずつ、2枚ずつも同じ
1回目に3枚ずつ乗せると特定できなくなるのは12枚以上で、
11枚までは特定することはできたな
>>600で8枚が書けてなぜ9枚が出来ないのかわからない
639:１３２人目の素数さん
19/07/29 01:20:21.21 9wmhrWpm.net
n,mを正の整数とするとき、
α=2^(1/n)+3^(1/m)
とおく。整数係数の多項式f(x)で、f(α)=0を満たすものが存在することを示せ。
可能であれば、高校レベルまでの数学でお願いいたします。
640:１３２人目の素数さん
19/07/29 16:55:07.35 HPuHfNC1.net
■n回の調査で判明する最大値
Table[2(n^2-n)+1,{n,3,20}]
{13, 25, 41, 61, 85, 113, 145, 181, 221, 265, 313, 365, 421, 481, 545, 613, 685, 761}
■n回の調査で判明しない最小値
Table[2(n^2-n+1),{n,3,20}]
{14, 26, 42, 62, 86, 114, 146, 182, 222, 266, 314, 366, 422, 482, 546, 614, 686, 762}
641:イナ
19/07/29 17:10:15.41 gBsagA9w.net
前>>601問題>>514>>585
>>600アンカー訂正。
n=9のとき、
>>554一回目、4枚ずつ―
>>549一回目、3枚ずつ―
一回目、2枚ずつ―
以上により、どうしても特定できない。
n=8のとき、（以下同文）
642:１３２人目の素数さん
19/07/29 18:06:17.78 Y/0wA4MK.net
n=9の時可能である方法上がってますがな。
643:１３２人目の素数さん
19/07/29 18:22:17.18 HPuHfNC1.net
>>605
4回で40枚から特定は不可能
644:１３２人目の素数さん
19/07/29 18:24:23.25 d5vj7LRN.net
>>600の枚数を1枚増やすだけでn=9が解けるのに何故>>549で思考停止するのか？
4枚ずつの解も上にある
645:イナ
19/07/29 18:26:20.82 gBsagA9w.net
前>>609
>>610
題意、>>514「それ（金貨）は他のものと見分けがつかない」に素直にした
646:がって解答すべきだ。題意に反する答案を認めるわけにはいかない。 マジックは使ってません、付箋は使います、置き場所を決めました、天秤に載せるときは付箋を外しました、とかいうズルを認めるわけにはいかない。
647:１３２人目の素数さん
19/07/29 18:29:59.66 C5pnbMnr.net
>>613
>>556とか
648:１３２人目の素数さん
19/07/29 18:30:49.24 6L7yKrQP.net
>>607
f(x) の高次項の係数は (x^n - 2)^m + (x^m - 3)^n - x^(mn) に似てるけど、違うだろな....ｏｒｚ
649:１３２人目の素数さん
19/07/29 18:38:55.59 IzIfrw09.net
>>613
見分けがつかないならどうやっても識別不可能だね
650:イナ
19/07/29 18:42:51.10 gBsagA9w.net
前>>613
>>616見分けがつかない金貨を見分けるための天秤じゃないのか。あきらめないでほしい。
651:１３２人目の素数さん
19/07/29 18:54:13.74 C5pnbMnr.net
もしかして見分けがつかないから二回目以降の測定で１回目にどれとどれを載せたかわかるなくなるって意味にとるとか？？？
そんなルールならn=3ですでに不可能じゃんwwwww
652:１３２人目の素数さん
19/07/29 20:25:28.22 YC4en7ro.net
>>611
40枚から4回で特定は可能。情報理論的には、(3^4-1)/2=40 だから可能と考えられるし、実際に、下に示すような方法で可能。
以後、次の記号を使うことにする。
不：重いかもしれないし、軽いかもしれないし、正しいかもしれないコイン
重：重いかもしれないし、正しいかもしれないコイン
軽：軽いかもしれないし、正しいかもしれないコイン
正：正しいコイン
一回目に、13枚ずつ載せればよい。すると、「重13軽13正14」または、「不14正26」に分かれる。
「重13軽13正14」は[重9軽5]と[正10重4]にして比較すればよい。すると、「重9正31」か「軽5重4正31」か「軽8正32」に分かれる。
（分岐は、天秤の結果が、「左が重い」、「右が重い」、「釣り合う」に対応。）
「不14正26」は、[正1不4]と[不5]にして比較すればよい。すると、「重4軽5正31」か「重5軽4正31」か「不5正35」に分かれる。
「重4軽5正31」は、[重2軽2]と[重1軽1正2]にして比較すればよい。すると、「重2軽1正37」か「軽2重1正37」か「重1軽2正37」に分かれる。以後略。
「不5正35」は、[正3]と[不3]にして比較すればよい。すると、「軽3正37」か「重3正37」か「不2正38」に分かれる。以後略
ちなみに、正しいコインが別枠で一枚有れば41枚、つまり「不41正1」から４回で可能。
[正1不13]と[不14]で比較すれば、「重13軽14正15」か「軽13重14正15」か「不14正28」に分かれます。以後略。
653:１３２人目の素数さん
19/07/29 20:52:27.47 HPuHfNC1.net
>>619
一回目に、13枚ずつ載せてもどちらのグループに重いか軽いかの
金貨があるのかの判定はできない
『ニセがどちらかにある』という情報だけ
重いか軽いかの確定判定には、もう一回必要になる
654:１３２人目の素数さん
19/07/29 20:56:39.17 HPuHfNC1.net
もっと根本的に
「不14正26」に分かれたときに
残り3回で不14は特定できないと自分で書いている
655:１３２人目の素数さん
19/07/29 21:25:37.32 d5vj7LRN.net
>>620,621
> 残り3回で不14は特定できないと自分で書いている
>>578
> 一回目に、13枚ずつ載せてもどちらのグループに重いか軽いかの
> 金貨があるのかの判定はできない
2回目：「重+軽26枚」の時
「重＋軽9枚」、「重＋軽9枚」かつ左右の重の数同士、軽の数同士が同数で比較で
傾けば1回目と傾きが同じ9枚(1回目、2回目ともに重い側、またはともに軽い側)、釣り合えば残りの9枚に絞られ、
「重＋軽9枚」、「重＋軽9枚」、「重＋軽9枚」に分岐
3回目：「重+軽9枚」の時
「重＋軽3枚」、「重＋軽3枚」かつ左右の重の数同士、軽の数同士が同数で比較で
「重＋軽3枚」、「重＋軽3枚」、「重＋軽3枚」に分岐
4回目：同様で終了
656:１３２人目の素数さん
19/07/29 21:37:26.10 HPuHfNC1.net
>>619
3回目の調査で
「重2軽1正37」か「軽2重1正37」か「重1軽2正37」の情報を得たとして
そこから残り1っ回で、具体的どうやってニセを判定するのかね(´･ω･`)？
657:１３２人目の素数さん
19/07/29 21:44:56.80 YC4en7ro.net
>>620 >>621
傾いた場合には、「重13軽13正14」になる。26通りのいずれかであるかを特定すればよいだけ。3^3=27以下なので、可能。
釣り合った場合には、「不14正26」となる。
14の二倍は28で、3^3=27を超えて、不可能ではないかと思われるかもしれない。
>>残り3回で不14は特定できないと自分で書いている
との書き込みがあるが、私はこ
658:れまで、一貫して「不14」だけなら、不可能だが、 別枠で正しいコインが有れば、可能だと書いている。 「別枠」というのは、いわば、「初回」に限った条件と言える。 二回目以降は、副作用で正しいコインが判明し、それが利用できるから。 目的は、14枚のコインの中から、不正な一枚を特定し、それが軽いのか重いのか見極める事ではない。 ただ単に不正な一枚を特定すればよい。天秤に載せて調査し、偽物を見極める場合、必ず軽重の情報も 付加されてしまう。従って、14枚の中から一枚を3回の天秤使用では不可能ではないかと思われるかも しれない。が、これは正しくない。 14枚から1枚を取りの除き、13枚のコインの中から、重い偽物を特定するか、軽い偽物を特定するか すべてが本物と確認すればよい。そうすれば、26通りに、すべて本物という一通りを加え、 27通りに落ち着き、情報理論的上限27に納めることができる。 最初に取り除かれたコインは、一度も天秤に載せら得ることなく、「おまえは偽物」と烙印を押される．．．かもしれない。
659:１３２人目の素数さん
19/07/29 21:45:14.43 d5vj7LRN.net
>>623
> 「重2軽1正37」か「軽2重1正37」か「重1軽2正37」の情報を得たとして
> そこから残り1っ回で、具体的どうやってニセを判定するのかね(´･ω･`)？
ここまできてそれ？
「重1、重1」または「軽1、軽1」で比較
傾けば、「重1、重1」なら重い方、「軽1、軽1」軽い方、釣り合えば残り
660:１３２人目の素数さん
19/07/29 21:46:55.55 YC4en7ro.net
>>623
>>「重2軽1正37」か「軽2重1正37」か「重1軽2正37」の情報を得たとして
いずれの場合も、天秤の片方に[正2]、他方に[重1軽1] と載せればよい。
661:１３２人目の素数さん
19/07/29 21:54:57.49 YC4en7ro.net
もちろん、>>625さんの方法でもok
662:１３２人目の素数さん
19/07/29 22:06:51.73 HPuHfNC1.net
>>622
『2回目：「重+軽36枚」の時
「重9＋軽9枚」、「重9＋軽9枚」かつ左右の重の数同士、
軽の数同士が同数で比較』に変更したとして
調査不能になるのはなぜかね(´･ω･`)？
663:１３２人目の素数さん
19/07/29 22:26:17.54 C5pnbMnr.net
一般にコインの枚数mが3以上(3^n-1)/2以下の場合帰納法を使って以下のようなn行m列の行列が存在する事が示せる。
全ての要素はLRS。
どのm文字からなるn個の行も含まれるLとRが等しい。
x,yを異なる部分列としzをyのLとRを入れ替えた列とするとき、x、y、zは全て相異なる。
これでm枚のコインの場合、n回で可能と示せる。
ただしm=(3^n-1)/2の場合には全てSからなる列を含むので、偽コインの重い、軽いは判定できないケースを含む。
これが最良である事もちょっと頑張れば出来た。
偽コインの重い軽いを特定したい場合には上の評価-1が最大枚数になる。
664:１３２人目の素数さん
19/07/29 22:34:13.16 d5vj7LRN.net
>>628
> 『2回目：「重+軽36枚」の時
> 「重9＋軽9枚」、「重9＋軽9枚」かつ左右の重の数同士、
> 軽の数同士が同数で比較』に変更したとして
> 調査不能になるのはなぜかね(´･ω･`)？
念のため、>>622の
> 「重＋軽9枚」
は重と軽の合計枚数が9枚であって、
> 「重9、軽9」
ではないからね
「重+軽36枚」の時、 「重9＋軽9枚」、「重9＋軽9枚」かつ左右の重の数同士、軽の数同士が同数、あまり0で比較で比較すると、
釣り合う場合の事象数は0通り、
右に傾く場合の事象数は、右の重9通り、左の系9通り、合計18通りで、残り二回の比較で得られる情報量3＾2=9では特定できない
左に傾く場合も同様
665:１３２人目の素数さん
19/07/29 22:39:50.80 YC4en7ro.net
>>628
天秤を使うと、一般に、左に傾く、右に傾く、釣り合うのいずれかの結果を得ます。
現在、可能性が z 通り有ったとして、ある載せ方をして、天秤を使った結果、
左に傾いた場合：可能性 z1 通り
右に傾いた場合：可能性 z2 通り
釣り合った場合：可能性 z3 通り
となるとします。当然、 z = z1 + z2 + z3 です。
可能性が z 通りあるとき、天秤を m = {log[3](z)} 回使用して、偽物を特定できます。 ；{x}は切り上げ関数とする
「ある載せ方」によって、z を、z1、z2、z3、のいずれかに分岐しますが、この時、
m-1 ≧ {log[3](z1)}
m-1 ≧ {log[3](z2)}
m-1 ≧ {log[3](z3)}
のすべて満たすような載せ方でないと、その載せ方は「失敗」です。至極当たり前のことです。が、
>>調査不能になるのはなぜかね(´･ω･`)？
に対しては、このような回答しかできません。
666:１３２人目の素数さん
19/07/29 23:01:54.95 HPuHfNC1.net
エクスチェンジした金貨グループは
残り調査回数が2回残っている�
667:ﾈら5枚まで判定可能だ という事は、>>619[重9軽5]と[正10重4]は [重9軽5]と[正9重5]のエクスチェンジ判定に置き換えることができる ゆえに、28枚がエクスチェンジで判定可能となり 「重14軽14正14」の合計42枚の中からニセが確定できる
668:１３２人目の素数さん
19/07/29 23:11:30.15 d5vj7LRN.net
>>632
> 「重14軽14正14」の合計42枚の中からニセが確定できる
出来ない
可能性のある事象数は重14+軽14=28通り
3回の比較で得られる情報量は3＾3=27通りでは特定できない
669:１３２人目の素数さん
19/07/29 23:35:06.75 1Z7KEzl/.net
面白くないから、さ、もう止めて
670:１３２人目の素数さん
19/07/29 23:37:50.28 Y/0wA4MK.net
単純に情報量だけで14枚が不可能をいうのはちょつと難しい。
例えば絶対ホンモノだというコインが一枚あれば14枚でも可能。
何故これが可能になるかというと13枚の軽重で26通りに加えて一度も傾かないという場合に一度も載せてないコインがニセモノという軽重を確定出来ない一通りを追加できるので
14枚でも偽コインを特定できる可能性は残っており、実際絶対ホンモノコインが一枚あればそのような測定が可能である事が示せる。
つまり絶対ホンモノコインがない場合にも14枚でも単純に情報量だけでは不可能と言い切る事は出来ず、そこは一工夫必要。
671:１３２人目の素数さん
19/07/29 23:50:44.86 YC4en7ro.net
>>635
14枚の場合について >>587 では、本物のコインが別枠で用意されている場合と、されていない場合に分け、
前者は可能、後者は不可能であることを、具体的な手順を添えて、示してあります。ご覧ください。
672:１３２人目の素数さん
19/07/30 00:09:00.73 zNLLWM38.net
>>636
なるほど。そこはもうクリアしてるんですね。
ちなみに私の見つけた一工夫は
１回目載せないコインの枚数は高々5枚。
何故ならは6枚以上残して釣り合うと、残る可能性は12通り。
一度も載せないコインは高々一枚でそれが重い偽コインと軽い偽コインの場合をまとめても11通り残ってしまう。
１回目に乗せるコインの枚数は高々8枚。
何故ならは10枚以上乗せて傾くと可能性が10通り残る。
ま、情報量についての議論をちょい精密化しただけですか。
同様にしてn回の場合、(3^n+1)/2枚は不可能が示せます。
673:イナ
19/07/30 07:56:32.52 O94O3VWc.net
前>>617問題>>514
>>618
n=3のとき、
>>601により、
特定できる。
674:１３２人目の素数さん
19/07/30 08:10:05.74 32/Qu64M.net
>>638
イナの解釈なら>>601もアウトでしょ？
見分けがつかないんだから、１回目釣り合わなかったら、乗せたどっちかが偽コインだけど、天秤から下ろした瞬間もうどれを乗せたからわからなくなるなら、１回目の情報はに2回目に使えない。
あくまで載せた二枚の両方がホンモノである偶然が起きた時しか偽コインを特定できないから確実に偽コインを特定する方法ないでしょ？
よって君の解釈ならn=3が最小値でいいじゃん。
675:１３２人目の素数さん
19/07/30 08:27:44.09 ppLmSMDR.net
情報が残らないなら3回って条件にまるで意味がなくなるわな
そういう条件だと何枚載せようと釣り合わなかったら当然特定出来ない
全体が奇数枚で1枚だけを残して他を同枚数ずつ乗せて釣り合った場合だけ残した1枚が偽だとわかるが
偶然に頼ることになるので最初が3枚である場合ですら確実に何回で特定出来るという回数は存在しない
最初が何枚であろうと最小値なし
676:イナ
19/07/30 11:36:36.51 O94O3VWc.net
前>>638問題>>514
>>639
答え>>600-601はセットです。
計量した結果はさすがに金貨を天秤から下ろしても記憶に残ります。あくまでも三回目まで計量した結果どうしても特定できないnの最小値はいくつかということ。
n=3のときは特定できるから候補にはならない。
天秤に載せる前の金貨をこれはAだ、Bだ、Eだと印をつけて見分けるのは、本来計量しなければ見た目は同一であるはずの金貨を選んで天秤に載せるという題意にそぐわない行為。これに対し、ルール違反だと指摘した。
677:イナ
19/07/30 11:48:36.94 O94O3VWc.net
前>>741
>>600の訂正(再掲載)。
×>>544→○>>554
678:１３２人目の素数さん
19/07/30 11:49:09.38 32/Qu64M.net
すでに上がっているやつについては、それは見分けのつかないコインを見分けてるからダメといい、自分の解答では記憶に残るからOKという。
なにそれwwww
679:イナ
19/07/30 12:06:48.73 O94O3VWc.net
前>>642
>>643
金貨をちゃんと天秤に載せ、釣りあったか釣りあわなんだかその結果で見分けてください。
金貨にAもBもないんです。たった1つだけ重さの違う金貨があるんです。
680:１３２人目の素数さん
19/07/30 12:17:19.96 eBMyS2dw.net
見分けがつかないのに記憶と実物をどうやって対応付けできるのだろう
681:１３２人目の素数さん
19/07/30 12:17:55.35 32/Qu64M.net
アホじゃね？
9枚コインがあったら適宜それにAとかBとか名前付けてるだけじゃん？
ホンットにわかんないの？
682:１３２人目の素数さん
19/07/30 13:54:50.82 udHn5lyl.net
天秤に乗せた途端に区別がつくようになるのか
斬新だな
683:１３２人目の素数さん
19/07/30 13:59:50.54 elHfUa7y.net
/＿/＿/＿/＿/＿/＿/＿/＿/＿/＿/＿/＿/＿/＿/＿/
はたしてミスがあるか
684:１３２人目の素数さん
19/07/30 14:01:04.63 elHfUa7y.net
『n枚の金貨がある(n≧2).
この金貨の中に1枚だけ重さの違うものが混ざっているが,
それは他のものと見分けがつかない.
天秤を4回使っても, 重さの違う金貨を特定出来ないという.
このときnの最小値を求めよ』
■重さの違う金貨を特定出来る最大値は40
天秤に1枚づつ以上載せて釣り合えばその金貨は
正式な金貨であることが確定する
最初に13枚づつ載せて釣り合えばこの26枚は正式が確定
残り14枚の中にニセ金貨がある
傾けばこの26枚の中にニセ金貨がある
ニセを含む14枚の内、9枚と正式な金貨9枚を比べる
釣り合えば残り5枚の内の3枚を情報が確定している
正式な金貨と比べる
釣り合えば残り2枚の内の1枚を情報が確定している
正式な金貨と比べればニセが確定
3枚が釣り合わなければ『重いか軽いかが確定している3枚』
となるので次の一回で確定する
ニセを含む9枚と正式な金貨9枚が釣り合わなければ、
『重いか軽いかが確定している9枚』となるので
次の二回で確定する
13枚づつ計26枚が傾けば、どちらかに
重いか軽いかの金貨がある
この場合、互いの13枚から4枚づつをエクスチェンジする
そこに情報確定済みの正式な金貨を片側に9枚加えて
13枚づつを計る
釣り合えば正式な金貨9枚の代わりに取り除いた
9枚の金貨が『重いか軽いかが確定している9枚』となるので
次の二回で確定する
傾きが逆になったときはエクスチェンジした金貨がニセ
この4+4枚の金貨でさらに1枚づつのエクスチェンジを行う
すると
『重いか軽いかが確定している3枚』と『重軽どちらかがある2枚』
となるので、次の一回で確定する
傾が変化しなければエクスチェンジしなかった9枚の金貨が
『重いか軽いかが確定している9枚』となる
これらの時、ニセ金貨が重いか軽いかも自動判定される
（ただし、『重軽どちらかがある2枚』は50％の確率でニセという
情報のみ判定）
金貨41枚だとさらに1回の調査が必要になる
以上により、
重さの違う金貨を特定出来ないnの最小値は41.
685:イナ
19/07/30 14:46:10.46 O94O3VWc.net
/＿/＿/＿/＿/＿/＿/＿
/＿人人__/＿/人人_/__
/_(＿)_)_/＿(＿)_)/__
/_( _＿)_/＿( _＿)/__
/_(^) )_/＿(`) )/__
/_(υ＿)_/__(_υ_)/__
◎ﾞυ┻◎ﾞ◎ﾞυ┻◎ﾞ_/__/_ｷｺｷｺ……＿/＿/ｷｺｷｺ……/＿/＿/＿/＿/＿/＿/＿/天秤に載せた瞬間に見分けがつくか？ なにを今さら。前>>644どっちかの天秤に載せた金貨が、重さの違う金貨だったときは、天秤に載せた瞬間に見分けがつくさ。手ぇ離したらすぐ。ｷｺｷｺ……
686:１３２人目の素数さん
19/07/30 15:47:54.20 elHfUa7y.net
[重9軽5]と[正10重4]なんて正式一枚でずらさなくても
[重9軽4]と[正9重4]の均等枚数のエクスチェンジで判定可能！
687:１３２人目の素数さん
19/07/30 15:56:25.94 Ofk/++MI.net
>>650
あんまりしつこいからあんたしてもらいたいことを明言しとくと、
・もし「全てのコインに名前をつけて区別することができない」という仮定で解いているなら、
それは他の人が扱っている問題の条件と全く違うものだから、然るべき仮定をつけ加えて
『（二次的な）出題者の立場として、新しい問題として提起する』こと。
それも、自分にとって未解決であればちゃんとそのことを明言した上で、な。
それができないようであれば、あんたが今繰り
688:返してる行為は 「問題文と関係ない自分が考えたことを延々と垂れ流してる」だけの単なる荒らしでしかないから、速やかにやめること。 「あんたらが勝手にコインを区別してんじゃん。こっちの方が問題文を正しく解釈してるんだからそれに従えよ」 ってのは無しだからな、先に言っておくと。どういう区別が許されると思ったのかをきちんと説明したり、 食い違いを共有してすり合わせしようともせずに、一人で自分設定の問題の思考過程を垂れ流してるのはあんたの方なんだからな。 ・もし新たに問題として投稿する時は、自分が無意識にどんな仮定をつけていたのかをよく考えること。 何度も訂正したり後出しじゃんけんみたいにならないように、その問題設定さえ見れば誰でも一通りに解釈できるようにすること。 特に今回の場合、コインの区別に関するあんたの認識が他の人のそれと違うことが明らかになってるんだから、その点で混乱が生まれないように。 ・もし誰かがその問題設定に興味を持って書き込んでくれればそのままある程度やりとりを続ければよし。 もし誰からも興味を示されなければ、その設定の問題はそれまで。せいぜい用意してた解答があればそれを発表したりする程度で終わり。 ・ついでに言うと、出題者の立場ってのはせいぜい基本的に問題を解いたり考えたりする他の人を、ヒントを出したり判定したりして見守ることを主とするものであって、 誰も興味を示してない、ましてや自己解決さえできていない自分設定の問題を、当の解決してない出題者が思考過程を何度も何度も垂れ流す、なんてのはやめること。 ・書き込みながら考えるとかいうことはやめて、自分のレスが多くなりすぎないように、ある程度自分なりに整理してから書き込むこと。 わからないかなあ
689:１３２人目の素数さん
19/07/30 17:43:09.81 LBMRjIX1.net
>>641
いや適当に4枚づつ乗せて左に乗せた方右に乗せた方乗せてない金貨って言っても同じだけど
別に乗せる前に名前つけなきゃ出来ないわけじゃない、どこに分類してるだけだから
乗せた後の金貨なら区別してもいいんでしょ？
それもわからない？
690:イナ
19/07/30 19:08:14.32 O94O3VWc.net
前>>650
>>652与えられた問題を解くのが面白いんで、改題する気はないです。
n≧2をn≧3にすべきという指摘はもっともな改題だと思いました。
題意を素直に受けとめ、n=9のとき特定できないことだけでなく、n=3～8のとき特定できることをすべて示すべきで、ここをもっと簡便に説明できるかもしれないけど、有限個の場合分けで数が知れてるんで各々書いたほうが速いしよくわかると思いました。
>>653載せたあとの金貨を区別してもいいかどうか、一解答者である俺にはわからない。出題者に訊いてほしい。
ただ天秤に載せたあとの金貨はただ1つをのぞいてほぼすべてが同じ重さなんで、金貨を左右どっちの皿に載せたかで差をつけるのは理論的にはわかりましたが、ズルいと感じました。
本来ただ1つの重さの違う金貨がみつかったら、あとの金貨は見分けなくていいはず。計量して一目で決着する方法がいいと思います。
691:１３２人目の素数さん
19/07/30 21:29:55.93 Ofk/++MI.net
> >>652与えられた問題を解くのが面白いんで、改題する気はないです。
この発言は
> >>653載せたあとの金貨を区別してもいいかどうか、一解答者である俺にはわからない。出題者に訊いてほしい。
> ただ天秤に載せたあとの金貨はただ1つをのぞいてほぼすべてが同じ重さなんで、金貨を左右どっちの皿に載せたかで差をつけるのは理論的にはわかりましたが、ズルいと感じました。
> 本来ただ1つの重さの違う金貨がみつかったら、あとの金貨は見分けなくていいはず。計量して一目で決着する方法がいいと思います。
これらと合わせれば、あんたは
「俺は与えられた問題を"自分の価値観や解釈で判断したもの"を解くのが面白いし、他の多くの人の解釈と合わせたり自分の解釈を他人がわかるよう明示したりする努力もしません」
って言ってることになるけど、つまり
「俺は問題文とは関係ない自分が考えたことを延々と垂れ流してるだけの荒らしです」
と認めてるってことでおけね？早いとこ満足してどっか行ってちょうだい
692:な
693:１３２人目の素数さん
19/07/30 21:36:13.35 7JgKt8gk.net
天秤くんは、専用スレを立てて、そこで好きなだけやれよ。
いつまで下らんおこちゃまのパズルをやってんだ？ｶｰｯ(ﾟДﾟ≡ﾟдﾟ)､ﾍﾟｯ
694:１３２人目の素数さん
19/08/01 18:07:59.38 lAN2N9kX.net
>>624
14枚から1枚を取り除き、13枚のコインの中から、
重い偽物を特定するか、軽い偽物を特定するか
すべてが本物と確認すればよい
そうすれば、26通りに、すべて本物という一通りを加え、
27通りに落ち着き、情報理論的上限27に納めることができる
最初に取り除かれたコインは、一度も天秤に載せら得ることなく、
「おまえは偽物」と烙印を押される．．．かもしれない
※3回目の調査で残り2枚あるときは
判定不能になる確率が50%ある
695:１３２人目の素数さん
19/08/01 21:13:30.95 XHT/wRDk.net
>>657
>>判定不能になる確率が50%ある
これは、
40枚の真贋判定は100%完遂でき、かつ、ほとんどの場合、偽物と判断した物が、重い偽物か軽い偽物かも、
判定できるが、「残り二枚の軽重不明のコインの中から一枚の偽コインの見極める」というルートを通過
する場合に限り、（真贋判定はきちんとできるが、）偽物と判断した物が、重い偽物か軽い偽物かの判断はできない。
という主旨のコメントでよろしいですね。
>>657の書き込みでは、内容を熟知している者なら、「偽物の軽重判定」に対しての「判定不能」
という意味だろうと、好意的に読み取ることができますが、一般的な読者なら、「真贋判定」に対しての
コメントと読みかねないと思うので、一言、書かせてもらいました
696:１３２人目の素数さん
19/08/01 21:34:37.90 XHT/wRDk.net
修正します。
前：する場合に限り、（真贋判定はきちんとできるが、）偽物と判断した物が、重い偽物か軽い偽物かの判断はできない。
後：する場合に限り、（真贋判定はきちんとできるが、）偽物と判断した物が、重い偽物か軽い偽物かの判断はできない事が確率が50%で起こる。
697:１３２人目の素数さん
19/08/01 21:39:02.85 lAN2N9kX.net
>>658
全く違います(´･ω･`)
「不14正26」から>>657の方法で調査すると
40枚の真贋判定は100%完遂できない場合があり、
残り2枚の判定を1回で行わなければならないときに
判定不能になる確率が50%あるのです
698:１３２人目の素数さん
19/08/01 22:20:44.02 XHT/wRDk.net
ということは、
「二枚の軽重不明のコインから、一回の天秤使用で軽重不明の偽コインを見極める事はできない。」
という主張ですね。もし、いきなり、二枚のコインと天秤を渡されたなら、そうかもしれません。
しかし、ここでは、40枚のコインの中から、偽物の候補が二枚に絞られたという文脈の中にあります。
本物と確定しているコインは38枚有ります。
本物と確定しているコイン一枚を天秤の片方に載せ、軽重不明のコインの内の一枚をもう片方に載せます。
傾けば、天秤に載せた軽重不明だったコインが偽物です。傾き方で、重い偽物か、軽い偽物かも判断できます。
釣り合えば、天秤に載せかなったコインが偽物です。しかし、これが、重い偽物か、軽い偽物かは判断できません。
この方法でも、できないと言い切るのですか！！！
真贋判定は１００％で可能。しかも、ほとんどの場合は、重いのか軽いのかも判断可能。
ただ、「軽重不明二枚」というルートをたどった場合は、真贋判定はきちんとできても、50%の確率で、
軽重判定はできない。という結論に、同意されますね。
699:１３２人目の素数さん
19/08/01 22:39:36.15 lAN2N9kX.net
>>661
『14枚から1枚を取り除き、13枚のコインの中から、
重い偽物を特定するか、軽い偽物を特定するか
すべてが本物と確認すればよい』
この調査に正式な26枚の金貨を使用しないと
判定不能になることがある
700:１３２人目の素数さん
19/08/01 22:58:35.62 XHT/wRDk.net
「40枚の中から、軽重不明の偽コイン１枚を４回の天秤使用で特定する問題」
と
「14枚の中から、軽重不明の偽コイン１枚を３回の天秤使用で特定する問題」
は異なります。前者は可能で、後者は不可能です。
「前者は可能か」という議論において、「後者は不可能だ」と答えても意味がありません。
あなたが行っていることは、将にこれです。
前者の中で、後者に似た状況が生じます。なのになぜ「可能」となるのか？
それに説明を与えたのが、>>624の内容です。
前者の中で生じる後者と似た状況が、後者と異なるのは、正しいコインの有無です。
前者の中で生じる後者に似た状況には、正しいコインがあるが、後者には無い。
この違いが、可能なのか不可能なのかに決定的な影響を与えます。
701:１３２人目の素数さん
19/08/01 23:15:51.55 XHT/wRDk.net
ｎ 枚のコインがあり、その中に一枚だけ軽重不明の偽コインが含まれている。
天秤 k 回の使用で偽コインを見極められる ｎ の最大値を求めよ。
ただし、別枠で、１枚の本物のコインが無い場合と、ある場合、それぞれについて答えよ。
という問題があった場合、無い場合は、(3^k-1)/2、ある場合は、(3^k+1)/2 が答えとなります。
情報理論的には、天秤 k 回の使用というのは、3^k 通りからの候補の見極めを可能とします。
これ�
702:ｪどう考えても、上限です。 別枠で、コインが用意されていない場合の答え、(3^k-1)/2 は、重いのか、軽いのかの見極め を行っている分の二倍を施すと、3^k-1 で上限3^kを下回っているので、問題ないが、 別枠で、コインが用意されている場合の答え、(3^k+1)/2 を二倍すると、3^k+1 で、3^k を 上回ってしまう。「そのようなことはあり得ないのでは」という疑問に対する解説が、 >>624 の後半などに記した内容です。 詰まるところ、軽重不明なコインｎ個 の自由度(?)は、2n ではなく、2n-1 だというものです。 もし問題が、「偽コインを特定し、軽重も判断せよ」なら、2n ですが、「偽コインを特定せよ」だけ なので、一つのコインは除き、そのかわり、チェックしたすべてのコインが正しいという場合を加えて、 (n-1)×2+1=2n-1にできるという話です。
703:１３２人目の素数さん
19/08/01 23:35:18.33 vBnXeieY.net
天秤スレ立てて、そこでやれよ
704:１３２人目の素数さん
19/08/02 01:17:17.93 bNF3wPAo.net
皆で解いてる感がほしいんでしょ
それで何か意味のあることを書けたらそれだけで"皆の"イチバンになれるからね
連投クソコテと同んなじ
705:１３２人目の素数さん
19/08/02 01:42:15.86 5/Whjr91.net
天秤荒らし君には困ったものだね
706:１３２人目の素数さん
19/08/02 02:03:49.42 79abfNhp.net
イナさんはNGしてるので本人のレスは見えないけど、
>>639は笑った
707:ヒドラ(コロン諸島)
19/08/02 23:41:56.73 /ORP8+ab.net
(問題)>>514
n≧2→n≧3に変更。
(答案)
n=3、4のとき、>>601より、三回目までに特定できる。
n=5、n=6、n=7、n=8のとき、>>600より、三回目までに特定できる。
n=9のとき、>>554より、天秤に4枚ずつ載せると特定できない。
>>549より、天秤に3枚ずつ載せても2枚ずつ載せても特定できない。
天秤に1枚ずつ載せても三回目までに特定できるのは6枚まで。あと残り3枚のうちのどれが重さの違う金貨か特定できないことがある。
以上3≦n≦9のすべてのnにおいて計量して、3≦n≦8では重さの違う金貨は特定できるが、n=9のときは、どうしても特定できない。
∴どうしても特定できないnの最小値は9である。
708:１３２人目の素数さん
19/08/03 20:30:12.88 UydpcLwR.net
関係ないけどプログラムで解いたやつを載せてる人もいるけどあまり面白くないね
709:１３２人目の素数さん
19/08/03 20:44:33.78 Xy1NvtMG.net
そんな人いた？手計算でできるようなものばかりだったと思うけど
そもそも有名問題なんだし
710:１３２人目の素数さん
19/08/03 21:45:48.54 UydpcLwR.net
例えば>>123みたいなやつとかね
711:１３２人目の素数さん
19/08/03 21:55:57.05 Xy1NvtMG.net
メモ代わりに使うのはなぁ
712:１３２人目の素数さん
19/08/03 22:45:17.76 8WR2VuYV.net
オレも与えられたmに対して具体的に錘をどう乗せれば
[log[3](2m)]+1回でニセモノ見つけられるかプログラム組んだ事あるな。
まぁまぁ楽しかったな。
713:１３２人目の素数さん
19/08/04 05:13:52.51 N7DDIMxB.net
俺は面白いからプログラムもいいよ
714:１３２人目の素数さん
19/08/04 08:11:50.33 5+IcxVye.net
自分では未解決ですが思いついてしまったので
(1)ユークリッド平面 R^2 の部分集合 A であって次の性質を満たすものは存在するか：
閉区間 [0,1] から R^2 への連続な写像 f が定値でないならば、x∈[0,1] であって f(x)∈A を満たすものも満たさないものもとれる.
(2)特に集合 A を
A = { (a,b)∈R^2 | aもbも有理数であるか、又は{1,a,b}が有理数体上一次独立}
と定めた場合、この A は(1)の性質を満たすか.
715:１３２人目の素数さん
19/08/04 16:40:10.02 NS5c9gmB.net
>>676
高校数学の美しい物語おすすめ
716:１３２人目の素数さん
19/08/04 16:54:56.08 mMtM
717:Y2PI.net
718:１３２人目の素数さん
19/08/06 12:34:38.35 i6yPV6vh.net
全ていいえ
719:１３２人目の素数さん
19/08/06 12:45:55.51 i6yPV6vh.net
重軽どちらかがある2枚も
100％判定可能でした
720:１３２人目の素数さん
19/08/06 15:11:31.90 Hkh8yfLh.net
な
721:
19/08/10 00:33:09.08 iX1EMrAx.net
前>>669話変わるんだけど、運転免許の修了検定だか卒業検定だかあるじゃん、あれ最後たしか二択で、どっちだ!? ってなって時間とられて大量失点して不合格不合格不合格不合格……何回も落ちて、時間と電車賃がかかってしょうがなかったな。
これ、引っかけじゃないか？ 考えだしたらどつぼ。あれはつらかった。センター試験みたいなのだったらまず完全にわかるから問題ない。国語とか英語とかでたまに自信ないのがあるときあったけど、四択や五択になってるおかげで救われることがあったような。
つまり正しさってやつは比較するものがあっての、相対的なものなんだよ。
722:１３２人目の素数さん
19/08/10 01:47:52.97 v2NzGOZT.net
運転免許のペーパーテストで、落ちるなんてまずありえない。
723:イナ
19/08/10 09:37:27.35 iX1EMrAx.net
>>683そう思うだろ。人生にはいろんな時季がある。数学の難問が見た瞬間イケイケどんどん解きほぐされてハートがきゅんきゅんすることもあれば、ありえないぐらいに二択が怖くてとり乱されることもあるんだよ。前>>682
￣]/＼_____________○｡
__/＼/ /|ﾟ｡
￣＼/ / |゜
￣|＼__________／| |__
］| ∥￣￣￣￣∥ | / /
__| ∥ □ □ ∥ |/ /｡
___`∥________∥／_/゜
￣￣￣￣￣￣￣￣￣∥°
］ □ □ ∥ /
_____∩∩_________∥/｡
￣⊂(-.-))⌒ つ~￣￣。
. ｀υ __
724:１３２人目の素数さん
19/08/11 13:19:33.18 A0eNdt+k.net
問題
1を2とし、2を3とせよ。このとき1+2はいくつか？
725:１３２人目の素数さん
19/08/11 17:23:23.42 09Xi+6JE.net
>>685
3
726:１３２人目の素数さん
19/08/12 14:10:30.36 hTgzpWU8.net
∫(x^n)(e^x)dx
727:１３２人目の素数さん
19/08/12 14:13:58.43 hTgzpWU8.net
>>687
n>0
728:１３２人目の素数さん
19/08/12 14:21:56.54 nJw90Iim.net
∫e^x = 0!(1)e^x+C
∫xe^x = -1!(1-x/1!)e^x+C
∫x^2 e^x = 2!(1-x/1!+x^2/2!)e^x+C
……
729:イナ
19/08/12 14:53:42.75 R6APndVz.net
前>>684
>>685
1+2は題意より、2+3
2+3は題意より、3+3
∴与式=3+3=6
730:１３２人目の素数さん
19/08/12 19:16:02.39 Si48iRkU.net
>>687
-Γ(n+1,-x) * (-x)^{-n-1} * x^{n+1}
Γは第2種不完全ガンマ関数．
731:１３２人目の素数さん
19/08/13 02:50:53.93 HqlhG0Td.net
>>579 にて5つの重りを天秤を使ってソートする問題を紹介しました。
出題形式は異なってしまいますが、簡単に言うと、
「7回以内の天秤使用で、5つの重りを重い順に並べる手順を考えよ」という問題です。
一件の誤答がありましたが、その他の回答はありませんでした。
初見の方に楽しんでもらいたく、知っている方の投稿を遠慮していただいたからだと思います。
しかし、もう十分時間がたったので、このお願いを取り下げます。
732:１３２人目の素数さん
19/08/13 04:35:16.64 Ef6DrBrl.net
>>692
AとE、BとCを比べる。
A≦E、B≦Cとしてよい。
AとBを比べる。A≦Bとしてよい。
733:ここまで３回でA≦B≦Cが確定。 次にBとD、その結果に応じてDとAまたはCを比較して２回でA、B、C、Dの順位が確定する。 この４つの順位をP≦X≦Y≦Zとする。 Pが最小は確定。 同じ要領で２回でE、X、Y、Zの順位を確定できる。 これを順にならべてQ≦R≦S≦TとしてPが最小は確定していたから最終順位は P≦Q≦R≦S≦T。
734:ヒドラ(コロン諸島)
19/08/13 10:18:15.03 LC7aWG7e.net
前>>690
>>692一件の誤答とはいえ、だれも張られませんなら、儂の一人勝ちではござらぬか。
735:１３２人目の素数さん
19/08/13 19:47:05.51 HqlhG0Td.net
>>693 さんの方法と内容は同一ですが、用意しておいた「図解的方法」と、別視点からのコメントをアップします。
○、○、○、○、○：五つの重りが対等に存在している状態
○←○、○←○、○：上の状態から、1番目と2番目、3番目と4番目を比較して、重かった方に矢印が向くよう表記。[天秤二回使用]
○←○←○、○ ：上の状態から、矢印が向いている重り二つを比較し、並べ替えた状態。[一回使用]
↑
○
○←○←○←○ ：上の三連部分に、孤立している一つを挿入。最初に三連の真ん中と、次に三連内のどちらかと比較し、四連が完成
↑ (↑) 結果により、下部の重りが、第一の重りにつながる場合と、第二の重りにつながる場合がある。[二回使用]
○ (○)
○←○←○←○←○：上の四連の後方三連に、下部の重りを挿入し五連が完成。[(多くても)二回使用]
このような経路を辿れば、七回以内でソートが可能です。以下、別視点での解説になります。
情報理論的見地から考えると、5! = 120 < 128 = 2^7 から、7回で可能だろうと、予想でき、実際上のように可能です。
4つの重りで、最も重いものを、トーナメント形式で特定することにします。（3回天秤を使用します。）
トップになったものをA、Aに一回戦で負けたものをB、Aに決勝で負けたものをC、Cに一回戦で負けたものをDとし、
参加していない重りをEとします。この段階で、A,B,C,Dの間での順番は、ABCD,ACBD,ACDBの三通りが考えられ、
Eは、各パターンのいずれかの位置に入るため、A～Eまでの順番で考えると、15通りが残されています。
736:１３２人目の素数さん
19/08/13 19:47:49.71 HqlhG0Td.net
次は4回目の天秤使用になりますが、ここで、EとAを比べたとします。E>Aなら3通り、E<Aなら12通りに分岐しますが、
これでは、残り三回では並べ替えられません。同様にEとDの比較も、3通りと12通りに分岐し、不可能なのがわかります。
それでは、EとBでは？ E>Bとなると、ABCDでは2通り、ACBDでは3通り、ACDBでは4通りなので、合計9通り。
やはり、この比較も失敗であることがわかります。
で、EとCのみが残されます。 E>Cとなると、ABCDでは3通り、ACBDでは2通り、ACDBでは2通りなので、合計7通り。E<Cなら8通りと、
この比較なら、残り三回で可能なことがわかります。その他、Eを使わない方法も、5通りと10通りに分岐する等、不可能な事がわかります。
つまり、4回目の比較は、（ここでのネーミングでは）EとCにユニークに絞られています。このように、比較後の分岐状況を
検討しつつ、比較ルートを見いだしていけば、ゴールにたどり着けます。この後続の比較方法は省略しますが、いくつか補足しておきす。
三回目の比較は、対称性からもわかるように、「トップ」ではなく、「最軽量」を決める比較でも可能です。
が、これら以外の方法、例えば、心情的にEを登場させたくなるかもしれませんが、このような方法は全て失敗することが、
分岐数のカウントからわかります。
「ソート済みの2^k-1個の重り」に、一つの重りを加え、天秤をk回使用して、「ソート済み2^k個の重り」にするのは、
情報理論的に無駄がなく、いわば定石です。k=2の場合を上の図解で紹介した方法では多用しています。
この定石に従えば、４回目に続いて五回目もEが登場するのが自然です。しかし、もし、四回目の比較でE>Cならば、
EABCD、AEBCD、ABECD、EACBD、AECBD、EACDB、AECDB という7通りに絞られていますが、
AとEの比較という定石の他、BとCの比較という方法も存在していることを補足しておきます。
737:１３２人目の素数さん
19/08/14 15:47:39.82 nsHYbjzT.net
これ錘の数がｎ枚のときの使用回数は[log[2] n!]+1回になる？
738:１３２人目の素数さん
19/08/15 00:14:49.63 j/ErZKDp.net
n=2は例外として扱うとして、『数学１００の問題』によると、
11以下では正しく、13では当てはまらない。14(13の誤植？)での値は、33か34か不明とある。
古い本なので、どこかに更新データは有ると思われる。
739:１３２人目の素数さん
19/08/15 00:54:52.85 j/ErZKDp.net
あるアルゴリズムによる必要回数の表を、Knuthの本に見つけた。
n=1～11,20,21 で、理論的下限={log[2](n!)} に一致する。 ；{x}は切り上げ関数
n=12～19,22～24 で 理論的下限 +1
25,26,27 で 理論的下限 +2
28～33 で 理論的下限 +3
740:１３２人目の素数さん
19/08/15 01:18:26.57 Jce3LOm5.net
>>698
へー、面白そう！
>>699
kunthの何て本ですか？
741:１３２人目の素数さん
19/08/15 01:39:31.73 j/ErZKDp.net
『The Art of Computer Programming』Vol.3 Sorting and Searching
です
742:１３２人目の素数さん
19/08/15 05:34:49.07 Jce3LOm5.net
>>701
thx
743:１３２人目の素数さん
19/08/15 17:19:35.35 RxBWT0Y0.net
>>687
部分積分により
∫(x^n)(e^x) dx = (x^n)(e^x) - n∫(x^{n-1})(e^x) dx
= (x^n)(e^x) - n(x^{n-1})(e^x) + n(n-1)∫(x^{n-2})(e^x) dx
= (x^n)(e^x) - n(x^{n-1})(e^x) + n(n-1)(x^{n-2})(e^x) - n(n-1)(n-2)∫(x^{n-3})(e^x) dx
= ････
= (e^x)Σ[r=0,n] (-1)^r (n!/(n-r)!)(x^{n-r}).
・参考書
森口・宇田川・一松 「数学公式I」 岩波全書221 (1956) p.153
第IV篇 第1章 §33 (i)
744:１３２人目の素数さん
19/08/18 23:41:25.54 S73cozEw.net
URLﾘﾝｸ(i.imgur.com)
745:１３２人目の素数さん
19/08/19 05:11:25.84 V6wAPODJ.net
1022^(1023^1024) + 1024^(1023^1022) は 1023 で何回割り切れるか
一般化して
(n-1)^{n^(n+1)} + (n+1)^{n(n-1)} は n で何回割り切れるか
2項公式より
(n-1)^{n^(n+1)} = -1 + n^(n+2) - (1/2)n^(n+3){n^(n+1)-1} + ････
(n+1)^{n^(n-1)} = 1 + n^n + (1/2)n^(n+1)}{n^(n-1)-1} + ････
より n回。
∴1023回
746:１３２人目の素数さん
19/08/19 05:20:03.41 18fvL3UC.net
(;ﾟ∀ﾟ)=3ﾊｧﾊｧ
747:１３２人目の素数さん
19/08/19 08:18:51.64 Q3ufC9fD.net
>>705
ど、どういうこと？
748:１３２人目の素数さん
19/08/19 08:28:24.02 DVQsi2eo.net
>>705
>一般化して
ただし、nが偶数なら0回ｗ
749:１３２人目の素数さん
19/08/20 04:55:13.92 tL4LcjDy.net
>>708
ただし、n=2 なら 1回ｗ
1^(2^3) + 3^(2^1) = 1^8 + 3^2 = 1 + 9 = 10,
750:１３２人目の素数さん
19/08/20 11:47:22.96 DuGsCWLF.net
そっか。
nの�
751:阯]が 1+(-1)^nなんだけど、 1+1=2=n のケースを見逃してたわ。
752:１３２人目の素数さん
19/08/20 12:36:08.22 PYeexkQP.net
そもそもn^(n+1)で割り切れないのは明らかなん？
753:１３２人目の素数さん
19/08/20 13:54:26.52 DuGsCWLF.net
>>711
すくなくとも、>>705の最初の２項だけをみると (1+n^2)n^n
なので、n^(n+1)では割り切れない。
あとは、３項目以降がn^(n+1)の倍数になってるかどうか
なんだが、確かに形式上はn^(n+1) が因数として入ってる
けど、分母にk!があるからねぇ。要するに n^(n-1)Ck×n^k
とn^(n+1)Ck×n^k がk>=2 で n^(n+1)で割り切れるかどうか。
kがn^(n-1)ともn^(n+1)とも素の場合には明らかなんだが…。
そうでない場合、kとそれぞれとの公約数をL1,L2として、
n^(n+k-1)/L1 とn^(n+k+1)/L2 がn^(n+1)で割り切れること
が示せればいいんだけどね。
そういう意味ではn^nで割り切れるかどうかについても同じ
ことが言えるけど、上が示せれば自動的にOK。
754:１３２人目の素数さん
19/08/20 15:49:14.68 PYeexkQP.net
やっぱり>>705の式変形だけでは1023回と結論づけられないよね。
もうひと議論必要。
755:１３２人目の素数さん
19/08/20 17:50:31.16 DuGsCWLF.net
>n^(n+k-1)/L1 とn^(n+k+1)/L2 がn^(n+1)で割り切れるか
nが奇数なんだから、k=2のときには明らかだね。
n^(k-2)/L1 (2<L1≦k)も n^k/L2 ( 2< L2 ≦k)もL1,L2を
素因数分解してチェックすれば割り切れそうな気がする。
L1の素因数の一つをa^sとすると、aはnの素因数でもある
ことからn^(k-2)はa^(k-2)を因数としてもつ（ただし、n
が奇数なのでaは2より大きい素数）
a^s≦L1≦k より a^(k-2)≧a^(a^s -2)
a^(k-2)/a^s ≧ a^{(a^s)-s -2) a≧3,s≧1より、
a^s -s -2 ≧0 したがって、a^(k-2)/a^s ≧1 は割り
切れる。こんな感じで行けそうかな？
しかし、もっと簡単に示せないものか。
756:１３２人目の素数さん
19/08/20 17:53:39.38 DuGsCWLF.net
× L1の素因数の一つをa^sとすると
○ L1の素因数の一つをaとし、a^sを因数とすると
757:１３２人目の素数さん
19/08/20 18:39:15.59 tL4LcjDy.net
nが平方因子を含まない奇数のときは n回
(略証)
C(N,k) = (N/k)Π[i=1,k-1] (N-i)/i
aをnの素因数とする。(奇素数)
1≦i≦N-1 のとき (N-i)/i の分母・分子に現れるaの回数は等しい。
また、kの中に現れるaの回数は < k/(a-1) ≦ k, ゆえ k-1 以下。
N=n^(n-1) のとき
C(N,k) は a^(n-k) の倍数、したがって n^(n-k) の倍数
N=n^(n+1) のとき
C(N,k) は a^(n+2-k) の倍数、したがって n^(n+2-k) の倍数。
758:１３２人目の素数さん
19/08/20 18:47:33.50 tL4LcjDy.net
n = 1023
= 32^2 - 1
= (32+1)(32-1)
= 33・31
= 3・11・31
759:１３２人目の素数さん
19/08/21 00:22:43.84 YfssQOZx.net
>>716 補足
kの素因数分解における素数aの回数
= [k/a] + [k/a^2] + [k/a^3] + ････ + [k/a^k]
≦ k/a + k/a^2 + k/a^3 + ････ + k/a^k
< k/(a-1),
760:１３２人目の素数さん
19/08/21 02:52:32.86 Y7aYDYYG.net
>>716
nが平方因子を含んでると駄目なの？
761:１３２人目の素数さん
19/08/21 03:16:43.84 Y7aYDYYG.net
>>714のやり方だと平方因子だろうが立方因子だろうが
含んでいても、nが奇数ならn回になりそうだけど？
762:１３２人目の素数さん
19/08/21 04:29:00.38 YfssQOZx.net
a^s | n とする。(s≧1)
C(N,k) = (N/k)Π[i=1,k-1] (N-i)/i
のうち素因数aが残るのは (N/k) のところ。
N=n^(n-1) には a が (n-1)s 回現れるが、k には (k-1)以下。
∴ (N/k) には (n-1)s - (k+1) 回以上
∴ (N/k) n^k には (n-1+k)s - (k-1) = ns + (k-1)(s-1) ≧ ns 回以上
なので OK ですよね。
763:１３２人目の素数さん
19/08/21 11:06:10.82 /bpWRxkM.net
>>705の一般化について、とりあえず、計算機を回してみたところ、
3から1023までの奇数nについて、
(n-1)^{n^(n+1)} + (n+1)^{n(n-1)} ≡ n^n (mod
764: n^(n+1)) であることは示せた
765:１３２人目の素数さん
19/08/21 11:08:05.84 2uEJxB3J.net
URLﾘﾝｸ(imgur.com)
766:１３２人目の素数さん
19/08/21 12:08:12.87 Y7aYDYYG.net
>>721
ですよね。
>>714をもう少し整理して書き直しておきます。
一般に、
C(N,k)=(N/k)*C(N-1,k-1) なので、kとNの最大公約数をL
として、k=qLとおくと、qとN/Lは素なので、qはC(N-1,k-1)
の約数でなければならない。 したがって、C(N,k)はN/Lの
倍数である。これを前提として、>>705の二項展開の各々の
k番目(k≧2)の項の絶対値 M=(n^k)*C(N,k) を評価すると、
Mは(n^k)N/L の倍数になるはず。LをL= (a^s)*(b^t)… と
素因数分解したとき、Nがnの累乗であれば、それらの素因数
a,b…はすべてNの素因数であり、nの素因数でもある。
ここで、nが奇数であれば、n^(k-2)がLで割り切れることを示す。
aがnの素因数より、n^(k-2)はa^(k-2)を因数として持つが、
k≧L≧a^sよりa^(k-2)/a^s≧a^(a^s-s-2)。 a≧3, s≧1より、
a^s-s-2≧0 となるので、a^(k-2)/a^s≧1 、つまりn^(k-2)
はa^sを約数として持つ。他のLの素因数についても同様に言
えるので、n^(k-2)はLを約数として持つ。
したがって M が(n^k)N/L = N*(n^2)*n^(k-2)/L の倍数で
あることから、MはN*(n^2)の倍数であると言える。
以上より、
N=n^(n-1)の場合、M は n^(n+1)の倍数
N=n^(n+1)の場合、M は n^(n+3)の倍数
よって、>>705の二項展開の２番目以降の項はすべてn^(n+1)
の倍数である。
767:１３２人目の素数さん
19/08/21 12:13:56.83 Y7aYDYYG.net
>>722
ご苦労さまです。wolframalphaにやらせてみようとしたんですが、
無料版だとn=7までが限界でしたｗ
768:１３２人目の素数さん
19/08/21 14:43:48.42 Y7aYDYYG.net
>>724
すみません、自己レスで修正しときます。
>>>705の二項展開の各々のk番目(k≧2)の項の絶対値
k=0から始まるので、k番目ではなく、(k+1)番目ですね。
したがって、最後から二行目、
>よって、>>705の二項展開の２番目以降の項はすべてn^(n+1)
のところは、「二項展開の３番目以降の項」になります。
769:１３２人目の素数さん
19/08/22 09:10:53.58 5qVSVnaY.net
a≧3
>>718 の評価を改良して
k≧2 では k-2回以下
N=n^(n-1), k≧2 のとき
C(N,k) は n^(n+1-k) の倍数。 M は n^(n+1) の倍数。
N=n^(n+1), k≧1 のとき
C(N,k) は n^(n+2-k) の倍数。 M は n^(n+2) の倍数。 >>716
770:１３２人目の素数さん
19/08/22 15:15:07.25 of3vaPk+.net
付置を使った照明。
補題
p を素数、vをp進付置とする。
a,bをp進単数でa ≡b (mod p)であるとする。
このとき
v(a^n - b^n) = v(a-b) + v(n)
771:１３２人目の素数さん
19/08/22 15:15:56.11 of3vaPk+.net
定理
nを奇数とする。
x = (n+1)^{n^(n-1)} + (n-1)^{n^(n+1)}とおく。
このとき
v(x) = nv(n)
が成立する。
特に
max{e | x ≡ 0 (mod n^e)} = n
である。
(∵)
pをnの素因子とし、ｖをp進付置とする。
補題により
v((n+1)^{n^(n-1)} - 1) = v(n+1 -1) +(n-1)v(n) = nv(n)
v((n-1)^{n^(n+1)} - (-1)) = v(n-1 +1) +(n+1)v(n) = (n+2)v(n)
であるから主張は成立する。
772:１３２人目の素数さん
19/08/22 16:17:13.66 hw83GYlR.net
Rを実数体として、g:[0,1]→Rを可測関数とするとき、
∫_0^1 f(x)g(x)dx=0
となる恒等的には0ではない連続関数f:[0,1]→Rが存在することを示せ
773:１３２人目の素数さん
19/08/22 16:56:45.39 r9/sw2kv.net
>>730
f(t,x)= sin(π(x-t))
I(t)=∫f(t,x)g(x)dx
とおく。
I(t)は収束定理により連続。
I(0) = -I(1)
774:１３２人目の素数さん
19/08/22 19:23:17.13 8233tz9b.net
>>731
gは可測関数とは言ってますが可積分関数とは言ってないので収束定理が使えないと思いますが
775:１３２人目の素数さん
19/08/23 10:34:30.02 w7ee27lc.net
>>730
それ本当に成り立つの？
Rの部分集合Aに対して関数1_Aを
(1_A)(x)=1 (x∈Aの時), (1_A)(x)=0 (それ以外の時)
と定めて、0以上1以下の全ての有理数が１回ずつ出現する数列を {q_n}_(n=1,2,…) とおく。
集合A_mを
A_m = ∪_(n=1,2,…) ( q_n - 1/(logm･2^n) , q_n + 1/(logm･2^n) )
とおいて、関数g~:R→[0,∞]を
g~(x) = Σ_(m=2,∞) (1_(A_m))(x)
と、そして関数g:R→[0,∞)を
g(x)=0 (g~(x)=∞の時), g(x)=g~(x) (それ以外)
と定める。
この時、0と1の間のどの有理数qをとっても、任意のε>0について
∫_(q-ε,q+ε) g(x)
=∫_(q-ε,q+ε) g~(x) (g~による∞の逆像はルベーグ零集合になるから)
≧∫_(q-ε,q+ε) Σ_(m=2,∞) (1_(q - c/logm , q + c/logm))(x) (cはある正の数)
=Σ_(m=2,∞) 2min(ε,c/logm)
=∞
となるから、fが恒等的に0でない連続関数であれば、
ある0と1の間の有理数の近傍で、fの絶対値がある正の数より常に大きいことになるから
∫_(0,1) |g(x)f(x)|dx = ∞
となってしまう
776:１３２人目の素数さん
19/08/23 13:23:50.88 75WRKQde.net
I0 = ∫_0^1 g(x) dx
I1 = ∫_0^1 x g(x) dx
とおく。
I0=0 のとき f(x) = 1,
I0≠0 のとき f(x) = x - I1/I0,
777:１３２人目の素数さん
19/08/23 14:25:33.66 DGGgm78l.net
近似単関数列から適当に小数展開の数字いじって作れんかなあ
778:イナ
19/08/30 01:49:00.30 Vf6wl0ub.net
前>>694
[問題]たばこの箱を最大の対角線を軸に一回転させた通過部分の体積を求めよ。
但し、箱はレギュラーサイズのボックスタイプ(88㎜×55㎜×23㎜)とせよ。
779:１３２人目の素数さん
19/09/02 23:30:01.93 0UZpS5tl.net
任意の偶数aについて、ある適切な二つの素数を取ればその差はaになることを証明せよ。
解けますか？（´-`）
780:１３２人目の素数さん
19/09/02 23:43:18.82 nu7cxdi6.net
>>737
ムズイ！
自作？
答えはあるの？
781:１３２人目の素数さん
19/09/03 00:00:09.08 N4vbmFyn.net
>>737
下らん
782:１３２人目の素数さん
19/09/03 00:08:42.32 0G/HzIel.net
思いつきの問題だろうが、
100万くらいまでの全ての偶数についてそのような素数の組があることが判明したなら
世紀の難問になる可能性はある。
783:１３２人目の素数さん
19/09/03 00:22:57.35 5h8T3vQd.net
なんか任意の長さの等差数列をなす素数の組があるとかタオが証明してなかったっけ。
なんかそれも既に示されてそう
784:１３２人目の素数さん
19/09/03 01:01:31.41 QgfJeJ2b.net
差を和に変えたらゴールドバッハじゃん
本当に解けるのか？
785:１３２人目の素数さん
19/09/03 10:14:44.97 5Iy0AKSj.net
連続する 2a-1 個の自然数
(2a)! +2, (2a)! +3, ････, (2a)! +(2a-1), (2a)! +(2a) はすべて合成数である。
(2a)! +1 と (2a)! +(2a)+1 が共に素数となるようなａが存在するか？
(2a)! -(2a), (2a)! -(2a-1), ････, (2a)! -3, (2a)! -2 でもよい。
「高校数学の美しい物語」(いくらでも長い素数砂漠が存在する)
URLﾘﾝｸ(mathtrain.jp)
786:１３２人目の素数さん
19/09/03 10:21:56.70 5Iy0AKSj.net
(修正)
a! +2, a! +3, ････, a! +(a-1), a! +a の a-1 個はすべて合成数である。
a! +1 と a! +a+1 が共に奇素数となるような偶数aが存在するか？
a! -a, a! -(a-1), ････, a! -3, a! -2 でも同様。
787:１３２人目の素数さん
19/09/03 10:48:53.35 ACtA2QeY.net
なんかキタ
788:１３２人目の素数さん
19/09/03 10:55:14.69 5Iy0AKSj.net
a ≦ 966 までは存在するらしい。
URLﾘﾝｸ(www.asahi-net.or.jp)
600を超えるのは確か。
しかし p≦4000億 まで探索しても ⊿p ≦ 4000 らしい。
URLﾘﾝｸ(math.a.la9.jp)
解けた方は�
789:ｫへ http://math.a.la9.jp/2prd.htm
790:１３２人目の素数さん
19/09/03 11:15:05.59 jVMNxAjV.net
a+1 が素数ならば a!+1 は a+1 の倍数である。
791:１３２人目の素数さん
19/09/03 11:50:58.00 ACtA2QeY.net
wilson
792:１３２人目の素数さん
19/09/03 13:20:48.72 5Iy0AKSj.net
>>736
〔問題824〕
3稜の長さが a,b,c (0<a≦b≦c, aa+bb+cc=1) の直方体を、体対角線を軸として回転させた。
このとき通過する部分の体積を求めよ。
分かスレ４５４ - 824,839,842,846-848,875-876
(類：東京工大,1993年)
793:１３２人目の素数さん
19/09/03 13:38:50.86 5Iy0AKSj.net
>>736
aa = 23･23/11298 = 0.0468224464507
bb = 55･55/11298 = 0.267746503806
cc = 88･88/11298 = 0.685431049743
体対角線をu軸とする。
① r(u) = (1/a)√(1-aa)･u (0 < u < aa)
②～⑤ (aa < u < 1-cc)
⑥ r(u) = (1/c)√(1-cc)･(1-u) (1-cc < u < 1/2)
⑥' r(u) = (1/c)√(1-cc)･u (1/2 < u < cc)
⑤'～②' (cc < u < 1-aa)
①' r(u) = (1/a)√(1-aa)･(1-u) (1-aa < u <1)
→ S(u) = πr(u)^2,
→ V = ∫[-1/2,1/2] S(u)du,
V(①) = V(①') = π(a^4)(1-aa)/3 = 0.00218832
V(⑥) = V(⑥') = π{(1-cc)/cc}(8c^6 -1)/24 = 0.0946902