was:ポーンたちのプレゼント交換



  • おなじみの「パズルの国のアリス」には素敵な問題がたくさんあります。
    「ポーンたちのプレゼント交換」もまた、そのような問題のひとつです。
    ネットでも参照できまして、 URL は以下です。

    http://www.nikkei-science.com/page/magazine/alice/202008/question.html

    さて、この「ポーンたちのプレゼント交換」の条件を少し変更した場合についてお考え頂きたく思います。

    オリジナルの問題では、《8人全員が自分の用意した以外のプレゼントを割り当てられる》ことを成功、そうならないことを失敗とすると、失敗する確率を求めるものでした。極限操作も念頭にいれると更に味わいに深みの出る問題です。

    今回の改作問題では成功ないし失敗の条件を変更した上で成功の確率についてお考え頂きたく思います。

    ポーンにクジを引いてもらいます。
    すると誰からもらうか誰にあげるかについて決まります。ポーンたちに立ってもらい、おのおのの左にはプレゼントを貰う人、おのおのの右にはプレゼントをあげる人となるように並んでもらいます。成功となるのは、8人全員がひとつの輪となって並ぶことができるときとします。

    失敗の例をいくつかあげておきます。
    オリジナルの問題でのように、自分が用意したプレゼントを自分がもらう羽目になる者がいたならば失敗です。
    また、AがBにプレゼントをあげる、BがAにプレゼントをあげるようになっていても失敗です。(これを2人による輪と呼ぶことにします。)
    また、AがBにプレゼントをあげる、BがCにプレゼントをあげる、CがAにプレゼントをあげるといった3人による輪ができていても失敗です。
    また、3人による輪がふたつ、2人による輪がひとつあるようでも失敗です。
    要するに8人による輪がただひとつできる、これが成功です。

    成功の確率はいかほどでしょうか。



  • これは難しい(私には(;'∀'))
    寝ながら考えますのでしばしお時間を!
    <昔原始根をベースにしたone time padを考えた時もこの手でした。!(^^)!



  • @riffraff 自己レス。
    柑橘類を収穫して、落ち葉、枯れ枝、まみれになったので昼風呂でうたたねしている内に・・・超初等解に?
    必要十分条件を満足しているかが、これからの課題。(;'∀')



  • @riffraff さん。
    >柑橘類を収穫して、落ち葉、枯れ枝、まみれになったので昼風呂でうたたねしている内に・・・超初等解に?

    とある政令指定都市のとある行政区に住まう当方、先日、自宅近所に数十年ぶりに熊が出たらしく。400メートルほど先なのですが。パトカーが巡回してスピーカーから注意を促していました。
    我が家は平野のど真ん中にあり、里山も近くには全然なく…
    近所の人からは「熊のエサにならないようにお宅の庭の柿を全部収穫してくれ」などと言われ、頑張って下半分は落としました。(甘柿なのですが我が家では誰も食しません。あうあう。)

    >昼風呂でうたたねしている内に・・・超初等解に?
    >必要十分条件を満足しているかが、これからの課題。(;'∀')

    (>_<) お風呂の浴槽内で寝落ちして死にそうになったことが4回くらいあります。お気をつけあそばせ。

    《超初等解》…そうかもしれません。改作問題はオリジナル問題よりは簡単なはずと自負しております。



  • 超初等解?
    リンク成功確率
    Π(自由度/場合の数)
    自由度:リンクルールに抵触することなく接続可能なポーンの数
    場合の数:自分を含めたポーンの総数
    {(n-1)!/(n^n)}
    8この場合は
    7!/(8^8)



  • @riffraff さん

    ポーンが2名の場合にこの式は正解を弾き出していない気がいたします。ちょっと考えてみました。

    改作問題でのクジのあり方はオリジナル問題と一致していますけれども… riffraffさんによるクジの設定は如何なるものなのでしょうか。

    分母が n^n になるところを拝察するに、次のようなものがriffraffさんによるクジの設定と等価なのでしょうか?

    ①n人のポーンたちには1からnまでの背番号を重複なく付番します。
    ②数字の1からnまで重複なく書かれたn枚のカードを用意します。これをカードセットと呼称しましょう。

    ③ポーンたちは全員、④の操作を行います。

    ④各ポーンはカードセットからランダムに1枚のカードを選びその数字と等しい背番号をもつポーンに自分が用意したプレゼントを送ることとします。【1枚抜いたカードはカードセットに戻します】

    ==

    一方、オリジナル問題や改作問題では、上記の④の設定が異なりまして、以下のようになります。

    ④'
    各ポーンはカードセットからランダムに1枚のカードを選びその数字と等しい背番号をもつポーンに自分が用意したプレゼントを送ることとします。【1枚抜いたカードはカードセットに戻しま《せん》】
    (最後のポーンのプレゼントの送り先は自動的に決まります。残り物ですね。

    上のようにクジの設定を変えれば、正解になると思います。たぶん。



  • @Hannibal さん
    考えてみます。(;'∀')



  • では用意していた解をば。

    想定解はこちら

    8人のポーンのうち1名をランダムに選び、そのポーンが参加している「輪」(1人からなるものも含みます)の人数が8人である確率を求めればよいことになります。

    そのためには当該のポーンが属する輪の人数が
    (1人ではない確率)×(2人以上だが2人ではない確率)×(3人以上だが3人ではない確率)×(4人以上だが4人ではない確率)×(5人以上だが5人ではない確率)×(6人以上だが6人ではない確率)×(7人以上だが7人ではない確率)
    を求めれば目的を達成できます。

    さて。以下ではポーンを歩と書きます。

    誰でもよいのでひとりの歩を選びます。この歩を1番目の歩と呼称します。

    《1番目の歩》
    1番目の歩が1人の輪を形成しない確率は
    7/8です。

    1番目の歩のプレゼント先の歩を2番目の歩と呼称します。

    《2番目の歩》
    ここまで1番目の歩まででは輪を形成していません。
    2番目の歩が加わることで輪が初めて形成されるとしたならばそれは1番目の歩から2番目の歩までの2名からなる輪に限られます。そうならない確率は
    6/7
    です。

    2番目の歩のプレゼント先の歩を3番目の歩と呼称します。

    《3番目の歩》
    ここまですなわち2番目の歩まででは輪を形成していません。
    3番目の歩が加わることで輪が初めて形成されるとしたならばそれは1番目の歩から3番目の歩までの3名からなる輪に限られます。そうならない確率は
    5/6
    です。

    3番目の歩のプレゼント先の歩を4番目の歩と呼称します。

    以下同様にして
    4≦k≦7 なるkについて

    《k番目の歩》
    ここまですなわち(k−1)番目の歩まででは輪を形成していません。
    k番目の歩が加わることで輪が初めて形成されるとしたならばそれは1番目の歩からk番目の歩までのk名からなる輪に限られます。そうならない確率は
    (8−k)/(9−k)
    です。

    《8番目の歩》
    ここまですなわち(k−1)番目の歩まででは輪を形成していません。
    8番目の歩が用意していたプレゼントの送り先は必ず1番目の歩です。
    すなわち、ただひとつの8人からなる輪のできあがりとなります。

    よって、求める確率は、
    (7/8)(6/7)(5/6)(4/5)(3/4)(2/3)(1/2) = 1/8
    となります。

    なお、riffraffさんからの最初の御解答では、想定解と比べると、分母が全て 8 になっているようです。



  • 《was:ポーンたちのプレゼント交換》の問題は、次に述べる問題を簡約化したものです。

    テーブルの上に1番から13番までの「トランプカードの」置場所をつくります。

    ジョーカーを除いた52枚のカードをよくシャッフルした後に4枚づつ、1番から13番までの置場所に、裏に伏せて配ります。

    Aは1、Jは11、Qは12、Kは13と読み替えます。

    最初にどの置場所のカードでもよいので、1枚、表にひっくり返します。

    表にしたカードに記されている数を読み、その数と同じ番号の置場所にこのカードを移動します。

    ●ループ開始点
    移動先の置場所にあるカードが全て表ならば、●ループ終了点に飛びます。
    裏のカードのうち1枚を選び、表にひっくり返します。
    表にしたカードに記されている数を読み、その数と同じ番号の置場所にこのカードを移動します。
    (●ループ開始点に飛びます)

    ●ループ終了点
    操作終了です。

    ○操作終了の時点でトランプの全てのカードが表になっている確率はどれほどでしょうか。

    ※52枚全てを使うのではなくスペードだけで13ある置場所に1枚づつ配った場合に、同様のルールで操作した際に全部が表になる確率は、《was:ポーンたちのプレゼント交換》に帰着されます。


Log in to reply
 

Looks like your connection to パズルハウス was lost, please wait while we try to reconnect.