Fill in Remaining Dice Rolls to Satisfy Average

Question

A coding problem originally sparked my question, but given the nature of the issue, I think it is most appropriate to ask mathematicians.

Suppose we have $n + m$ dice rolls and know the mean of these rolls (which will be an integer). However, we only know $m$ of the rolls. We must choose the remaining dice rolls such that the average corresponds to the average provided; it is guaranteed that there exists at least a single possible selection that would satisfy the average needed.

I created the following algorithm, which passed the test, but I cannot seem to prove why it works:

Before I delve in, I will label some variables. $j$ represents the total sum still needed from the remaining rolls; this will begin at the value $a * (n + m) - sum(m)$, where $a$ represents the average, $n$ represents the number of unknown rolls, $m$ represents the number of known rolls, and $sum(m)$ represents the sum of the known rolls. With this, we can now compute the algorithm:

1. Start by dividing $j$ by $n$; call the quotient $c$
2. If an even iteration, take the floor of $c$ and count it as our roll for the current turn; if an odd iteration, take the ceiling and count it as our roll for the current turn
3. Repeat steps 1 and 2 until there are no more rolls remaining

It is a simple algorithm, but I am having a hard time trying to prove why this works. Any advice on how to progress would be wonderful. Thank you.

Answer 1

If you guess $\ x_{m+1},x_{m+2},\dots,x_{m+n}\ $ for the values of the $\ n\ $ unknown rolls, then your guesses will give you the correct average $\ a\ $ if and only if $$ \frac{sum(m)+\sum_\limits{i=m+1}^{m+n}x_i}{n+m}=a\ , $$ or, equivalently $$ \sum_{i=m+1}^{m+n}x_i=a(n+m)-sum(m)=j\ .\tag{1}\label{e1} $$ This equation has a solution for integers $\ x_i \ $ with $\ 1\le x_i\le 6\ $ if and only if $$ n\le j\le 6n\ .\tag{2}\label{c2} $$ It's obvious that these conditions are necessary. That they're also sufficient is easily proved by induction. For $\ n=1\ ,$ equation \eqref{e1} is just $$ x_{m+1}=j\ , $$ and if conditions \eqref{c2} hold, then $\ 1\le x_{m+1}\le6\ ,$ and $\ x_{m+1}\ $ is a solution (the unique solution , as a matter of fact). Now suppose that whenever $\ n=r\ge1\ $ and conditions \eqref{c2} hold, then equation \eqref{e1} has a solution satisfying the required inequalities, and then consider equation \eqref{e1} for $\ n=r+1\ $ with $$ r+1\le j\le6(r+1)\ .\tag{2a}\label{e2a} $$ It follows from \eqref{e2a} that \begin{align} j-6r&\le6\tag{3a}\label{c3a}\\ 1&\le j-r\ ,\tag{3b}\label{c3b} \end{align} and since $\ r\ge1\ ,$ we obviously have $$ j-6r\le j-r\ , $$ and it then follows that $$ 1\le\max(1,j-6r)\le\min(6,j-r)\le6\ .\tag{4}\label{c4} $$ Now choose $\ x_{m+1}\ $ to be any integer in the interval $\ \big[\max(1,j-6r),\min(6,j-r)\big]\ $ (you could choose $\ x_{m+1}=$$\,\max(1,j-6r)\ $ or $\ x_{m+1}=\min(6,j-r)\ ,$ for instance), and set $\ j'=j-x_{m+1}\ .$ From our choice of $\ x_{m+1}\ $ we have $\ j-6r\le$$\,x_{m+1}\le$$\,j-r\ ,$ from which it follows that $$ r\le j-x_{m+1}=j'\le6r\ , $$ and the induction hypothesis therefore tells us that the equation $$ \sum_{i=(m+1)+1}^{(m+1)+r}x_i=j'\tag{5}\label{e5} $$ has a solution satisfying $\ 1\le x_i\le6\ $ for $\ i=m+2,$$\,m+3,$$\,\dots,$$\,m+r+1\ .$ Now adding $\ x_{m+1}\ $ to both sides of \eqref{e5} gives equation \eqref{e1} for $\ n=r+1\ .$ It follows by induction that conditions \eqref{c2} are sufficient for equation \eqref{e1} to have a solution satisfying the required inequalities.

You algorithm works because if the conditions \eqref{c2} are satisfied at any given stage, then choosing either $\ x_{m+1}=\left\lfloor\frac{j}{n}\right\rfloor\ $ or $\ x_{m+1}=\left\lceil\frac{j}{n}\right\rceil\ $ will guarantee that they're still satisfied at the next stage. It's unnecessary to alternate between them . You could choose the floor at every stage, or the ceiling at every stage, or switch randomly between them, and the algorithm will still work.

Here's a proof that choosing $\ x_{m+1}=\left\lfloor\frac{j}{n}\right\rfloor\ $ or $\ x_{m+1}=\left\lceil\frac{j}{n}\right\rceil\ $ when conditions \eqref{c2} are satisfied will guarantee that they will still be satisfied at the next stage.

First, dividing conditions \eqref{c2} through by $\ n\ $ gives $$ 1\le\frac{j}{n}\le6 $$ from which it follows that $$ 1\le\left\lfloor\frac{j}{n}\right\rfloor\le\left\lceil\frac{j}{n}\right\rceil\le6\tag{6}\label{ine6}\ . $$ From the right-hand inequality of conditions \eqref{c2} it follows that $\ (n-1)j\le6n(n-1)\ $ or, equivalently, $$ n(j-6(n-1))\le j\ , $$ from which it follows that $$ j-6(n-1)\le\left\lfloor\frac{j}{n}\right\rfloor\le\left\lceil\frac{j}{n}\right\rceil\ .\tag{7}\label{ine7} $$ From the left-hand inequality of conditions \eqref{c2} it follows that $\ n^2-n\le (n-1)j\ $ or, equivalently, $$ j\le n(j-(n-1)) $$ from which it follows that $$ \left\lfloor\frac{j}{n}\right\rfloor\le\left\lceil\frac{j}{n}\right\rceil\le j-(n-1)\ .\tag{8}\label{ine8} $$ From inequalities \eqref{ine6}, \eqref{ine7} and \eqref{ine8} it follows that $$ \max(1,j-6(n-1))\le\left\lfloor\frac{j}{n}\right\rfloor\le\left\lceil\frac{j}{n}\right\rceil\le \min(6,j-(n-1))\ , $$ and now by the same argument used on $\ x_{m+1}\ $ in the induction proof above, we get \begin{align} n-1&\le j-\left\lfloor\frac{j}{n}\right\rfloor\le6(n-1)\ ,\text{ and}\\ n-1&\le j-\left\lceil\frac{j}{n}\right\rceil\le6(n-1)\ , \end{align} which are the conditions \eqref{c2} needed to guarantee that the algorithm is still on track at the next stage.

Answer 2

So, here's my interpretation of the algorithm above:

1. sum values of the $m$ known dice
2. calculate $j$: $j=a(n+m)-sum(m)$
3. calculate $c$: $c=j \div n$
4. Alternate between rounding up or down $c$ to the nearest integer, depending on whether this is an odd-th or even-th iteration. This is now the value of die $n_i$.
5. re-calculate $j$ and $n$: $j=j-n_i,n=n-1$
6. return to step 3 unless all $n$ dice are assigned values.

If this is the entire algorithm (and $a$ is always an integer), then I think all we need to prove is that by the time all $n$ dice are assigned, $j=0$. I believe this would also be equivalent to proving that our algorithm always distributes the remainder of $j \div n$ across our $n$ dice.

I'm pretty sure that a general proof would only need to show that this holds when the remainder of $j \div n$ is even, and when it is odd - Your algorithm will clearly do so if the remainder is zero (if the remainder is zero, it will remain zero, because both the floor and ceiling of an integer is that integer, so your algorithm will just assign $j \div n$ across all $n$ dice), so if you can show that the other two conditions are always true, that would prove it for all $n$.