A council has $6$ members and decisions are based on agreeing and disagreeing votes. We call a decision making method an Acceptable way to decide if it satisfies the two following conditions: Ascending condition: If in some case, the final result is positive, it also stays positive if some one changes their disagreeing vote to agreeing vote. Symmetry condition: If all members change their votes, the result will also change. Weighted Voting for example, is an Acceptable way to decide. In which members are allotted with non-negative weights like $\omega_1,\omega_2,\cdots , \omega_6$ and the final decision is made with comparing the weight sum of the votes for, and the votes against. For instance if $\omega_1=2$ and for all $i\ge2, \omega_i=1$, decision is based on the majority of the votes, and in case when votes are equal, the vote of the first member will be the decider. Give an example of some Acceptable way to decide method that cannot be represented as a Weighted Voting method.
Problem
Source: 2016 Iran MO 2nd round p3
Tags: combinatorics, Iran
10.03.2018 18:19
I solved this some time ago but didn't manage to write solution, here it is: Mark any three members of the council, one may consider this as sub-council consist of only members with high ranks. First, if (strictly) more than half of six votes are positive (or negative), take that as the final decision of the council. But if exactly half of the votes are positive, and exactly other half are negative, use the choice that has an odd number of votes from marked members as the final decision. This method clearly satisfy the ascending condition. For symmetry condition, note that the no. of positive votes and negative votes from marked members have different parity. Suppose this turn out to be a weighted voting, i.e., there exist such weights $\omega_1,\omega_2,...,\omega_6$. Let $S=\sum_{i=1}^{6}{\omega_i}$. WLOG assume $\omega_1,\omega_2,\omega_3$ to be those for the votes of three marked members. Since the case when exactly $\omega_{i_1},\omega_{i_2},\omega_j$ vote the same where $i_1,i_2\in \{ 1,2,3\}$ and $j\in \{ 4,5,6\}$, the final decision opposed to that, we get $$\omega_{i_1}+\omega_{i_2}+\omega_j <\frac{S}{2}.$$Summing this over three choices of $i_1,i_2$ with fixed $j$ gives $2(\omega_1 +\omega_2 +\omega_3)+3\omega_j <\frac{3S}{2}$ for all $j\in \{ 4,5,6\}$. Summing this over three choices of $j$ gives us $$6(\omega_1 +\omega_2 +\omega_3)+3(\omega_4 +\omega_5+\omega_6)<\frac{9S}{2}\implies \omega_1 +\omega_2+\omega_3 <\omega_4+\omega_5+\omega_6.$$But since the case when exactly $\omega_1 ,\omega_2 ,\omega_3$ vote the same, that becomes the final decision. This gives $$\omega_1 +\omega_2 +\omega_3 >\frac{S}{2}\implies \omega_1 +\omega_2 +\omega_3 >\omega_4+\omega_5+\omega_6.$$Thus, we've reached the contradiction and so this finish the problem.
20.04.2018 11:20
ThE-dArK-lOrD wrote: I solved this some time ago but didn't manage to write solution, here it is: Mark any three members of the council, one may consider this as sub-council consist of only members with high ranks. First, if (strictly) more than half of six votes are positive (or negative), take that as the final decision of the council. But if exactly half of the votes are positive, and exactly other half are negative, use the choice that has an odd number of votes from marked members as the final decision. This method clearly satisfy Ascending condition. For Symmetry condition, note that the no. of positive votes and negative votes from marked members have different parity. Suppose this turn out to be Weighted Voting, suppose the weights are $\omega_1,\omega_2,...,\omega_6$. Let $S=\sum_{i=1}^{6}{\omega_i}$. Note that we WLOG $\omega_1,\omega_2,\omega_3$ to be for the vote of three marked members. Since the case when exactly $\omega_{i_1},\omega_{i_2},\omega_j$ vote the same where $i_1,i_2\in \{ 1,2,3\}$ and $j\in \{ 4,5,6\}$, the final decision opposed to that, we get $$\omega_{i_1}+\omega_{i_2}+\omega_j <\frac{S}{2}.$$Summing this over three choices of $i_1,i_2$ with fixed $j$ gives $2(\omega_1 +\omega_2 +\omega_3)+3\omega_j <\frac{3S}{2}$ for all $j\in \{ 4,5,6\}$. Summing this over three choices of $j$ gives us $$6(\omega_1 +\omega_2 +\omega_3)+3(\omega_4 +\omega_5+\omega_6)<\frac{9S}{2}\implies \omega_1 +\omega_2+\omega_3 <\omega_4+\omega_5+\omega_6.$$But since the case when exactly $\omega_1 ,\omega_2 ,\omega_3$ vote the same, that becomes the final decision. This gives $$\omega_1 +\omega_2 +\omega_3 >\frac{S}{2}\implies \omega_1 +\omega_2 +\omega_3 >\omega_4+\omega_5+\omega_6.$$Thus, we've reached the contradiction and so this finish the problem. Comment: I wonder whether this method really use in real-world anywhere? There's only similar voting method I ever found using in my country, but not with parity-decided details, i.e. there's only one person to decide in case the whole council can't decide. How did you come up with this solution?
13.12.2020 20:43
Here's another solution: Name the members of the council $C_1, C_2,...C_6$. The decision making method is described by these statements: 1) If the number of agreeing (or disagreeing) votes exceeds $3$, then the outcome is positive (or negative). 2) If the numbers of agreeing and disagreeing votes are equal then, for a positive outcome, the $3$ council members who deposited an agreeing vote must be one of the following $3$-tuples: $(C_1, C_2, C_3), (C_1, C_3, C_4), (C_1, C_4, C_5), (C_1, C_5, C_6), (C_1, C_2, C_6), (C_3, C_5, C_6), (C_3, C_4, C_6), (C_2, C_4, C_5), (C_2, C_4, C_6), (C_2, C_3, C_5)$. This method fulfills the ascending and symmetry conditions. If it can't be represented as a Weighted Voting method, we are done. For the sake of contradiction, let $a_1,a_2,...,a_6$ be the weights of the council members $C_1, C_2,...C_6$ respectively. The second statement implies that the following $10$ inequalities hold: $a_1+a_2+a_3>a_4+a_5+a_6$, $a_1+a_3+a_4>a_2+a_5+a_6,..., a_2+a_3+a_5>a_1+a_4+a_6$ Adding these $10$ inequalities gives that: $$5(a_1+a_2+a_3+a_4+a_5+a_6)>5(a_1+a_2+a_3+a_4+a_5+a_6)$$which is clearly a contradiction. Note: To construct the $3$-tuples, since there are $6\choose3$$=20$ $3$-tuples and the number of $3$-tuples every specific $a_i$ is contained in is $5\choose2$$=10$ , all I had to do is make sure that each side had $\frac{10}{2}=5$ of every $a_i$. One may check that this solution is not identical to the one mentioned above by taking cases of the marked members. Maybe the motivation is a bit more clear in this solution.