There is a small town in old times. And there was one interesting game.
Consider $N$ people playing this game. Every evening they are getting together to play this game. Every evening exactly $N$ people come to play.
Game rules: everybody chooses random integer number from $1$ to $F$: $1,2,3,...,F$. $F$ is a constant value and never changes. So, $k$ persons write chosen number on the paper and name. There is some probability of participation. I mean with probability $\tau$ person will play this game.
Then they collect papers. They look at the numbers. If I choose number that nobody except me choose than I win this game. There could be multiply winners.
Example. $N = 6$, $F = 4$ and then $k=6$ that day then if
A wrote $3$,
B wrote $2$,
C wrote $3$,
D wrote $4$,
E wrote $2$,
F wrote $1$, then F and D won that game that day and every winner get 100 gold.
QUESTIONS
I ask you too find the expected number of winners per day. (solved)
And the hardest question is to find out the optimal $\tau$ in order to maximize expected number of winners. let's think that habitats are smart and try to use this optimal $\tau$ in order to get as much gold as possible.
My solution:
- Let's take a look on one day. I can choose $k$ people with $\binom N k$ ways of doing it. Lets think that these people will play and another $N-k$ will not.
So now we have $$ \sum_{k=0}^{N} \binom N k \tau^k (1-\tau)^{N-k} \cdot smth $$
Then let's deal with smth.
Lets $B(m,k,F)$ -- number of ways to write a random numbers, which are $\le F$ so that exactly $m$ persons are winners among $k$ people.
I can compute this number correctly.
Then I think that probability of winning of exactly $m$ persons is $$\frac{B(m,k,F)}{\sum_{m} B(m,k,F)}$$
Now I think that desirable thing is equal to the following:
$$ \sum_{k=0}^{N} \binom N k \tau^k (1-\tau)^{N-k} \cdot \sum_{m=0}^{k}m\cdot\frac{B(m,k,F)}{\sum_{m} B(m,k,F)} $$
And another answer to this problem you can see in the comments.
- But for should I do for optimal $\tau$? Derivative gives nothing.