Solving General Machhli Chhapak

Written in a single night. Credit goes to the friend who nerdsniped me with this problem, and the other friend who didn't stop me from having coffee when she should have.

Introduction

Machhli Chhapak is a game that has been doing the social media rounds recently. the game works as follows. A group of players sit together and play multiple rounds. In each round $n$, the statements '$n$ Machhli', 'paani mein gayi', and 'chhapak' are repeated $n$ times in order by all the players (so, for instance, the third round would have the statements '3 machhli', '3 machhli', '3 machhli', 'paani mein gayi', 'paani mein gayi', 'paani mein gayi', 'chhapak', 'chhapak', 'chhapak' in that order). An illustrative example:

let's formally solve it.

A Simple Problem: 2 Statements, 2 Players

We solve the problem by considering the simplest example: each round having a 1 and a 2, and there only being 2 players. A round $n$ has $2n$ values; the rounds look like $(1, 2), (1, 1, 2, 2), (1, 1, 1, 2, 2, 2), (1, 1, 1, 1, 2, 2, 2, 2)$ and so on. In each round, player 1 goes first (since the number of values in each round are even, and since both players alternate, at the beginning of a new round it is always player 1's turn).

The fundamental idea is to look at each round independently, solve it, and see if there is any useful structure to be found. For instance, consider round $n=3$, given by $(1, 1, 1, 2, 2, 2)$. This round has 3 1's and 3 2's. Player 1 and player 2 alternate; player one will speak the first 1, the third 1, and the second 2, and player 2 will speak the second 1, the first 2, and the third 2.

the insight here is that rounds can be further divided into two: the run of 1's and the run of 2's (for instance, round $n=3$ can be written as $((1, 1, 1), (2, 2, 2))$). We can first calculate how many 1's a player says, and then determine how many 2's the player says, which suffices to tell us what the player will speak in a given round.

To simplify the problem (and to motivate a result, later), we calculate the total times each player will speak. IN a round $n$, player 1 speaks values indexed by $(1, 3, 5, 7, ..., 2n-1)$, and player 2 speaks values indexed by $(2, 4, 6, 8, ..., 2n$)-which implies that in round $n$, both players speak $\frac{2n}{2}=n$ times. this fact is useful because, amongst other things, it now suffices to only calculate the number of 1's said by each player (since the players only say either a 1 or a 2, if $m$ is the number of 1's they say, $n-m$ must be the number of 2's they say).

Now, we calculate the number of 1's that both players say. In a round $n$, as mentioned earlier, there are $n$ 1's and $n$ 2's. Player 1 speaks 1's at the indices $(1, 3, 5, ..., n-1)$, which is equivalent to $\left\lceil{\frac{n}{2}}\right\rceil$. Player 2 speaks indices at $(2, 4, 6, ..., n)$. To make the expressions symmetric (as well as for a useful reason, later), we can model this as player 2 starting from an offset of 1 (essentially, player 2 starts off with $n-1$ 1's instead of $n$). consequently, player 2 speaks $\left\lceil{\frac{n-1}{2}}\right\rceil$ 1's.

With that, we're done: for an arbitrary round $n$, when it is player 1's turn, she will first speak $\left\lceil{\frac{n}{2}}\right\rceil$ 1's, then $n-\left\lceil{\frac{n}{2}}\right\rceil$ 2's; when it is player 2's turn, he will first speak $\left\lceil{\frac{n-1}{2}}\right\rceil$ 1's, then speak $n-\left\lceil{\frac{n-1}{2}}\right\rceil$ 2's.

A slightly complicated problem: 2 statements, P players

We now expand the model to allow $P$ players playing at once. For instance, consider the round $n=4$, represented by $(1, 1, 1, 1, 2, 2, 2, 2)$, and 3 players. Player 1 says $(1, 1, 2)$; player 2 says $(1, 2, 2)$; player 3 says $(1, 2)$. (I invite you to verify that this is true.)

It is evidently no longer true that each player says a total of $n$ statements in round $n$. given $P$ players, player 1 speaks at the indices $(1, 1+P, 1+2P, ..., 1+mP)$, player 2 speaks at the indices $(2, 2+P, 2+2P, ..., 2+mP)$, and player 3 speaks at $(3, 3+P, 3+2P, ..., 3+mP)$, with the constraint that $mP \leq n$. The situation is even more dour: the above expression is not quite correct, because player 1 doesn't always go first anymore for every round. (The easiest way to see that is to look at the rounds $((1, 2), (1, 1, 2, 2))$ and $p=3$). Our strategy will be to first figure out which player goes first for every round, then use that to determine how many statements each player makes in a given round, and finally use that to determine how many 1's and 2's each player speaks.

We begin by determining, for any round $n$, which player goes first. Each round $n$ has $2n$ values. Starting from $n=1$, we have $2+4+6+8+...$ until $2n$. IN round $n$, The sum of these up to round $n-1$ is the total statements made in the game so far. Since there are $P$ players, we can take the modulus of the sum and the number of total players, which will allow us to determine which player will go first this round.

Formally, let $p$ be a value in ${0, 1, 2, ..., P-1}$ (where $P$ is the total number of players). Before round $n$ begins, the total number of moves made so far are $2+4+6+...+2(n-1)$, which is equivalent to $n^{2}-n$ (the boring and tedious algebra left as an exercise to the reader...). The offset $o$ for a player $p$ is defined to be $(n^{2}-n+p) \mod P$, where $o$ is a zero-indexed indication of when $p$ speaks in round $n$: $o=0$ implies $p$ goes first, $o=1$ implies $p$ goes second, and so on.

Now, we calculate the total statements made by $p$ in round $n$. From the 2-player case earlier, our total statements were $\frac{2n}{2}$; we can do a similar exercise to get a similar result. Suppose player 1 goes first. Then, player 1 will speak until $mP \leq 2n$ (where $m$ is such that $m+1$ would violate the inequality). Rearranging, we get $m=\left\lceil{\frac{2n}{P}}\right\rceil$ and, using the offset (where we use the exact intuition from before, where for a player $p$ with offset $o$, we remove the first $o$ items from the round), the final expression for the total statements made by $p$ is $\left\lceil{\frac{2n-o}{P}}\right\rceil$.

Finally, we calculate the number of 1's said by each player. Each round has $n$ 1's; each player has $n-o$ 1's to speak, and speaks them in $P$ strides. Therefore, the number of 1's spoken by player $p$ (with the associated offset $o$) is $\left\lceil{\frac{n-o}{p}}\right\rceil$. And we are done: for any player $p$, in any round $n$, they start speaking from the offset $o$, and speak $\left\lceil{\frac{n-o}{P}}\right\rceil$ 1's and $\left\lceil{\frac{2n-o}{P}}\right\rceil-\left\lceil{\frac{n-o}{P}}\right\rceil$ 2's.

The actual problem: 3 statements, P players

After much arduous effort, we're finally at the original problem: 3 statements ($n$, Machhli, and Chhapak!!), and $P$ players. We can use much of the machinery we developed earlier to make this problem tractable, but it (unsurprisingly) has its own little idiosyncrasies which we'll have to deal with.

First, let's get the easy stuff out of the way. The offset $o$ for a player $p$ is defined in the same way as it was earlier, except now the sum is $3+6+9+12+...+3(n-1)$. This is represented by the equation $1.5n^{2}-n$, and $o=(1.5n^{2}-n+p) \mod P$. Similarly, the total statements made by a player $p$ are now $\frac{3n-o}{P}$.

The tricky bit here is determining how many 1's, 2's, and 3's a player speaks. It no longer suffices to determine the number of 1's and subtract them from the total statements made, which means we will have to explicitly calculate them.

The strategy we use is the following. We calculate the number of 1's in the usual way ($\left\lceil{\frac{n-o}{P}}\right\rceil$). For calculating 2's, we determine how many 1's have been calculated, and subtract them from the total terms of 1's and 2's (that is, subtract from $2n$). Finally, we subtract the number of 1's and 2's from the total terms in the round ($3n$), leaving us with the number of 3's.

Formally, let the number of 1s player $p$ speaks (with associated offset $o$) be $\left\lceil{\frac{n-o}{P}}\right\rceil$. Then, the total number of 2's that $p$ speaks is $\left\lceil{\frac{2n-o-P \left\lceil{\frac{n-o}{P}}\right\rceil}{P}}\right\rceil$, and the number of 3's $p$ speaks is $\left\lceil{\frac{3n - o - P \left\lceil{\frac{2n-o}{P}\right\rceil}}{P}}\right\rceil$.

That equation may seem a little arcane, so let's take an example. Consider round $n=7$ ($(1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3)$), and $P=4$. Player 1 goes at the beginning. In the first cycle (a cycle being all the players having spoken once), player 1 speaks the first term (1); in cycle 2, player 1 speaks the fifth term (1 again). In the third cycle, player 1 speaks the 9th term (2). Notice that, in the second cycle, a 2 was already consumed (by player 4). If we want to calculate the number of 2's spoken by player 1, we have to subtract the 2's already spoken before we divide. We do that by taking all the 1's and 2's together (14 terms, in this case) and subtracting all the cycles which consume all the 1's ($14 - 4 \left\lceil{\frac{7}{4}}\right\rceil$), yielding 6 2's. Similarly, for the number of 3's, we take all the terms of 1's, 2's, and 3's (21 terms), and subtract all the cycles which have consumed 1's and 2's ($21 - 4 \left\lceil{\frac{14}{4}}\right\rceil$), yielding 5 3's. Divide these by $P$, and take the ceiling, and we're done.

The general problem: S statements, P players

We now present the solution to the problem of General Machhli Chhapak in its full glory.

Let each player be indexed by $p$, $p \in {0, 1, 2, ..., P-1}$. Let $o$ be an integer, called the offset, associated with each player $p$, defined as $o=(\frac{S}{2} n^{2} - n + p) \mod P$ ($o \in {0, 1, ..., P-1}$).

In round $n$, player $p$ is the $o+1$th player to speak. Every player $p$ makes $S$ statements. The problem is to determine, for each $s_i$ ($i=1, 2, 3, ..., S$), how many times $s_i$ is spoken.

The total statements made by a player in round $n$ are $\left\lceil{\frac{Sn-o}{P}}\right\rceil$. Statement $s_1$ is made $\left\lceil{\frac{n-o}{P}}\right\rceil$ times. Statement $s_i$ is made $\left\lceil{\frac{i n - o - P \left\lceil{\frac{n (i-1) - o}{P}}\right\rceil} {P}}\right\rceil$ times.