夕食は $n$人々はランダムに円卓に来て座った。アナ、イヴァン、マークがその中にいたとしたら、彼らはいくつの方法で座ることができますか…

2
josf 2019-11-03 04:41.

問題:

夕食は $n$ (($n \geq 4$)人々はランダムに円卓に来て座った。アナ、イヴァン、マークがその中にいた場合、アナとイヴァンが隣同士に座らず、少なくとも1人がマークの隣に座るように、いくつの方法で座ることができますか?(注:円卓は、回転のみが異なる座席配置を意味します。)

私の試み:
私が持っている場合$n$ 円形のテーブルの周りに座っている人々、さまざまな配置の数は $(n-1)!$
私が持っている場合$2$ マークとアナの隣同士に座れるアレンジの数は $2 \cdot (n-2)!$。したがって、マークがイワンの隣に座っているアレンジメントの数も $2 \cdot (n-2)!$、そしてアナの隣にも座っています $2 \cdot (n-2)!$

私がこの問題について知っているのはそれだけです。

5 answers

3
N. F. Taussig 2019-11-03 05:13.

方法1: シートマーク。彼を基準点として使用します。

マークの隣に座っているのはアナだけです。彼女は左または右の2つの方法で座ることができます。それは去ります$n - 2$座席。イワンはアナやマークの隣に座ることができないので、彼は座っているかもしれません$n - 4$方法。残り$n - 3$ 残りの人は着席できます $n - 3$ の座席 $(n - 3)!$マークを基準にしてテーブルの周りを時計回りに進む方法。したがって、$2(n - 4)(n - 3)!$ そのような取り決め。

マークの隣に座っているのはイワンだけです:対称性により、$2(n - 4)(n - 3)!$ そのような取り決め。

アナとイワンの両方がマークの隣に座っています:アナを座らせるには、マークの左または右の2つの方法があります。イワンはマルコの反対側に座らなければなりません。残り$n - 3$ 残りの人は着席するかもしれません $n - 3$ の座席 $(n - 3)!$マークを基準にしてテーブルの周りを時計回りに進む方法。したがって、$2(n - 3)!$ そのような座席配置。

合計: 3つのケースは相互に排他的で網羅的であるため、許容される座席配置の数は \ begin {align *} 2(n-4)(n-3)です。+ 2(n-4)(n-3)!+ 2(n-3)!&= [4(n-4)+ 2](n-3)!\\&=(4n-14)(n-3)!\ end {align *}

方法2: シートマーク。彼を基準点として使用します。

AnaまたはIvanのどちらが彼の隣に座っているかを選択します。その人がマークのどちら側に座っているかを選択します。残りの席$n - 2$マークを基準にして円の周りを時計回りに進むと、人々が移動します。これは与える $$2 \cdot 2 \cdot (n - 2)! = 4(n - 2)!$$ 座席配置。

これらから、アナとイワンが隣り合って座っている配置を差し引く必要があります。これが起こるためには、彼らは両方ともマルコの同じ側に座っていなければなりません。マークの隣にあるものを選択してください。その人がマークのどちら側に座っているかを選択します。その人がアナの場合、マークが彼女の反対側にいるので、彼女の隣にイワンを座らせる唯一の方法があります。同様に、IvanがMarkの隣に座っている場合、Markは反対側にいるため、AnaをIvanの隣に座らせる方法は1つしかありません。これらの3つのシートが埋まったら、残りのシートをシートします$n - 3$ 残りの人 $n - 3$テーブルの周りを時計回りに進むと、席に着きます。がある $$2 \cdot 2 \cdot (n - 3)! = 4(n - 3)!$$ そのような座席配置。

また、最初のカウントで2回カウントしたため、AnaとIvanの両方がMarkの隣に座っている座席配置を差し引く必要があります。1回はAnaをMarkの隣に座っている人として指定したとき、もう1回はIvanを人として数えたときです。マークの隣に座っている人。上に示したように、 $$2(n - 3)!$$ アナとイワンの両方がマークの隣に座る座席配置。

したがって、許容される座席配置の数は次のとおりです。 $$4(n - 2)! - 4(n - 3)! - 2(n - 3)! = [4(n - 2) - 4 - 2](n - 3)! = (4n - 14)(n - 3)!$$

1
S. Dolan 2019-11-12 14:59.

まず、A、M、Iの配置だけを考えてみましょう。

がある $2$ Mは真ん中になければならないので、3つすべてが一緒になるように配置します。

がある $4(n-4)$ AとIのいずれかをMの片側または反対側に配置し、それらの3番目をいずれかに配置するため、2つだけを一緒にするための配置 $n-4$ 座席。

したがって、 $4n-14$ 指名された人々のための取り決めとこれらの取り決めのそれぞれのためにあります $(n-3)!$残りのゲストの手配; の合計$(4n-14)(n-3)!$ 段取り。

0
mjqxxxx 2019-11-12 06:29.

Ana、Mark、Ivan、およびの可能性のタイプ $n-3$ 空の椅子は次のように書くことができます

  1. $AMI-$
  2. $IMA-$
  3. $AM-I-$
  4. $MA-I-$
  5. $IM-A-$
  6. $MI-A-$

どこ $-$少なくとも1つの椅子の列を示します。各構成はに対応します$(n-3)!$ 残りの配置を考慮した座席 $n-3$椅子に座っている人。1.と2.はユニークな構成です(椅子の列には長さがあります$n-3$); 残りの項目はに対応します$n-4$ 椅子の最初の列の長さはすることができるので、それぞれの構成 $1,2,\ldots,n-4$。つまり、合計は $$ (n-3)!\cdot(2 + 4\cdot(n-4)) = (4n-14)(n-3)! $$

0
CopyPasteIt 2019-11-13 18:59.

しましょう $A$AnaがMarkの隣にあるか、IvanがMarkの隣にある場合の座席配置の数を表しますが、両方ではありません。場合$n \ge 5$ それを示すのは難しくありません

$\tag 1 A = 4 (n-3) (n-4) \,(n-4)!$

の因数 $4 = 2 \times 2$Ana / Ivanインターチェンジと左/右インターチェンジを2倍にすることで得られます。残り$n - 2$ 要因は、 https://en.wikipedia.org/wiki/Rule_of_product 残りを着席させながら $n - 2$ 人(最後に着席した人は、 $1$)。だが$A = 0$ いつ $n = 4$ など $\text{(1)}$ の正しいカウントも提供します $n \ge 4$

しましょう $B$AnaとIvanの両方がMarkの隣にいるときの座席配置の数を表します。それを示すのは難しいことではありません

$\tag 2 B = 2 \,(n-3)!$

の因数 $2$Ana / Ivanインターチェンジを2倍にすることで得られます。これには、同時に左/右インターチェンジも組み込まれています。繰り返しになりますが、製品のルールを使用しながら、残りの各人を着席させます。

私たちが計算する代数を使用する

$\tag 3 A + B = (4n - 14) \, (n - 3)!$

上記の手法をNFTaussigの方法1と比較してください(わずかな違い)。

0
CopyPasteIt 2019-11-17 13:27.

再帰的な手法を使用して答えを見つけることもできます。

この問題は、次の場合にのみ解決策があります。 $n \ge 4$。ために$n \ge 4$ 定義する

$\quad A(n) = \text{the number of solutions where Mark IS NOT next to BOTH Ana and Ivan.}$

$\quad B(n) = \text{the number of solutions where Mark ---IS---- next to BOTH Ana and Ivan.}$

合計を求めたい $C(n) = A(n) + B(n)$

私たちの座席カウントアルゴリズムは、「到着」したときに既存の多様な座席配置に一度に1人ずつ着席することによって達成されると主張できます。また、最初に到着した3人は、マーク、アナ、イワンです。

つまり、4人称が到着すると、

$\quad A(4) = 0 \text{ and } B(4) = 2$

座席配置。

のすべての座席配置のリストがあるとします。 $n$ 人々、そして今、私たちは次の席に着かなければなりません $(n+1)^{\text{th}}$人。組み合わせ/カウント引数を使用して、次のことを実証できます。

$\tag A A(n+1) = (n-1)A(n) + 4B(n)$

そして

$\tag B B(n+1) = (n-2) B(n)$


組み合わせ問題の面白いところは、いくつかの方法で解決できることが多く、さまざまな解決策で同じ結果が得られたときに答えを確認できることです。興味のある読者は、次のことに取り組むことができます。

演習:インダクチンを使用して、ここで説明する再帰モデルが、これに見られる座席配置方法と同じ結果をもたらすことを示します https://math.stackexchange.com/a/3433525/432081


この再帰モデルから始めて、閉じた式の答えを導き出すことも可能です-を参照してください。 https://math.stackexchange.com/a/3434904/432081

Related questions

MORE COOL STUFF

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは、夫に会ったとき、典型的な交際のアドバイスに逆らいました。

マイケルシーンが非営利の俳優である理由

マイケルシーンが非営利の俳優である理由

マイケルシーンは非営利の俳優ですが、それは正確にはどういう意味ですか?

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

特徴的なスターのコリン・エッグレスフィールドは、RomaDrama Liveでのスリル満点のファンとの出会いについて料理しました!加えて、大会での彼のINSPIREプログラム。

「たどりつけば」をオンラインでストリーミングできない理由

「たどりつけば」をオンラインでストリーミングできない理由

ノーザンエクスポージャーが90年代の最も人気のある番組の1つになった理由を確認するには、Blu-rayまたはDVDプレーヤーをほこりで払う必要があります。

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖は、世界で2番目に大きいボイリング湖です。そこにたどり着くまでのトレッキングは大変で長いですが、努力する価値は十分にあります。

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

サロンからのヘアトリミングや個人的な寄付は、油流出を吸収して環境を保護するのに役立つマットとして再利用できます。

ホワイトハウスの最も記憶に残る結婚式を見てください

ホワイトハウスの最も記憶に残る結婚式を見てください

過去200年以上の間にホワイトハウスで結婚したのはほんの数人です。彼らは誰でしたか、そしてそこで結婚式を獲得するために何が必要ですか?

Netflixのジョエルマクヘイルとのジョエルマクヘイルショーは、ジョエルマクヘイルにぴったりの車を復活させます

Netflixのジョエルマクヘイルとのジョエルマクヘイルショーは、ジョエルマクヘイルにぴったりの車を復活させます

ジョエル・マクヘイル、マイク・コルター(スクリーンショット:Netflix)「私の神よ、これは1つのことを変えます。」これは、ジョエル・マクヘイルとのジョエル・マクヘイルショーの最後のジョークです。リアリティ番組の嘲笑と寛大なスナキネスの時間は、なじみのある顔を見つけます。

チームロケットは20年ぶりにポケモンシリーズでアッシュを破った

チームロケットは20年ぶりにポケモンシリーズでアッシュを破った

画像経由:@pancakeparadox(Twitter)。1997年にポケモンシリーズが初公開されて以来、チームロケット(またはラテンアメリカではチームロケット)として知られる悪役のグループは、何度もアッシュに直面してきました。

今週の科学技術でトランプがめちゃくちゃになったことすべて

今週の科学技術でトランプがめちゃくちゃになったことすべて

画像:ゲッティ私たち全員が千年もの間生きていて、私たちの体が燃える風によってほこりと長引く悲鳴だけに押し流されたと考えるのは驚くべきことです。私たちがそうしていないことを除いて、それはトランプ政権の最初の週の終わりであり、驚くほど多くの恐ろしいことがすでに起こっています。

あなたの「マイクロピッグ」が代わりに通常のピッグになってしまったとしても驚かないでください

あなたの「マイクロピッグ」が代わりに通常のピッグになってしまったとしても驚かないでください

そして今、あることを手に入れていると思っていたが、まったく別のことをしてしまった男の話。CBSニュースは、彼女が「ミニブタ」であるという誤ったふりをしてエスターを養子にしたカナダ人のスティーブジェンキンスの心温まる物語をもたらします。これは、特にせいぜいゴールデンレトリバーまたはセントバーナードをストラップします。

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya shared a sweet photo in honor of boyfriend Tom Holland's 26th birthday Wednesday

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

シーレン「Ms.JuicyBaby」ピアソンは、先月脳卒中で入院した後、「もう一度たくさんのことをする方法を学ばなければならない」ため、言語療法を受けていることを明らかにしました。

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

オスカー受賞者の世紀半ばの家には、3つのベッドルーム、2つのバス、オーシャンフロントの景色があります。

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、生後4か月の娘、モナコに母乳育児をしていると語った。

Come diventare Web Developer?

Come diventare Web Developer?

Vorresti diventare web developer e non sai da dove cominciare?! Qui troverai tutte le risposte necessarie, anche io non sapevo che strada intraprendere ma voglio aiutarti a non commettere i miei stessi errori. Cosa imparare? Le competenza essenziali per qualsiasi web developer sono almeno tre.

投資ノート:Bioscout AU$300万シード

投資ノート:Bioscout AU$300万シード

Bioscoutは、農家を運転席に置くという使命を負っています。Artesian(GrainInnovate)やUniseedと並んで、最新のシードラウンドでチームを支援できることをうれしく思います。問題真菌症による重大な作物の損失は、農民にとって試練であることが証明されています。

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

遠隔医療は、パンデミック後の時代では新しいものではなく、時代遅れの分野でもありません。しかし、業界を詳しく見ると、需要と供給の強力な持続可能性と、米国で絶え間ない革命となる強力な潜在的成長曲線を示しています。

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

2021年は、世界的なベンチャーキャピタル(VC)の資金調達にとって記録的な年でした。DealStreetAsiaによると、東南アジアも例外ではなく、この地域では年間で記録的な25の新しいユニコーンが採掘されました。

Language