What are these kind of problems called?

77 Views Asked by At

The question is that:

There are $100$ of coins, to be given to members of a family.

The eldest brother is the one who decides how to distribute them After his decision, family members vote if they accept it or not. The eldest brother also votes.

If the accepted votes are equal or more than half, the decision is made.

If not, the eldest brother will be killed, and the second-eldest brother will instead do the decision.

The process continues until the decision is made.

For example:

If there are $2$ people, then $1$st person: $100$ and $2$nd person: $0$ (acceptance is $\dfrac{1}{2}$).

If there are $3$ people: then $1$st person: $99$, $2$nd person: $0$, and $3$rd person: $1$ (acceptance is $\dfrac{2}{3}$ by $1$st and $3$rd).

The reason is that if $3$rd person does not accept it, the $1$st person will be killed and thus $2$nd will make the decision, being same with the case of $2$ people. Thus, $3$rd person will get nothing.

I want to practice solving the problem like this one, but I have no idea what people called this kind of problems, and thus cannot find any problems to practice.

I think it's close to combinatorics (maybe) and recursive algorithm.

Please give any advice.

3

There are 3 best solutions below

0
On

I think you're asking about where to find similar problems. I've seen this problem before as a brain teaser/puzzle about pirates. To find similar puzzles, you can click any links in the "Games" topic at the bottom of the Wikipedia page here. I would consider this a game theory problem.

0
On

The kind of thinking behind this problem is called 'backwards induction'. Check out the 'Centipede game' for another example.

0
On

Did you solve this problem completely? If there are $n$ family members, what is the acceptance? What if $n>100$ (very big family)? What if $n>200$?

The general formula is: $$\frac{\lceil{\frac{n}{2}}\rceil}{n}.$$ where $\lceil{x}\rceil$ is a ceiling function.