並び替えの問題で、一般的な教科書に載っているような問題ではなく、ウェブ上で検索しても同じ質問を見つけることが出来なかったので、自分で質問することにしました。
お知恵をお貸しください。
■□■□■
10人が部屋に集まって、中央の円卓に、ランダムに座ったとします。
そして、今両隣にいる2人のうちどちらとも隣に来ないように並び替えます。
(つまり、両隣には全く新しい2人が来ます)
これを繰り返していったとして、何通りの並び方が出来ますか。
※部屋に入って最初にランダムに座った並びも1通りと数えてください。
■□■□■
私が取り組んでいる活動で、時々こういった活動をするんですが、参加者の人数に応じて、果たして何回入れ替えが出来るのだろうということが気になって質問させて頂きました。
※今回は10人としていますが、人数が変わってもすぐ計算できるように、単純な円順列や数珠順列のような公式的なものを教えて頂けると助かります。
A 回答 (3件)
- 最新から表示
- 回答順に表示
No.3
- 回答日時:
No.2 です。
前の回答のときに書き忘れたことがありますので、追加です。この問題は、大学の情報系(理工系でも?)の学科で学ぶ離散数学の中のグラフ理論の応用問題です。グラフ理論で、n 点の完全グラフというグラフと、グラフのハミルトンサイクルとを学びます。これらの言葉を使って、問題を言い換えると、n 点の完全グラフに、辺を共有しないハミルトングラフの個数を求めよ、という問題になります。
No.2
- 回答日時:
今は、10人の問題ですが、一般的な形で、n 人の場合を考えます。
n 人を区別するために、その人たちに0から n - 1 までの番号を振ります。みんなが手をつないで輪になることを考えます。そのとき、適当な規則(後で述べます)で次に繋ぐ人を決めていき、うまくn 人で1つの輪ができるかどうかを調べます。できたらば、その規則でOKということになります。うまく n 人の輪ができる規則がいくつあるかを調べれば、この問題が解けることになります。輪になっていることから、最初の人を 0 番の人としても一般性は失いませんから、そのようにします。
規則は、何人かが手を繋いでいるとき、次に手を繋ぐ人を決める方法で表すことにします(最後に、0番の人が決まると、輪が完成となります)。
規則k: i 番目の人まで決まっているとき、次に手を繋ぐ人は、i + k 番目の人とする。ただし、i + k が n 以上になったら、n で割った余り番目の人とする。
ためしに、規則1を使ってみると、
0, 1, 2, ..., n - 2, n -1, 0
という n 人の輪ができます。
規則2を使ってみると、n が偶数ならば、
0, 2, 4, ..., n - 1, 1, 3, 5, ..., n - 2, 0
となり、n 人の輪ができますが、奇数ならば、
0, 2, 4, ..., n -2, 0
となって、n 人の輪ができません。
この場合、2で n 割り切れるかどうかによって、n 人の輪ができるかどうかが決まることがわかります。
このことを一般化して、n が k(1 ではない)で割り切れないとき、n の輪ができることがわかります(割り切れるとき、輪ができないこともわかります)。
すると、問題は輪ができる規則がいくつあるかを数えればよいことになります。つまり、n が k で割り切れないような k がいくつあるかを調べればよいことになります。
ここで、注意しなければならないことがあります。たとえば、規則1と規則(n - 1) 都を考えてみると、お互いに逆回りになっていることが分かります(規則1は、次の人と右手で繋ぐことを表しているとすれば、規則(n - 1) は、左手で繋ぐことを表していることになるという関係です)。
このことを踏まえて、n を割り切らない k を探す範囲は、n/2 まででよいことが分かります。
したがって、求める数は、n を割り切らない n/2 以下の k の個数プラス 1(規則1の分) となります。
折角ですから、No.1 さんの結果を参考に、試してみると、
n = 3 のとき、1通り
n = 4 のとき、1通り
n = 5 のとき、2通り (k = 1, 2)
n = 6 のとき、1通り (No. 1 さんの答えをどう読めばよいのかよく分かりませんでした。)
後は、ありませんでしたので、7から先の場合を書いておきます。
n = 7 のとき、3通り (k = 1, 2, 3) (k = 4 は、k = 3 と同じなど)
n = 8 のとき、2通り (k = 1, 3)
n = 9 のとき、3通り (k = 1, 2, 4)
n = 10 のとき、2通り ( k = 1, 3)
となります。
一般の n のときも、この考えで良いことが分かると思います。
改めて書いておきます。
n 人の人が円卓に着くとき、すべての人について両隣の人が異なるように着くことのできる席の着き方の数は、n/2 以下の n を割り切らない数の個数に1を加えた数である。
No.1
- 回答日時:
とりあえず順番に考えてみます。
自分の位置に関わらず隣の人のみで判断するので、Aさんの位置を固定してみます。
規則性を見つけるには一応少ない人数から順番に考えてみましょう。
3人までは1通りですね。
4人
A-B-C-D-A 隣になってない人がそれぞれ1人しかいないので動けません。
なので1通りですね。
5人
A-B-C-D-E-A それぞれ2人ずつ隣になっていない人がいます。
A-C-E-B-D-A もしくはこの左右逆のパターン
となり2通りですね。
※毎回左右逆のパターンと付けるのは面倒なので省略します。
6人
A-B-C-D-E-F-A それぞれ3人ずつ隣になっていない人がいます。
Aさんの隣にいけるのはCDEさん。
Dさんが隣に来ない場合
Dさんの隣に来れるのはABFさんですが、BFさんの隣にAさんは来れないので、
A-?-B-D-F-?-A の形になります。よって
A-C-F-D-B-E-A だけですね。
Cさんが隣に来ない場合
Cさんの隣に来れるのはAEFさんですが、BFさんの隣にAさんは来れないので、
Cさんが中央の場合
A-?-E-C-F-?-A の形になってしまい、Bさんの行ける場所が無いので
Cさんが中央ではない場合
A-?-C-?-?-?-A なので
A-E-C-?-?-D-A の形。つまり
A-E-C-F-B-D-A のみですね。
Eさんが隣に来ない場合
Cさんの場合と同様です。
A-?-B-E-C-?-A ではFさんの行き場がありません
A-?-E-?-?-?-A なら
A-C-E-?-?-D-A となり
A-C-E-B-F-D-A のみですね。
3通りありますが、それぞれ次隣になれる人が1りしかいないので、
どのパターンでも席替えは1回(席のパターンだと2通り)しかできません。
7人…とする必要もないですね。分かりましたか?
1度席替えをすると、どんなに上手くやっても隣になれる人は2人減ります。
(下手な並び替えをすると、もっと減ります)
つまり、最初の人数が10人であれば、最初座った時点で席替えして隣になれる人は残り7人、2回目で5人、3回目で3人、4回目で1人となり、5回目の席替えは不可能です。
よって5通りの並びができますね。
N人の場合だと、(N+1)/2通りですね。(少数以下切捨て)
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
重複順列
-
数学の質問です。 1〜6までの番...
-
数学の問題で4C0の答えを教えて...
-
男子4人と女子4人が輪の形にな...
-
数学
-
数学の質問です。 a、a、b、b、...
-
数学の問題です。 A.B.C.D.E.F...
-
1.2.3.4の中から重複を許して3...
-
a.b.c.d.eの5個から3個を選んで...
-
大至急お願いします。 8枚のカ...
-
数A教えてください
-
数学Aです。 7種類の異なる果物...
-
00~99、AA~ZZの組み合わせっ...
-
円順列の問題です。 大人2人と...
-
数字の順列問題
-
高校数学1の順列の問題?を教...
-
同じ数字が隣り合わない並べ方
-
4ケタの暗証番号 何通り?
-
数学の問題で確率、組み合わせ...
-
数学A 場合の数 ABCDEを辞書式...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
5人の人々を3人と2人のグループ...
-
重複順列
-
数学の質問です。 1〜6までの番...
-
数学の問題で4C0の答えを教えて...
-
a.b.c.d.eの5個から3個を選んで...
-
00~99、AA~ZZの組み合わせっ...
-
円順列の問題です。 大人2人と...
-
数学の問題です。 A.B.C.D.E.F...
-
1.2.3.4の中から重複を許して3...
-
円順列
-
数学Aです。 7種類の異なる果物...
-
数学に関する質問です。
-
男子4人と女子4人が輪の形にな...
-
数学
-
重複組み合わせの問題を教えて...
-
数学A 9人を3人ずつの3組に分け...
-
4ケタの暗証番号 何通り?
-
9人を3人ずつの3つのグループに...
-
順列の問題です。 4個の数字 1...
-
数学A 円順列の問いです。 6個...
おすすめ情報