10

Welcome to the fictional game of "color-tag"; the not-so-fast-paced cousin of paintball Where marking your opponent is all that counts!

If $A$ marks $B$ with his/her color, then $B$ will be permanently marked with $A$'s color, but at the same time all other people marked with $B$'s color will instantly be permanently marked with $A$'s color as well.

The first one to have marked everyone wins, and the game is finished!

$m<x$ where $m = 16$, and the number of players, $x$, is put in a room and assigned an unique color.

With every hour that progress, all the players have a probability of $1 - \frac{m}{x}$ of successfully marking another player. There is no limit as to how many times a player marks another player.

In the event that $A$ marks another player, the player, that is being marked, $B$, is chosen at random; Although players cannot mark themselves.

Now, I would like to know what the optimal number of players for the game having the highest probability of being the fastest.

That is, how many players are needed for the game to have the highest probability of finishing the fastest?

Sounds simple enough, right?

It turns out that it sounds simpler than it is; At least in my ears.

I've tried to warp my head around it, but I fail to find a viable approach.

I started out by calculating $(1 - \frac{16}{32} * \frac{1}{32})^{32}$, thinking that $(1 - \frac{m}{x} * \frac{1}{x})^x$ was the way to go about calculating the fastest possible game with respect to the number of players. I soon realized that there was no way that was going to give me anything near correct results, so I came up with something along the lines of $\sum_{n=0}^{x-1} ((1 - \frac{m}{x}) * \frac{x-n}{x})^n$, which I hoped would get me somewhere; But all it did was feed me an absurdly small number and make me realize that I've never been faced with a problem like this, and that I have no idea of how to solve it.

Right now, I'm not even considering that I must find the cases with the highest probabilities of success, then cross check to see which is he fastest; Which I do think is paramount in this problem, alas I know of no way to approach this.

Any input (especially tag additions) is greatly appreciated!

EDIT 1:

Just to make sure there is no confusion: If a player $A$ and another player $B$ both get to mark an opponent (opponents being all the other players) within a hour, then there is a chance, and it is allowed that $A$ marks $B$, and $B$ marks $A$.

Marking another player happens instantaneously and simultaneously.

JohnWO
  • 2,089
  • 14
  • 29
  • 2
    How do you handle simultaneous marking i.e. $A\to B$ and $B\to C$ at the same time, does $A\to C$ or not? – Dale M Oct 09 '14 at 04:46
  • Yes, $A\rightarrow B \wedge B \rightarrow C \implies A \rightarrow C$ – JohnWO Oct 15 '14 at 07:33
  • "With every hour that progress..." The grammar of that paragraph is confusing to me. – leonbloy Oct 16 '14 at 20:41
  • @leonbloy Thanks for pointing that out, and I understand your confusion, as it was erroneous. Please excuse the minor syntax and grammar errors, as english is not my first language. – JohnWO Oct 16 '14 at 21:26
  • Interesting idea, but I still don't understand the timing, or the definition of the "probability of marking." Is it possible to mark multiple players in the hour? – Michael Oct 17 '14 at 00:40
  • 1
    To make this a more precisely defined problem, it might be better to assume that at the beginning of each new hour, one player is selected (uniformly at random), that player then flips a biased coin. If "HEADS," the player randomly chooses exactly one other player to mark (uniformly chosen over all other players). If "TAILS," the player decides not to mark anyone. Thus, every hour, at most one player is marked. The same procedure is then repeated every hour. – Michael Oct 17 '14 at 00:42
  • What about $A \rightarrow C \wedge B \rightarrow C$? And what actually is the result of $A \rightarrow B \wedge B \rightarrow A$? – mhum Oct 17 '14 at 01:38
  • One player can mark one player per hour. $A\rightarrow B \wedge B \rightarrow B$ is defined as allowed in the edit, and it implies that players $A$ and $B$ will be marked with eachothers colors; Players can be marked with multiple colors at once. It is also said that one player can mark a maximum of one player per hour. – JohnWO Oct 17 '14 at 07:05
  • What happens when a player is marked with multiple colors at once? What happens when $A\rightarrow C\wedge B\rightarrow C$? – mhum Oct 17 '14 at 16:04
  • Can somebody explain to me when does the game "finish the fastest" ? Because I've absolutely no idea what that means ? Maybe someone can detail how to compute this probability in a simple case with few players ? – mercio Oct 19 '14 at 10:10
  • What happens with B if A tags B? Is B still playing the game, tagging others? If B then tags C, will C get A's color or B's color? – 2'5 9'2 Oct 25 '14 at 18:09
  • @alex.jordan A player can be marked with multiple colors. – JohnWO Oct 25 '14 at 19:08
  • That does not answer my question. If red tags blue, so that blue has red paint on them, and then this person (blue with some red paint) tags yellow, what colors will yellow have on them? – 2'5 9'2 Oct 25 '14 at 19:09
  • @alex.jordan Blue (and yellow). – JohnWO Oct 25 '14 at 19:31

2 Answers2

1

In short, you want to minimize the players in the game to expect the game to finish as quickly as possible. We could interpret the original question literally - 'Now, I would like to know what the optimal number of players for the game having the highest probability of being the fastest' - then we are simply looking for the number of players to finish the game in as few steps as possible. The shortest time possible a game could last only goes up as more players are added to the game, as it takes more steps for a player's color to spread to all the players in the game.

If on the other we're not trying to be the grammar police then we are trying to minimize the expected time it takes to finish the game. Representing the problem mathematically is very difficult: you have a dynamic Markov process in which the state of every player's color influences all future states of the game. I have not been able to find any probability distributions that fit the game; the closest I have been able to find is the Dirichlet-multinomial.

The answer is still that you want to minimize the number of players in the game to minimize the expected time to finish. With x players in the game, any given player needs to spread his color to x-1 separate players. For a player to win the game, every single player needs to be hit. As the number of players in the game increases, the chances that a specific player is hit in a given round decreases as x goes up. With two players in the game, the probability a player has of being hit is 1 - $\frac{m}{x}$. As x increases, this probability converges to $\frac{e-1}{e}$ or 0.63 for each player (granted I am suspicious of 'm' missing from the result. Also, resembles hat check problem).

And for some more math:

The probability a player does not hit in a given hour is $\frac{m}{x}$.

Let dt,c be the number of players at time t with a particular color c. The probability none of the players with color c are hit by other players in a given round is represented by $ (\frac{m}{x} + (1 - \frac{m}{x}) * \frac{x-1-d_{t,c}}{x-1} )^{x-d_{t,c}} $.

dt,c is an unknown discrete probability distribution for each color. I say unknown because attempting to represent the distribution as a probability could result in the universe imploding.

I believe the best way to prove the minimum time needed to finish needed to finish the game would be using mathematical induction. To do so you'd likely need to simplify the problem first, by demonstrating that a particular outcome is less than/greater than another outcome. And on that, good luck.

bjorn
  • 311
  • Thanks for answering, as it get me closer to the answer I'm looking for, even though I would like something more conclusive. As I am, as mentioned, looking for something more conclusive, I'll let this bounty run out and start a new one at 200-400 rep; Then if I get no more/better answers, I'll award this answer. – JohnWO Oct 18 '14 at 10:26
  • I understood some things differently. I thought people can be marked with several colours at a time (as in paintball), but they "have a color" (the color they shoot), and when you shoot someone you always also mark the ones already marked with that someone's "shooting colour". – Rojo Oct 18 '14 at 13:14
  • 1
    Previously I had stated 'When two players have the same color they will have the same color for the remainder of the game. We can therefore think of players merging into the same team when they share colors, continually absorbing other players and teams of players.' I've now realized that is incorrect and have updated the answer. In other words, if (1. A > B, 2. B > C) then C still does not have the color of A. So yes @Rojo you are correct. – bjorn Oct 26 '14 at 06:10
  • I'm confused. I also had bjorn's interpretation, based on the sentence "If A marks B with his/her color, then B will be permanently marked with A's color, but at the same time all other people marked with B's color will instantly be permanently marked with A's color as well." in the OP. What am I missing? – David E Speyer Oct 27 '14 at 10:55
1

Based on comments to bjorn's answer, there seems to be some confusion about the question. The way I understood it was that each person has an assigned color at any particular time. If player B shoots player A, then A changes her color to B's color. If player C then shoots player B, then players A and B both change to C's color. We want to know how long it takes for everyone to have the same color.

Let $G$ be the graph whose vertices are players and where the vertices $i$ and $j$ are joined by an edge if $i$ has shot $j$. Then two players have the same color exactly if they are in the same connected component of $G$.

Let's first look at the easier question where taggings happen completely at random: Every after every $\frac{\mbox{1 hour}}{(1-m/x)x}$, some player tags another player at random. So, after $h$ hours, the expected number of edges is $h(x-m)$, and any set of $h(x-m)$ edges is as likely as any other.

According to a theorem of Erdos and Renyi, if $h(x-m)$ is much more than $(1/2) x \log x$, the graph is extremely likely to be connected and, if $h(x-m)$ is much less than $(1/2) x \log x$, the graph is extremely unlikely to be connected. More precisely: Fix a constant $c$. Consider graphs with $x$ vertices and $(1/2) x \log x + cx$ edges, as $x \to \infty$. The probability that such a graph is connected is $\exp(- \exp(- 2c))$: extremely close to $0$ for $c$ negative and extremely close to $1$ for $c$ positive.

So I would expect connectivity after about $(1/2) \log x$ hours. The constant $m$ only produces second order effects.

Your situation is a bit different, because one shooter cannot tag two people in the same hour. I would predict the final answer is the same. You might try adapting my answer here to your setting.

Community
  • 1
David E Speyer
  • 61,724