|
%I #8 Nov 19 2017 12:47:24
%S 1,3,3,3,3
%N Minimum number of n-candidate full-rank-order ballots required to instantiate any tournament on n nodes (where A beats B in the tournament if and only if it does so in a majority of the ballots and we forbid pairwise ties).
%C Every entry is an odd number. a(n) <= a(n+1) <= a(n)+4. For all large enough n we know Cn/log(n) < a(n) < Kn/log(n) for suitable constants 0<C<K. Additional entries should be within the reach of computers. a(19) >= 5.
%H P. Erdos and L. Moser, <a href="https://www.renyi.hu/~p_erdos/1964-22.pdf">On the representation of directed graphs as unions of orderings</a>, Publ. Math. Inst. Hungar. Acad. Sci. 9 (1964) 125-132; also reprinted in Paul Erdos: The art of counting, Selected writings (ed. Joel Spencer) MIT Press 1973, pp. 79-86.
%H Warren D. Smith, <a href="http://rangevoting.org/PuzzHowManyBallots.html">Answer to puzzle 28</a> (surveys the problem)
%H Richard Stearns, <a href="https://www.jstor.org/stable/2310461">The voting problem</a>, Amer. Math. Monthly 66 (1959) 761-763. Warning: Erdos, Moser and Stearns actually consider a slightly different problem definition, where ties are allowed. That would define a different sequence which would upper-bound this one and is related to it, but the present sequence seems to be a little more pleasant.
%K hard,more,nonn
%O 1,2
%A _Warren D. Smith_, Sep 19 2006
|
