Author Topic: A colaboration game  (Read 9029 times)

MrPuzzle

  • Jr. Member
  • **
  • Posts: 75
A colaboration game
« on: 十月 22, 2004, 02:50:20 pm »
Just got this problem from a friend (who doesn't read Chinese, otherwise, he would definitely be here). Seems interesting. Haven't thought about it, just want to post it here so that you guys have something to think about over the weekend.

-----------------------------
In order to test "the level of cooperation" in a group of n people, a card game is set up in the following way: inside a secret room, n cards, each of which contains a number from 1 to n on one side and a name of a person on the other side, are laid out on a table such that the numbers are facing up. The group members have no knowledge about the numbers that are assigned to them. Moreover the number-name mapping is a bijection (sort of renaming). Members of this group are invited inside the secret room one at a time. Each one of them is asked to to turn over up to n/2 cards to find her/his own card. Once he/she finishes his/her visit to the secret room, the cards are brought to their initial state (before the visit). If any of the members looses (cannot find her/his card), by definition, the group looses. Otherwise (every member finds his/her own card), the group wins. The group members can agree on a strategy before the game begins. Once the game starts, no communications are permitted. Is there a strategy that the group can invent in order to improve their probability of winning (making the probability of group success lower-bounded by a positive constant) ?

Elixir

  • Jr. Member
  • **
  • Posts: 32
A colaboration game
« Reply #1 on: 十月 22, 2004, 04:23:36 pm »
感觉上好象前一半人总翻前一半, 后一半人总翻后一半就是最佳方案.
[(n/2)! * (n/2)!]/n!

sean

  • Jr. Member
  • **
  • Posts: 86
A colaboration game
« Reply #2 on: 十月 22, 2004, 05:04:43 pm »
Quote from: Elixir
感觉上好象前一半人总翻前一半, 后一半人总翻后一半就是最佳方案.
[(n/2)! * (n/2)!]/n!


好像不对吧. 这个极限是 0.

fzy

  • Hero Member
  • *****
  • Posts: 520
A colaboration game
« Reply #3 on: 十一月 18, 2004, 03:41:21 pm »
The answer to the problem (making the probability of group success lower-bounded by a positive constant) is no. What any strategy can do at most is that every team member knows the range of the cards of thenmembers before him. Let's assume that the (k+1)th team member already knows exactly where the previous k cards lie. Then from 1st to the (N/2)th member, his chance to find his own card is (N/2/(N-k+1). Therefore the best any strategy can achieve is ((N/2)^(N/2))/[N(N-1)...(N/2+1), which converges to 0.

An immediate question is, how much better can we do than total random? The winning probability for total random is 1/2^N. Elixir's method is better. But unfortunately, not by a lot (although it might still be the best): From Stirling's formula, [(N/2)! * (N/2)!]/N! = √(π(N/2))/2^N. So we are better only by a factor of √(π(N/2))