anonymous1173 wrote: We say positive integer $ k$ is monotone if and only if for every $ R$ poll profile and every winner $ a$ for $ R$ poll profile is also a winner for all $ a - good$ $ R'$ poll profiles. Prove that $ k$ is monotone if and only if $ k > \frac {m(n - 1)}{n}$. $ k$ is not used in the defination of itself as a monotone so there is no reason to have a conddition defining $ k$ so is the problem correct or have i got it wrong????????? the second one is most probably

i really cant understand the problem please help

sorry, i can't understand your problem with this question. maybe it can be from my bad english but if you can ask your problem more clear i will try to explain. but i can say that, "the first $ k$ in voters' lists are selected. it is $ k$'s definition. Being monotone is a property of $ k$."

sorry, i did not realize that

yes you are right. using kirkit's theorem in this problem is really sensible.

What is Kirkit's theorem? Pierre.

Ok, Kirkit's theorem does not exist, and this is only spam... Pierre.

So what is exactly the number of winners in a particular profile?

This statement is absolutely horrible. I do not think the problem itself is really difficult(i guess we will never know...), but the statement is absolutely unreadable making this problem impossible to think at, for me... If someone can rewrite it, or whatever, i would be really grateful for a statement in English.

There are $n$ voters and $m$ candidates. Every voter makes his/her arrangement of all candidates (there is one person in every place $1,2,...,m$) and votes for the first $k$ people in his/her list. $k$ candidates with most votes are elected (we call them winners). Consider the candidate $a$ and two elections $R$ and $R^{\prime}$. The election $R^{\prime}$ is $(R,a)$-good if for every voter $v$, the candidates that are in worse position on $v$'s list than $a$ in the election $R$ are also in the worse position than $a$ in $R^{\prime}$. We say that a positive integer $k$ is monotone if for every election $R$ and every winner $a$ for $R$, $a$ is also a winner for all $(R,a)$-good elections. Prove that $k$ is monotone if and only if \[ k>\frac{m\left( n-1\right) }{n}. \]

Here is a cleaner problem statement: Let $N$ denote a society of voters where each voter is endowed with preferences over a set of alternatives $A$ with $|N|=n>2$, $|A|=m>2$. A preference profile $R$ is an $n-$tuple of linear orderings on $A$ representing the preferences of voter's on $A$. Given some $k\in\{1,2,\dots,m\}$, the $k-$plurality choice rule chooses the alternatives achieving the highest vote after each voter assigns equal votes for all top $k$ alternatives in his preference ordering regardless of their ranking. Let $R$ and $R'$ be any two preference profiles and $a\in A$. We say that $R'$ $a-$dominates $R$ iff for every $i\in N$, all alternatives which are ranked below $a$ in $R_i$ are also ranked below $a$ in $R_i'$. $k-$plurality choice rule is said to be monotone iff for any $R$ and any $R'$ which $a-$dominates $R$, if $a\in A$ is chosen by $k-$plurality choice rule in $R$, $a$ is still chosen in $R'$. Assume $(m,n)\neq (3,4)$. Prove that, $k>\frac{m(n-1)}{n}$ is a necessary and sufficient condition for the monotonicity of $k-$plurality choice rule. Note: This problem has been proposed by Prof. Semih Koray of Bilkent University, Ankara, Turkey, whose one of primary research interest is in social choice theory; and electoral system. Note 2: For another Turkish olympiad problem regarding electoral system, which also happened to be proposed by Dr. Koray, see here.

Here is a neat solution: