Weekend Mathematicsコロキウム室テーマ別 /2.プレゼントの問題



コロキウム室(プレゼントの問題)


NO.72     4/2   MK142857 プレゼントの問題(1)

僕は、数学オリンピックに出てみようと思って、 この前、英才セミナーを受けてみました。 その時に出た問題の中で、面白い問題があったので送ります。

問題 

あるパーティーに参加する6人の友達が各自1つずつ 用意したプレゼントを交換し合うことになりました。 このとき、自分自身の用意したプレゼントをもらう人が 1人もいないようなプレゼント交換のし方は、 何通りあるでしょうか。



NO.74     4/3   Junko  プレゼントの問題(2)

N人でプレゼントを交換し合うとします。
自分自身の用意したプレゼントをもらう人が 1人もいないようなプレゼント交換のし方が、 f(N)通りあるとします。
f(6)の値を求めればいいわけです。
N=2から順番に考えてみました。
それぞれの人数で単独の仲間はずれが出ないように チェ−ンを作る(手をつないで輪を作る)にはどうしたらよいか と考えました。





          

NO.75     4/3   みかん  プレゼントの問題(3)

べつかい、別かい? 別解

6人がプレゼントをする全ての場合は6!=720通り

ゆえに 自分のプレゼントを受け取らない方法は
720−(1+15+40+135+264)=265
であるから、265通りとなる。
円順列というようなしゃれたものは使いませんでしたが 同じ結果となりました。
この方法は結局ランクを一つ下げて計算をする方法なので、 数式上の表現が面倒である。
この問題は「5人が交換する方法」を求めることであり、 そして「4人が交換する方法」を求めること・・ ・・。
  しかし、計算は前のことを使えるので案外簡単でした。



         

NO.76     4/4   水の流れ  プレゼントの問題(4)

MK142857さんのプレゼント問題ですが、 これは「完全順列」または、モンモール問題と 言いまして、一般にn人の場合のときまで、考えられます。
ご存じとは思いますが、n人について、 1人も自分自身の用意したプレゼントをもらわない方法を、 f(n)とすると、
f(1)=0,f(2)=1で、
漸化式:f(n)=(n-1){f(n-2)+f(n-1)}で、表現できています。
私自身教員7年目のとき、知ってそれ以来、 機会あることに教えています。
だから、f(3)=2(0+1)=2,f(4)=3(1+2)=9,f(5)=4(3+9)=44
f(6)=5(9+44)=265通りです。

また、j人だけが自分のプレゼントをもらう場合も、 考えられます。 (j=0,1,2,3,・・・,n) だから、 n=6,j=0のときが出題されたことになります。

さらに、n人とも自分自身のプレゼントをもらわない確率 は1/e(eは超越数)約36.8%位(訂正)です。
これは、関数eのx乗のマクロニー展開で証明されます。
私の場合は、席替えのとき、少なくとも1人以上の人が、 前と同じ席になる確率は約63%くらいあるのだから、 我慢しなさい。と言って生徒にはよく話します。



      

NO.77     4/4   みかん  プレゼントの問題(5)

NO.76に、 「また、j人だけが自分のプレゼントをもらう場合も、 考えられます。(j=0,1,2,3,・・・,n) だから、n=6 ,j=0のときが出題されたことになります。」
  とありますが、それではn とj の入った場合はどうなるのでしょうか。




      

NO.78     4/4   Junko  プレゼントの問題(6)

n人でプレゼントを交換し合うとします。
自分自身の用意したプレゼントをもらう人が 1人もいないようなプレゼント交換の仕方が、 f(n)通りあるとします。

またn人のうち、j人だけが自分自身のプレゼントを もらう場合の交換の仕方が、g(n,j)通りあるとします。
このg(n,j)について考えます。
n人のうち、自分自身のプレゼントを もらうj人を選びます。
これが、通り。
残った(n−j)人については、 自分自身の用意したプレゼントをもらう人が 1人もいないような交換の仕方をするわけですから、
f(n−j)通り
従って、
g(n,j)=×f(n−j) ではないでしょうか。

特に、g(n,0)=×f(n−0)
        =f(n)
となります。



      

NO.79     4/6   Junko  プレゼントの問題(7)

ところで、
漸化式:f(n)=(n-1){f(n-2)+f(n-1)} で表現できるのはなぜなのでしょうか?
さらに、これを解いて一般項を求められるのでしょうか?



NO.81     4/8   水の流れ  プレゼントの問題(8)

小島先生 こんにちわ
g(n、j)の値を表にしました。 20年前、この表を作って、有頂天になって、 黒板に書いた思いでがあります。

モンモールの三角形
n\j
      
     
    
   24
44452010  120
2652641354015 720
1854185592431570215040
         

g(n,0)とg(n,1) との差が ご覧のように常に1のように思います。
さらに、その大小が交互にきています。 g(n,n)=1 ,g(n,n−1)=0,g(n,j)=nCj×g(n−j,0)
などの性質があるよと言ってあります。
だから、パスカルの三角形にちなんで、 モンモールの三角形と言ったものです。 実に、懐かしい。



      

NO.82     4/9   MK142857  プレゼントの問題(9)

今晩は。僕の解き方を紹介します。

友達の人数がn人のときのプレゼント交換のし方の数をf(n)で表します。
n=1のときには、題意を満たすプレゼント交換はできないので、f(1)=0。
また、n=2のときには、2人の友達が互いに他のプレゼントをもらう場合しかないので、f(2)=1。

次に友達の人数が(n+2)人のときについて考えます。
(n+2)人の友達をそれぞれ
、A、A・・・・ An+2で表します。
がAのプレゼントをもらう場合の数の n+1倍がf(n+2)となるので AがAのプレゼントをもらう場合を考えます。

1、2より、
f(n+2)=(n+1){ f(n+1)+ f(n)}・・・・(1)
が成り立ちます。
(1)と、f(1)=0, f(2)=1を用いてf(6)を求めることもできますが、 もう少し計算を簡単にすることを考えます。

(1)の両辺から(n+2)f(n+1)引くと、
f(n+2)−(n+2)f(n+1)=−{f(n+1)−(n+1)f(n)}
また、f(2)−2f(1)=1
これより、数列{ f(n+1)−(n+1)f(n)}は、
初項が1、項比が−1の等比数列となり、
f(n+1)−(n+1)f(n)=(−1)(n−1)
即ち、 f(n+1)=(n+1)f(n)+(−1)(n−1)
従って、数列はf(n)漸化式
f(1)=0、f(n+1)=(n+1)f(n)+(−1)(n−1)・・・(2)
によって定まる数列とも言えるわけで、 この式を利用した方が、計算が簡単になります。
また、最近分かったことですが、nの値を限りなく大きくしていくと、 n人がプレゼント交換をしたときに全員が 他の人のプレゼントをもらう確率は限りなく 1/e=0,367879441・・・に近づきます。

完全順列に関する面白い問題をもう一つ作ったので紹介します。

問題

A君は、あるテストの問題を考えています。 その問題は、5つの空欄のあ る文章の空欄に入る語句を5つの選択肢の中から選んで答える問題です。 問題には、同じ語句を二度以上用いてはならない、 と書いてあるため、5つの空欄には、 全て異なる語句が入ることになります。 A君は、ちっとも勉強していなかったため、 直感で答えを書くしかありませんが、次の2つの方法のうち、 どちらの書き方をした方が得でしょうか。

  1. 5つの空欄に全て同じ選択肢を書く。
  2. 5つの空欄に全て異なる選択肢を書く。
 



      

NO.83     4/12   水の流れ  プレゼントの問題(10)

f(n)の一般項です。
数列はf(n)漸化式
f(1)=0、f(n+1)=(n+1)f(n)+(−1)(n−1)
で定まります。 NO.82で、「MK142857」さんが示してくれています。(2)の式です。
これより、
f(n+1)−(n+1)f(n)=(−1)(n−1)

ここで、a=f(n)/n!とおくと、

n+1−a=f(n+1)/(n+1)!−f(n)/n!
      =1/(n+1)!×{f(n+1)−(n+1)×f(n)}
      =1/(n+1)!×(−1)(n−1)

従って、階差数列の公式により。
=f(1)/1!=0

n≧2にたいしては、
=a+Σ(k=1..n-1)(−1)k−1×{1/(k+1)!}
  =Σ(k=1..n-1)(−1)k−1×{1/(k+1)!}
(Σの書き方が不自然でごめんなさい・・・junko)
つまり、
f(1)=0

n≧2にたいしては、
f(n)=n!×a
   =n!×Σ(k=1..n-1)(−1)k−1×{1/(k+1)!}
というわけです。


次にnがだんだん大きくなると、f(n)が1/eに近づくことです。

=f(n)/n!
 =Σ(k=1..n-1)(−1)k−1×{1/(k+1)!}
 =1/2!−1/3!+1/4!−1/5!+・・・+(−1)×1/n!(訂正4/16)
一方、eのマクロ−リン展開によれば、
=1+x+x/2!+x/3!+x/4!+・・・+x/n!+・・・
なので、x=−1とすれば、
=1/2!−1/3!+1/4!−1/5!+・・・+(−1)×1/n!+・・・(訂正4/16)

(これは、大学の1年で勉強します。・・・junko注)

従って、
lim(n→∽)f(n)/n!=lim(n→∽){1/2!−1/3!+1/4!−1/5!+・・・+(−1)×1/n!+・・・}(訂正4/16)
           =1/e

となります。

これは、手元にあったある研究冊子にありました。





NO.84     4/12   Junko  プレゼントの問題(11)

NO.82で、「MK142857」さんから出題された 問題について考えてみました。
高校生らしい現実的な問題ですね。
期待値で比較をします。

  1. 5つの空欄に全て同じ選択肢を書く。
    この解答の仕方では、必ず1題は正解となりますが、 それ以外は確実に得点できません。
    従って、こちらの期待値をE(n=5)とすると、
    (n=5)=1となります。
  2. 5つの空欄に全て異なる選択肢を書く。
    こちらの期待値をE(n=5)とします。
    5つの選択肢をでたらめに並べるとその並べ方は、
    5!=120通りあります。
    n個のうちj個だけが正解で、 それ以外は不正解な場合がg(n,j)通りあるとします。
    NO.81で、「水の流れ」さんが作ってくださった、 モンモールの三角形 を利用しました。
    (n=5)=5×g(5,5)/120+4×g(5,4)/120+3×g(5,3)/120
         +2×g(5,2)/120+1×g(5,1)/120+0×g(5,0)/120
      
        =5×1/120+4×0/120+3×10/120+2×20/120+1×45/120+0×44/120
       
        =(5+30+40+45)/120
    
        =1
    

というわけで、E(n=5)=E(n=5)=1という結果になりました。
ただし、「2」の解答の仕方の方がギャンブル性が高いということはいえますね。

   ところで、E(n=5)=1というのことですが、 これはn=5の場合に限った話しではないのではないかと思います。
NO.81で、「水の流れ」さんが作ってくださった、 モンモールの三角形 でn=7まで確認してみました。
一般に、
(n)=Σ(k=0..n)k×g(n,k)/n!

   =Σ(k=1..n)k×g(n,k)/n!
 
   =1
が言えるのではないかと思い、その証明を試みました。

まず、NO.81で、「水の流れ」さんが作ってくださった、 モンモールの三角形の 一番右の合計をみてください。
これは結局n個のものの並べ方ですから、n!になっています。
つまり、

 g(n,0)+g(n,1)+g(n,2)+・・・+g(n,n)

=Σ(k=0..n)g(n,k)

=Σ(k=0..n)f(n−k)

 (NO.78のg(n,k)=f(n−k)より)

=n!・・・(3)
ということです。これを証明で使います。

さて、

(n)=0×g(n,0)/n!+1×g(n,1)/n!+2×g(n,2)/n!+・・・+n×g(n,n)/n!
  
   =Σ(k=0..n)k×g(n,k)/n!

   =Σ(k=1..n)k×g(n,k)/n!

   =Σ(k=1..n)k×f(n−k)/n!

   =Σ(k=1..n)k×n!/{k!×(n−k)!}×f(n−k)/n!

   =Σ(k=1..n)1/{(k−1)!×(n−k)!}×f(n−k)

   =Σ(k=1..n)(n−1)!/{(k−1)!×(n−k)!}×f(n−k)/(n−1)!

   =Σ(k=1..n)n−1k−1×f(n−k)/(n−1)!

   =1/(n−1)!×Σ(k=1..n)n−1k−1×f(n−k)

    ここで、Σの変数kを1つずらします。

   =1/(n−1)!×Σ(k=0..n-1)n−1×f(n−1−k)

    さらに、(3)の式 

    Σ(k=0..n)f(n−k)=n!

    のnを(n−1)で置き換えると
、
    Σ(k=0..n-1)n−1f(n−1−k)=(n−1)!

    となるので、 

   =1/(n−1)!×(n−1)!

   =1
となります。



NO.85     4/13   Junko  プレゼントの問題(12)

NO.81で、 「水の流れ」さんが g(n,j)の表に関して、
「g(n,0)とg(n,1) との差が 常に1のように思います。 さらに、その大小が交互にきています。」 とかいていらっしゃいます。 これの裏付けをしました。

 g(n,0)−g(n,1)

=×f(n)−×f(n−1)

=f(n)−n×f(n−1)

ここで、NO.82で、 「MK142857」さんが示してくださった
f(n+1)=(n+1)f(n)+(−1)(n−1)・・・(2)
この式において、n+1をnで置き換えると、
f(n)=n×f(n−1)+(−1)(n−2)となります。
従って、
 g(n,0)−g(n,1)

=(−1)(n−2)

=(−1)
よって、nの偶奇により1または−1となるわけです。




NO.94     4/21   水の流れ  プレゼントの問題(13)

(n)=1の証明を書きます。
集合{1,2,3,・・・,n}(n≧1)上の置換を考えます。 ちょうどj(j=0,1,2,・・・,n)個の不動点を もつものの個数をg(n,j)で表すことにする。
(注:集合{1,2,3,・・・,n}上の置換を (a,a,・・・,a)とするとき、 a=iを満たす要素iをその置換の 不動点と言う。)
このとき、Σ(j=0...j=n)j× g(n,j) =n!   を証明します。
j× g(n,j) は、不動点の総数を表しています。

証明
集合{1,2,3,・・・,n}上の置換は全部でn!通りああります。
それらをf,f,f、・・・、fn! とします。
写像 f(i)で置換f による iの像を下記のように並べます。

                                  例 n=3のとき
          
         1列   2列  ・・・    n列                  1,2,3
f :(a1112 ・・・ a1n)      f: (@,A,B)
f :(a2122  ・・・ a2n)        f: (@,3,2,)
     ・                                       f:  (2,1,B)
      ・                                   f: (2,3,1)
      ・                                       f: (3,1,2)
fn!:(an!1n!2  ・・・ an!n )    f: (3,A,1)
            ↑    ↑              ↑                  ↑ ↑ ↑  
          (n-1)! (n-1)! ・・・    (n-1)!               2個2個2個
                                                 

ここで、1列を考えると、像が@である個数は 1以外の(n−1)個を並べた個数、 すなわち、(n−1)!に等しい。
2列を考えると、像がAである個数は 2以外の(n−1)個を並べた個数、(n−1)!に等しい。 ・・・・
n列を考えると、像がnであるのは n以外の(n−1)個を並べた個数、(n−1)!に等しい。
よって、不動点の総数は、n×(n−1)!=n!
すなわち、 Σ(j=0...j=n)j× g(n,j) =n!

  したがって、

E2(n)= Σ(j=0...j=n)j× g(n,j) /n!
       =1 
                   証明終
 

*不動点の総数を今までは、横で数えていましたが、 この証明は縦方向で数えました。




NO.100     5/9   水の流れ  プレゼントの問題(14)

集合{1,2,3,・・・,n}(n≧1)上の置換を考えます。 ちょうどk(k=0,1,2,・・・,n)個の不動点をもつものの 個数をg(n,k)で表すことにする。
(注:集合{1,2,3,・・・,n}上の置換を (a1,a2,・・・,an)とするとき、 ai=iを満たす要素iをその置換の不動点と言う。)
このとき、Σ(k=0...k=n)k× g(n,k) =2n!  をまず証明します。

 Σ(k=0...k=n)k× g(n,k)  
=Σ(k=1...k=n)k× g(n,k)
=Σ(k=1...k=n)k×k× ×f(n−k)
            注1 
=Σ(k=1...k=n)k×k× n!/{k!×(n−k)!}×f(n−k)
=Σ(k=1...k=n)k×n×( n−1)!/{(k−1)!×(n−k)!}×f(n−k)
=Σ(k=1...k=n)k×n× n−1k−1×f(n−k)          
=Σ(k=1...k=n)k×n× g(n−1,k−1)
=nΣ(k=1...k=n)k× g(n−1,k−1) 
=n{Σ(k=1...k=n)(k−1)×g(n−1,k−1)+ Σ(k=1...k=n)g(n−1,k−1)}
=n{Σ(k=0...k=n-1)k×g(n−1,k)+ Σ(k=0...k=n-1)g(n−1,k)}
  注2                  注3
=n{(n−1)!+(n−1)!}
=2n! 

注1:NO.78のg(n,k)=f(n−k)より)

注2:NO.94のΣ(k=0...k=n)k×g(n,k)=n!より

注3:不動点の総数Σ(k=0...k=n)×g(n,k)=n!より

そして、不動点の個数をX(X=0,1,2,・・・,n)とし、 Xを確率変数とみると、 期待値E(X)=1・・・<NO.94ですでに証明済み >
さらに、 標準偏差σ(X),分散V(X)とすると
V(X)=E(X2)−{E(X)}2 で 
σ(X)=√ V(X) の公式から

 E(X)= Σ(k=0...k=n)k× g(n,k)/n!
  =2n!/n!=2
よって、
 V(X)=E(X)−{E(X)}
     =2−1=1 

 σ(X)=√ V(X) =1

感想:この確率変数Xは 期待値と標準偏差がともに1となった。 これには何か意味があるのだろうか。 他にまだ、調査研究することがあるのだろうか。 解明していない。

更に、
Σ(k=0...k=n)k× g(n,k)=5n!
Σ(k=0...k=n)k× g(n,k)=15n!
と、予想できます。証明はまだやっていません。
この証明は時間があれば、挑戦したいです。 これは何を意味するか分かりませんが。



 

NO.106     5/29   ヴァ−    プレゼントの問題(15)

このまえの水の流れさんの結果から次のような関係があると予想できます。
Σ(k=0...n)km×g(n,k)=h(m)×n!
ここで、h(m)に関して次の漸化式が成立することを証明します。

[証明]

m=0のときは、不動点の総数を考えることになりますが、
これは、すでに証明済みです。

m>0のときは、
h(k)×n!=Σ(k=0...n)km×g(n,k)
=Σ(k=1...n)km×g(n,k)
=Σ(k=1...n)km×nCk×f(n-k)
=Σ(k=1...n)km×n!/{k!(n-k)!}×f(n-k)
=Σ(k=1...n)km-1×n×(n-1)!/{(k-1)!(n-k)!}×f(n-k)
=Σ(k=1...n)km-1×n×n-1Ck-1×f(n-k)
=Σ(k=1...n)km-1×n×g(n-1,k-1)
=n×Σ(k=1...n)km-1×g(n-1,k-1)
=n×Σ(k=0...n-1)(k+1)m-1×g(n-1,k)
=n×Σ(k=0...n-1){g(n-1,k)×Σ(i=0...m-1)m-1Ci×ki}
=n×Σ(i=0...m-1){m-1Ci×Σ(k=0...n-1)ki×g(n-1,k)}
=n×Σ(i=0...m-1){m-1Ci×h(i)×(n-1)!}
=n!×Σ(i=0...m-1)h(i)×m-1Ci

両辺をn!で割れば証明したい式が得られます。

ところで、このh(m)は統計学で言う「(原点のまわりの)m次のモーメント」です。

このモーメントを先の式を使ってmの値に応じて順番に計算すると
次のように変化します。
m h(m)
0 1
1 1
2 2
3 5
4 15
5 52
6 203
7 877
8 4140
9 21147
10 115975




NO.644 '99 11/1水の流れプレゼントの問題(16)

皆さんは、プレゼントの問題(9) の中にある次のような問題をご存じでしたか。

問題
A君は、あるテストの問題を考えています。 その問題は、5つの空欄のある文章の空欄に入る語句を5つの選択肢の中から選んで答える問題です。 問題には、同じ語句を二度以上用いてはならない、と書いてあるため、 5つの空欄には、全て異なる語句が入ることになります。 A君は、ちっとも勉強していなかったため、直感で答えを書くしかありませんが、 次の5つの方法のうち、どちらの書き方をした方が得でしょうか。



いわゆる正解数の期待値を求めてください。



NO.923 2001.1.10.qthumanプレゼントの問題(17)

(一部訂正1/12)

プレゼント交換の問題で少し加わった問題がありました。

円卓に8人座っています。この8人でプレゼント交換するのです が、自分のプレゼントはもらうことはできず、しかも右隣の人に渡す事ができないとします。 このとき何通りの交換の仕方があ るでしょう。
また一般的にn人の場合についてはどうでしょう。



戻る