Anonymous Voting

Number Theory Level 4

There is a 16-person committee that has to vote to approve a budget.

The members prefer to keep their votes anonymous. So they've adopted the following mathematical way to have every person vote Yes , vote No , or Abstain , while ensuring that all votes are kept secret.

We’ll call the chair $A_1$ and the other 15 members $A_2, A_3 , \ldots , A_{16}$ .

The chair takes a blank piece of paper, writes a large number, let's call it s , say $s=7923$ , on it, and passes this to $A_2$ .

Then $A_2$ adds $V_y=17$ for Yes , $V_n=1$ for No , or $V_a=0$ for Abstain . $A_2$ writes this sum on a new piece of paper, hands the new number to $A_3$ , and returns the paper with 7923 written on it back to the chair.

$A_3$ now has a piece of paper with either $7940$ (if $A_2$ voted Yes ), $7924$ (if $A_2$ voted No ), or 7923 (if $A_2$ abstained ). Because $A_3$ does not know the original number $s$ , there is no way for $A_3$ to know how $A_2$ voted.

This process continues with $A_3$ adding $V_y=17$ for Yes , $V_n=1$ for No , or $V_a=0$ for an abstention , and then passing the result to $A_4$ .

They continue until $A_{16}$ gives a number to $A_1$ , who adds a number for $A_1$ ’s vote. Let’s say the final sum is 8050. The chair subtracts the secret number 7923 from 8050 and gets 127. Then since

$127 = 7 \times 17 + 8,$

the chair announces that 7 people voted Yes , 8 people voted No , and there was 1 abstention (since $(7 + 8)$ is one less than 16, one person must have abstained).

Let us say, "a triplet of non-negative integer $(p,q,r)$ works" , if this voting system works flawlessly for any integer $s$ with $V_y=p$ , $V_n=q$ and $V_a=r$ . For instance, $(17,1,0)$ works.

Find the minimum positive integer value of $p$ when $q=801$ and $r=3$ such that $(p,q,r)$ works.

Bonus: Generalize this for $m$ number of members in the committee.

The answer is 1.

1 solution

Alex Burgess
Mar 7, 2019

The smallest value possible for $p$ is $1$ . It's easy to see this works, as $A_1$ subtracts the initial number to obtain $x$ . Then subtracts $16 = \#V_y + \#V_n + \#V_a$ .

$x - 16 = 800(\#V_n) + 2(\#V_a)$ which is easy to establish as $\#V_a < 400$ .

Generalising the value of $p$ for $q = 801, r = 3$ :

If $m < 400$ , $p = 1$ :

$x - m = 800(\#V_n) + 2(\#V_a)$ , converting to base $800$ and dividing the units by $2$ gives the values of $\#V_n$ and $\#V_a$ .

$\#V_y = m - (\#V_n + \#V_a)$ .

If $400 \leq m < 799, p = 2$ :

$x - 2m = 799(\#V_n) + (\#V_a)$ , converting to base $799$ gives the values of $\#V_n$ and $\#V_a$ .

$\#V_y = m - (\#V_n + \#V_a)$ .

If $799 \leq m, p = 798m + 4$ :

$x - 3m = (798m + 1)(\#V_y) + 798(\#V_n)$ , converting to base $798m + 1$ and dividing the units by $798$ gives the values of $\#V_y$ and $\#V_n$ .

$\#V_a = m - (\#V_y + \#V_n)$ .

Anonymous Voting

The answer is 1.

1 solution

0 pending reports