-2
$\begingroup$

$n$ persons are placed in a room. Each man has with him $2$ marbles. Each turn consists of one person taking another person's two marbles and destroying them along with one of his own marbles. A person is allowed to take marbles only from a person with $2$ marbles. A player gets a turn if he has at least $1$ marble and can take $2$ marbles from someone but the turns aren't in any specific order.

The process stops when no more marbles can be taken.

If $f(n)$ denotes the number of marbles left after the process ends, then I need to determine $f(n)$.

My work: I started by noting the first few values of $f(n)$. Everything was fine until $n=6$, from whereon I'd get multiple values of $f(n)$?

$$\begin{array} {|r|r|}\hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline f(n) & 2 & 1 & 0 & 2 & 1 & 3,0 & 2 & 4,1 \\ \hline \end{array}$$

As asked in the comments, I present how I found these values. Here's an example $n=6$:

visual representation of n=6

Each pair of two points represents the two marbles of each person. The line segments represent which marbles were destroyed in a single round.

One value of $f(n)$ is always given by $(2n \bmod 6)\bmod 3$. When $n$ is even then $f(n)=\frac{n}{2}$ is also a solution. I've noted this with observation, but I can't prove if these are the only values that would always arise.

I also think this problem can be connected with graph theory. I'm really a beginner at the same; I would appreciate if somebody could let me know how to phrase the problem in graph theoretical terms.

$\endgroup$
11
  • $\begingroup$ Rules are not clear $\endgroup$ Jan 4 at 16:46
  • $\begingroup$ You start with two marbles. You can take two marbles from another person and destroy them along with exactly one of yours. As long as you have at least one marble, you are allowed to keep on doing this. However, you can take marbles only from a person with 2 marbles. $\endgroup$
    – Sahaj
    Jan 4 at 16:48
  • $\begingroup$ Is there a goal in this game? what exactly are we trying to calculate? What choices does a player have on his\her turn? Calrfiy the orignal post not in comments. $\endgroup$ Jan 4 at 16:50
  • $\begingroup$ I think the post is clear enough and specifies all details. $\endgroup$
    – Sahaj
    Jan 4 at 16:51
  • $\begingroup$ Frankly I have no idea what you are asking. $\endgroup$ Jan 4 at 16:54

1 Answer 1

0
$\begingroup$

This is not really a game at all and would be better worded as "given n sets of $2$ etc.." and trying to find the final state, calling it a game is just confusing.

Final states:

When $ n=0 \bmod 2$ a final state can be ${n \over 2}$

When $n=0 \bmod 3$ a final state can be $0$

When $n=1 \bmod 3$ a final state can be $2$

When $n=2 \bmod 3$ a final state can be $1$

When $n$ can be partitioned into partitions of $3 (p3)$ and $2 (p2)$ in multiple ways (this is the case for all $n>5$ except 7) there will be multiple values as all partitions of $3$ can be $=0$ and partitions of $2$ can be $= {p2\over 2}$

[Your value for n=5 is wrong.] Since corrected.

$\endgroup$
3
  • $\begingroup$ Thanks for letting me know. I'll appropriately word the post. $\endgroup$
    – Sahaj
    Jan 4 at 17:48
  • $\begingroup$ This was what was causing the whole hullabaloo in the comments. $\endgroup$ Jan 4 at 17:50
  • 1
    $\begingroup$ Fixed it. A little ugly now as my mathjax knowledge is meh. $\endgroup$ Jan 4 at 17:55

Not the answer you're looking for? Browse other questions tagged .