2016年8月10日 星期三

訓練數學感 110 ─ 數支數支輪到誰

http://4rdp.blogspot.com/2016/08/110.html

一群人,假設有 10 個人,每個人能夠出 1 ~ 5 根手指頭進行 "數支" 的活動。 當從發起人位置一直循環數到誰,誰就要被逞罰。 假設發起人的位置是固定,請問:
1. 你要出幾支手指頭最有利?
2. 你要站在靠近那裏的位置最有利?
3. 每個人被逞罰的機會相等嗎?

這個問題是由網友行天下提供的,他說公司每月有慶生會,採用此法處理剩餘的蛋糕與 Pizza,他觀察到這不是一個機會均等的決策過程,就請大家點出問題所在。

18 則留言:

  1. 每人最少出1支,最多出5支,所以總支數會是10~50,但10支和50支的機率最小,是1/((1/5)^10),
    接著是11支和49支的機率是C(10,1)*1/((1/5)^10),12支和48支的機率是C(10,1)*1/((1/5)^10)+C(10,2)*1/((1/5)^10)
    依此類推下去,然後
    把除10餘1的支數(11,21,31,41)的機率加起來就是第1個人被數到的機率,
    把除10餘2的支數(12,22,32,42)的機率加起來就是第2個人被數到的機率,
    .
    .
    .
    把被10整除的支數(10,20,30,40,50)的機率加起來就是第10個人被數到的機率。
    我沒有細算,但我覺得應該是第5個或第6個被選中的機率較高。
    第1個或第10個的機率則最低。
    以上是大家隨機出支數的前提下算出的,不知道正不正確。

    回覆刪除
    回覆
    1. 基本判斷正確,不過有個違反直覺的狀況,請先計算十人數支的期望值,再來看答案。

      刪除
  2. 莫非是每個人出的期望值是3支,所以10個人的期望值是30支,所以第10個人和他的前後(第9人和第1人)中獎機率反而最高?

    回覆刪除
  3. 大家很容易疏忽遊戲總人數,直覺認為是開頭者的對面會是苦主,包含我也一樣曾這樣想,總人數五人時就比較跟直覺相近。

    現在十個人玩,被數到的人就淘汰出局,每次都是從最小號開始數,假設大家每次都出三,請問最後勝利者會是誰?這又有數列可找,有興趣的人請討論留言,以此分辨貢獻度。

    回覆刪除
    回覆
    1. 如果照這樣的規則,其實跟總人數無關,
      都是最後一個人點到機率最高不是嗎?

      假設N個人,每人期望值都是3支,
      總支數3N,3N/N=3整除,所以不管人數
      幾人,都會是最後一個人點到機率最高。

      當然N越大,越多人的時候依照大數法則,
      總支數期望值會越接近3N,N小的時候誤差
      則會比較大。

      不知道這樣理解有沒有錯誤?

      刪除
    2. https://drive.google.com/file/d/0B-DZQIn9YfoDZVZEYVpob19tVDVzV0pCM0dfUG8xaWs3QmZN/view?usp=drivesdk

      但是我剛剛做了個試算表,模擬1000次的結果,我用肉眼看起來發現第10位前後的次數
      似乎也沒有特別高,到底是哪裡有問題呢?

      刪除
    3. 這似乎與試算表亂數函數有關,我曾自己產生均勻亂數,以中央極限定理是會有常態分佈,
      http://4rdp.blogspot.tw/2008/06/blog-post_14.html

      你說的對,數支總數除以人數後,都是最後一位中獎,那就沒甚麼好玩,其實只要每個人都出一樣,最後一個人一定出局,看來題目再修正為
      現在十個人玩,被數到的人就淘汰出局,每次都是從最小號開始數,假設每次數支總數為十,請問最後勝利者會是誰?這應該有數列可找,有興趣的人請討論留言,以此分辨貢獻度。

      刪除
    4. 這題好像是一條經典的寫程式題目...
      被淘汰的人依次為10, 1, 3, 6, 2, 9, 5, 7, 4
      勝利者是8

      刪除
    5. 你的答案顯示下一輪是從淘汰者的下一位開始,我的題目是一律從最小號開始。

      嗯,這題練習寫程式很適合,尤其是環狀資料結構。

      刪除
    6. 看來可以找兩條不同數列,一個是每次都從做小號開始,另一個是被淘汰者的下一家。
      新題目一修正為
      有 N 個人玩數支,被數到的人就淘汰出局,每次都是從最小號開始數,假設每次數支總數為 N (剛開始的數值),請問最後勝利者會是誰?

      新題目二為
      有 N 個人玩數支,被數到的人就淘汰出局,第一次從 1 號開始,之後為淘汰者的下一位開始數,假設每次數支總數為 N (剛開始的數值),請問最後勝利者會是誰?

      刪除
    7. 噢噢看錯了(掩面)
      應該是10, 1, 3, 5, 7, 9, 4, 2, 8
      勝利者是6
      不論多少人一定是先淘汰最後和第一人(假設人數等於數支總數)

      可以請教一下什麼是環狀資料結構嗎?因為好像之前沒聽說過...是用linked list來實現的嗎?

      刪除
    8. 沒那麼糟,可以當做第二個數列,這數列若排名,你可以當第一順位。
      當初 3M 想發明超強膠帶不成,結果產出便利貼一樣。

      這個問題確實是需要以 linked list 來實現,而環狀資料結構是指頭尾相接的資料串

      刪除
  4. 剛剛試寫了N=1~12時的情形,在都由編號最小的人開始數的情形下,勝利者依序為1,1,2,2,4,2,6,2,6,6,10,2...
    我找到的規律如下,
    如z423大提的,第1個淘汰的一定是N號,第2個淘汰的是1號,接著是3,5,7,..一直到最接近N的奇數號為止,
    此時已經至少淘汰掉一半以上的人數,剩下的只有偶數號2,4,6,8...,人數<=N/2。
    但這之後淘汰的順序就牽涉到N這個數本身有多少個因數,似乎就沒有一個規律可循了。
    我找不出一個通解來,還請大家多指教。

    回覆刪除
    回覆
    1. 聽起來,這題數列或許與質數有些關聯。

      刪除
    2. Tora 有一則貼文不見,補貼如下

      我拿一開始的問題問我朋友,他用SQL把所有可能用窮舉法列出來統計,
      http://imgur.com/a/qduy7
      果然是MOD(10)=0的次數最高,MOD(10)=5的次數最低。
      但是這差距不是那麼的大,所以即使用excel模擬很多次,
      肉眼看不出來差距也是正常的。
      我想如果今天人數變成100人的時候,第100人和第50人被選中的機率
      差距應該會更明顯,但是5的100次方用窮舉法的話可能要算到天荒地老了。

      另外站長後面這問題,出局編號依序應該是10,1,3,5,7,9,4,2,8,6所以6號最後出局是獲勝者。
      但是除了前面的1,3,5,7,9有規律之外,後面的4,2,8,6規律我還找不出來,哈。

      刪除
  5. 行天下私訊我,提供一個 Python 數支程式大家參考看看
    import random
    def fingers():
      finger=random.randint(1,5)
      return finger
    x=0
    while x <10000:
      result=fingers()+fingers()+fingers()+fingers()+fingers()+ \
         fingers()+fingers()+fingers()+fingers()+fingers()
      print (result%10)
      x+=1

    回覆刪除
  6. 網友行天下,程式跑出來的結果如下
    https://drive.google.com/file/d/0B_TFWEwZaQ8_WktVQTNiUmFZOFU/view?usp=sharing
    https://drive.google.com/file/d/0B_TFWEwZaQ8_X1E4Yk01TnBSSEE/view?usp=sharing

    回覆刪除
  7. 另外,數列與級數網站 http://web.ntnu.edu.tw/~499412058/series/Sequences.html 站長 潘彥廷,也提供一段 Python 程式

    from visual import*
    time = 100000
    tot_people = 10

    def test(time,tot_people):
      count = zeros((tot_people))
      for i in range(time):
        number = sum(ceil(random.rand(10)*5))%tot_people
        count[int(number)] += 1
      return count/time*10

    print test(time,tot_people)

    new_count = zeros((tot_people))
    for i in range(10):
      a = test(time,tot_people)
      new_count[a>1.04]+=1
      new_count[a>1.03]+=1
      new_count[a>1.02]+=1
      new_count[a>1.01]+=1
      new_count[a>1]+=1
      new_count[a<1]-=1
      new_count[a<0.999]-=1
      new_count[a<0.998]-=1
      new_count[a<0.997]-=1
    print new_count

    下面是潘站長對程式的說明
    我使用亂數模擬的方法
    ceil(random.rand(10)*5) 是每個人數支出的數字,放置在list內部,並做加總,還有找出餘數,也就是數支最後所選出來的人。
    接著進行統計count[int(number)] += 1
    當這個程式重複運行time = 100000,這麼多次後,印出每個人被選中的次數。
    由於大家被分到的機率是差不多相同的,為了放大這些人機率之間的差異,因此在下方做了一個迴圈來統計多次模擬的結果。
    雖然每次的結果不盡相同
    不過能夠看到,遠離第一個人的機率似乎會比較小。(離第一個人最遠的並不是第十個是第五個或第六個,因為第十個數完會回到第一個)

    回覆刪除