Here are some not-very-helpful comments: either the expressed desired can be extended by transitivity or they induce a cycle. Obviously, if they induce a cycle then no ordering can make everyone happy, so this case is not interesting. If they can be extended transitively, then the question becomes whether there is a poset on 20 vertices with exactly 2010 linear extensions. At this point, I have to admit that I really have no idea how to proceed. Linear extensions have some nice multiplicative structure. For example, if there exists a poset on 13 vertices with exactly 67 linear extensions, then we can build our 20-element poset easily: with vertices $v_1, v_2, v_3, w_1, w_2, w_3, w_4, \ldots$ set the $v_i$ smaller than all other vertices but incomparable with each other, set $w_1 < w_2 > w_3 < w_4$ and the $w_i$ smaller than the other 13 vertices, and let the remaining 13 vertices take the shape of our mystery 13-vertex poset. The total number of linear extensions of the resulting poset is $6 \cdot 5 \cdot 67 = 2010$. But it's completely unclear to me how to tell whether there exist posets on 13 vertices with 67 linear extensions. (In fact, any multiple of 67 dividing 2010 would be fine.) And, of course, even if such 13-vertex posets don't exist, this doesn't rule out the existence of the 20-vertex poset we're looking for.

I graded this problem when it appeared on a test at the US training camp. The answer is in fact yes, and I got a lot of different constructions of 67, none of which I remember exactly. There are a ton of variables you have control over in this problem, so I think it's pretty easy to stumble on one. Even silly looking identities like $67 = {4 \choose 2} + {5 \choose 2} + {6 \choose 2} + {9 \choose 2}$ or $67 = 8 + 9 + 11 + 12 + 13 + 14$ can lead to constructions. One thing to note: you can get 30 linear extensions by taking 5 elements $a,b,c,d,e$ and forcing $a \leq b$, $c \leq d$. This is basically the letter arrangement problem on $AABBC$ which has $5!/(2!)^2 = 30$ solutions. So actually you have 15 elements to work with in getting 67.

For the sake of completeness, here's an explicit construction I came up with. First, set requirements for singers $1\ldots 5$ so they have 30 possible arrangements. This is pretty easy: Make $\{1,2,3\}$ indifferent, have $4$ require to play after $\{1,2,3\}$, and make $5$ indifferent as well. Obviously $\{1,2,3,4\}$ have 6 options and 5 can be inserted in any one of 5 spots which makes 30. Now require singer $6$ to come after both $4$ and $5$ which makes all of $\{1,2,3,4,5\}$ confined to appear before $6$. Make $7$ follow $6$, $8$ follow $7$ and so on through singer $16$. Finally make singer $17$ come anywhere after singer $13$, and singer $18$ come anywhere before singer $16$. That's it. Given the positions of $\{1,\ldots, 16\}$, obviously $17$ can be inserted in 4 places: right after $13$, $14$, $15$ or $16$. In the first three cases singer $16$ is preceded by 16 other singers ($1,\ldots ,15$ and $17$) while in the last case it is preceded by only 15 other singers. So $18$ has 17 insertion points in the first three cases and 16 in the last, yielding $17+17+17+16=67$ overall for $17, 18$ given the other signers. This realizes 2010 possible arrangements with 18 singers. The last two singers can be forced to follow everyone in a specific order and we're done. EDIT: Just wanted to add that the open-ended phrasing of the question ("can it be that...") is really nasty. It's very reasonable for a solver to spend time thinking it's impossible - I know I fell in that trap for a while...

Here is my solution. To be simple, I list out the set that each singer wishes. The proof should be easy, and note that 67 = 3*9 + 4*10. Please let me know if it is correct. Singer no.1 {empty set} Singer no.2 {1} Singer no.3 {2} Singer no.4 {3} Singer no.5 {empty} Singer no.6 {empty} Singer no.7 {4,5,6} Singer no.8 {7} Singer no.9 {8} Singer no.10 {9} Singer no.11 {10} Singer no.12 {11} Singer no.13 {12} Singer no.14 {13,19} Singer no.15 {14} Singer no.16 {15} Singer no.17 {16} Singer no.18 {17} Singer no.19 {7} Singer no.20 {10}

A very simple construction with $14$ signers I found after flailing around for about four hours: We can consider $11$ signers $A_1 > \dots > A_6$ and $B_1 > \dots > B_5$ satisfying $B_1 > A_6$ (excludes $1$ possibility) and $B_5 < A_5$ (excludes $\textstyle\binom95$). Then $335 = \textstyle\binom{11}{5} - \textstyle\binom{9}{5} - \textstyle\binom{5}{5}$. Finally, note that $2010 = 3! \cdot 335$.

orl wrote: In a concert, 20 singers will perform. For each singer, there is a (possibly empty) set of other singers such that he wishes to perform later than all the singers from that set. Can it happen that there are exactly 2010 orders of the singers such that all their wishes are satisfied? Proposed by Gerhard Wöginger, Austria Yes, it is possible. Call a number $a$ to be $b$-good, if it is possible to find $b$ singers whose mutual preferences account for exactly $a$ possible orders. Claim. Suppose $m$ is $k$-good and $n$ is $\ell$-good. Then $mn$ is $(k+\ell)$-good. (Proof) Put the $k$ singers in group $A$ and $\ell$ singers in group $B$. Assume no singer in $A$ sings before any singer in $B$. Then $A \cup B$ equipped with this ordering is the desired $(k+\ell)$-set. $\blacksquare$ Claim. $30$ is $5$-good. (Proof) Pick $a,b,c,d,e$ with $a <b, c <d$ as the lot of singers. Clearly, $5!/(2!)^2=30$ valid permutations exist. $\blacksquare$ Claim. $67$ is $15$-good. (Proof) Pick singers $A_1>A_2>A_3>A_4>B_1>B_2>B_3>B_4$ and $X, Y, Z$ with $X>Y>Z$ and $A_4>Z>B_4$, $A_1>X>Y>B_2$. We claim that these singers have exactly $67$ possible orders. If $A_4>Z>B_1$ then $\binom{5}{2}$ ways to pick $X, Y$; If $B_1>Z>B_2$ then $\binom{6}{2}$ ways to pick $X, Y$; If $B_2>Z$, then $2$ ways to pick $Z$ and $\binom{7}{2}=21$ ways to pick $X, Y$. In total, we have $10+15+2 \cdot 21=67$ ways. $\blacksquare$ Apply the initial claim to conclude that $2010$ orders are attainable for some set of $20$ singers. $\blacksquare$

Here's my construction for $67$: \[\begin{array}{c|cccccccccccc} \boxed{x_6} & & & & & & & & & & & & \\ x_7 & & & & & & & & & & & & \\ x_8 & &x_7 & & & & & & & & & & \\\hline \boxed{x_9} & &x_7 &x_8& & & & & & & & & \\ x_{10} &x_6 &x_7 &x_8& & & & & & & & & \\ x_{11} &x_6 &x_7 &x_8& & x_{10}& & & & & & & \\ x_{12} &x_6 &x_7 &x_8& & x_{10}&x_{11} & & & & & & \\ x_{13} &x_6 &x_7 &x_8& & x_{10}&x_{11} &x_{12} & & & & & \\\hline \boxed{x_{14}} &x_6 &x_7 &x_8& & x_{10}&x_{11} &x_{12} &x_{13} & & & & \\ x_{15} &x_6 &x_7 &x_8&x_9 & x_{10}&x_{11} &x_{12} &x_{13} & & & & \\ x_{16} &x_6 &x_7 &x_8&x_9 & x_{10}&x_{11} &x_{12} &x_{13} & &x_{15} & & \\ x_{17} &x_6 &x_7 &x_8&x_9 & x_{10}&x_{11} &x_{12} &x_{13} & &x_{15} &x_{16} & \\ \end{array}\](The singer $x_j$ is in a row that has $x_i$ as its leftmost entry if and only if $x_i > x_j$.) Basically, we consider the three separate arrangements $\{x_6, x_7, x_8 \}, \{x_9 ,x_{10} ,x_{11}, x_{12}, x_{13} \}, \{x_{14}, x_{15}, x_{16}, x_{17}\}$, satisfying $x_7 < x_8$, $x_{10} < x_{11} < x_{12} < x_{13}$, $x_{15} < x_{16} < x_{17}$. There are respectively $3,5,4$ ways to permute the separate arrangements. Now we can put these three arrangements together, but delete the constraints $x_6 < x_9$ and $x_9 < x_{14}$. This works because $3 \cdot 5 \cdot 4 + 3 + 4 = 67$.

The answer is yes. Interpret the problem as a directed graph with an edge $u \to v$ iff singer $v$ wishes to perform later than $u$. Consider the following graph. [asy][asy] unitsize(0.85cm); dot((12, -1), blue); dot((15, 1), blue); for (int i = 0; i <= 15; ++i) dot((i, 0), (i < 6) ? red : black); dot((15, -1), green); dot((15, -2), green); draw((0, 0)--(1, 0), black, EndArrow(TeXHead), Margin(1.5, 1.5)); draw((1, 0)--(2, 0), black, EndArrow(TeXHead), Margin(1.5, 1.5)); draw((2, 0)--(3, 0), black, EndArrow(TeXHead), Margin(1.5, 1.5)); draw((3, 0)..(4.5, -1)..(6, 0), black, EndArrow(TeXHead), Margin(1.5, 1.5)); draw((4, 0)..(5, 1)..(6, 0), black, EndArrow(TeXHead), Margin(1.5, 1.5)); draw((5, 0)..(5.5, 0.3)..(6, 0), black, EndArrow(TeXHead), Margin(1.5, 1.5)); for (int i = 6; i < 15; ++i) draw((i, 0)--(i + 1, 0), black, EndArrow(TeXHead), Margin(1.5, 1.5)); draw((12, 0)--(12, -1), black, EndArrow(TeXHead), Margin(1.5, 1.5)); draw((15, 1)--(15, 0), black, EndArrow(TeXHead), Margin(1.5, 1.5)); draw((15, 0)--(15, -1), black, EndArrow(TeXHead), Margin(1.5, 1.5)); draw((15, -1)--(15, -2), black, EndArrow(TeXHead), Margin(1.5, 1.5)); [/asy][/asy]It is easy to see that we can arrange the red singers in $\frac{6!}{4!} = 30$ ways. The green singers don't matter; we can simply tack them on at the end. It suffices to place the blue singers into the red and black line, which contains $16$ singers. The bottom blue singer has $4$ spaces to go: three space before the last black singer, in which the top blue singer can go in $17$ spaces between singers, and one of them after all black singers, in which the top blue singer can go in only $16$ spaces. Hence there are \[ 30 \cdot (3 \cdot 17 + 16) = 30 \cdot 67 = 2010,\]arrangements, as desired. $\blacksquare$

Solved with rowechen The answer is yes. Construction. 1: none 2: 1 3: 2 4: 3 5: none 6: 1-5 7: 6 8: 7 9: 8 10: 1-5 11: 1-5 12: 1-11 13: 12 14: 13 15: 14 16: 15 17: 20, 16 18: 17 19: 18 20: 3 We now show that this works. Excluding $20$, the groups do not speak to each other, and so obviously the second group gives the factor of $6 \cdot 5=30$. The third group is fixed. Now we do casework on where $5$ is in the first group (excluding 20): -$\text{ }\text{ }\text{ }\text{ }$if it is in the 4th or 5th slots, then after adding $20$, $20$ can be in the 4th to 17th slots, so $14$ choices here. -$\text{ }\text{ }\text{ }\text{ }$if it is in the 1st, 2nd, or 3rd slots, then similarly after adding $20$, $20$ can be in the 5th to 17th slots, so $13$ choices here. Since $2 \cdot 14+3 \cdot 13 = 67$, and $67 \cdot 30=2010$, we're done.

I hate this problem It suffices to find $15$ singers with preferences so that there are $67$ ways to order them; we can simply include some extra five singers $S_1, S_2, \ldots, S_5$ so that each must come after the other fifteen, and that $S_1$ comes before $S_2$ while $S_3$ comes before $S_4$, of which there are $5!/(2!)^2 = 30$ orderings. Say we have have some $13$ singers that must be in the order $s_1 \rightarrow s_2 \rightarrow \ldots \rightarrow s_{13}$ and then two additional singers $X$ and $Y$ for which\[s_3 \rightarrow X \rightarrow s_{12} \text{ and } s_1 \rightarrow Y \rightarrow s_7.\]We examine a few cases: If $X$ is inserted between $s_3$ and $s_7$, of which there are $4$ spaces, then $Y$ now has $8$ spaces to be inserted (original $7$ and the extra one created by inserting $X$), for a total of $4 \times 8 = 32$ arrangements. If $X$ is inserted after $s_7$ but necessarily before $s_{12}$, of which there are $5$ spaces, then $7$ must be inserted before $s_7$, of which there are $7$ spaces, for a total of $5 \times 7 = 35$ arrangements. Indeed, this is a total of $67$ arrangements for $15$ singers, and we are done! $\blacksquare$

Let the singers be labeled $1$, $2$, $\ldots$, $20$. Then, suppose that every singer between $1$ and $15$ goes before any singer between $16$ and $20$, and the singers between $16$ and $20$ can go in any order except $16$ must go before $17$ and $18$ must go before $19$. Then, there are $\frac{5!}4=30$ ways to arrange the last five singers. Therefore, it suffices to find an arrangement of $15$ singers such that there are exactly $67$ possible ways. Suppose that out of the first seven singers, $1$, $2$, $3$, $4$, $5$, and $6$ must be in order, and $7$ must go before singers $8$ through $15$. Then, the possible orders are $1234567$, $1234576$, $1234756$, $1237456$, $1273456$, $1723456$, and $7123456$. Then, let singers $8$ through $12$ go in order after the first seven singers, and suppose that the only restriction on singer $13$ is that he must go after singer $3$. Then, there are a total of $10+10+10+10+9+9+9=67$ total possibilities. Then, let singers $14$ and $15$ go after every other singer. Then, there are exactly $67$ possible orders for these $15$ singers, so there are a total of $67\cdot30=2010$ possible orders, so it is possible.

Set requirements for the first $5$ singers such that they have exactly $30$ ways to order themselves; we can achieve this by forcing them all to be the first five to perform, and furthermore, having the only requirement among them being that the fourth singer must perform after the first, second, and third singers. Now, we need to give a construction for $67$ ways. To do this, we only use $11$ out of the last $15$ singers; we can ignore the other four by fixing them to be, say, the last four to perform. Now, take $8$ of these $11$ singers, and fix their order. Label them $1$ to $8$, left to right. Let the last three singers be $9$, $10$, and $11$. Then, let $9$ perform after $6$, let $10$ perform after $1$ and before $9$, and let $11$ perform after $4$ and $10$ and before $9$. It's easy to check that this works (I'm lazy). $\blacksquare$

why -_- Denote the singers by $a_1,a_2,\dots,a_n$ and let $S_i$ be the set of singers that $a_i$ has requested to sing before. Let $S_1=S_2=S_3=S_5=\{\},S_4=\{a_1,a_2,a_3\}.$ We see that there are $30$ ways to order these singers so that their requests are fulfilled. Force the order of $a_{6}$ through $a_{15}$ and then let $a_{16}$ have to go after $a_{11}$ and $a_{13}$ have to go after $a_{17}.$ To construct such a order, first take where $a_{16}$ is. If it is right after $a_{11}$ or $a_{12}$ then there will be $14$ open slots, before $1,2,\dots,13,$ and $16$ namely, for $a_{17}.$ If $a_{16}$ is right after $a_{13},a_{14},$ or $a_{15}$ then there will be $13$ open slots for $a_{17}.$ Thus, there are $14+14+13+13+13=67$ ways to do this. For the remaining three singers, I'm sure their singing is great but for the purposes of this problem they don't matter. They can go last in a certain order and we're done.

Order $5$ of the singers to be the first $5$ singers, $a_1, \dots , a_5$ and make $a_1$ have to go after $a_2$, $a_3$, and $a_4$. This gives $30$ ways. Now we need to construct $67$ orders of the last $15$ singers. Consider $11$ of the singers, $b_1, \dots , b_11$ and force them into that order. Now consider two other singers $X$ and $Y$. Make $X$ have to go in front of $b_9$ and $Y$ have to go behind $b_5$. We have that there are $9 \cdot 7 - 4$ ways to place $X$ and $Y$ if they aren't adjacent and $2 \cdot 4$ ways to place them if they are adjacent. This gives $67$ ways to order these $13$ singers and we can put the other $2$ at the very back and this gives $30 \cdot 67 = 2010$ ways to order the singers so we are done.

Very funny (and hard!) problem. This solution uses the fact that $67=\binom{9}{2}-1+4(8)$. Yeah, I know. We view the problem as asking for a DAG on $20$ vertices which can be topologically sorted in exactly $2010$ ways. First, we construct a DAG on $13$ vertices which can be topologically sorted in exactly $67$ ways. Number the vertices $1$ through $13$ and create the following edges: $$i \to i-1~\text{for } 4 \leq i \leq 13,$$$$2 \to 1, 2 \to 3, 10 \to 1.$$Here is a picture: [asy][asy] pair[] p = {(1, 0), (1, -1), (0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (1, 7), (2, 7), (3, 7)}; for (pair pt : p) { dot(pt); } draw(p[1]--p[0], linewidth(0.5), Arrow); draw(p[1]--p[2], linewidth(0.5), Arrow); draw(p[9]--p[0], linewidth(0.5), Arrow); for (int i = 12; i >= 3; --i) { draw(p[i]--p[i-1], linewidth(0.5), Arrow); } [/asy][/asy] Note the number of topological sorts of some DAG is the sum of the number of topological sorts across all DAGs obtained by deleting a vertex of indegree zero in the original graph. Using this, we can easily find that if we take the vertices $1$ through $i$ for $i \leq 9$, then there are $\binom{i}{2}-1$ ways to topologically sort the resulting graph. Then for $9 \leq i \leq 12$, adding one to $i$ generates $8$ additional topological sorts, for a total of $67$ as desired. Next we construct a DAG on $5$ vertices which can be topologically sorted in exactly $30$ ways. This is simple: number the vertices $14$ through $18$, and use edges $14 \to 15, 16, 17$. We now "merge" everything together to create a DAG on $20$ vertices that can be topologically sorted in $2010$ ways as desired. Number vertices $1$ through $20$. Draw the provided $13$-vertex DAG on vertices $1$ to $13$. Then draw the provided $5$-vertex DAG on vertices $14$ to $18$, and for all $1 \leq i \leq 13$ and $14 \leq j \leq 18$, draw $j \to i$. Finally, just draw $19, 20 \to i$ for all $i \leq 18$, and $19 \to 20$. Then any topological sort must start with $19, 20$, followed by an ordering of $14$ through $18$ (which we have $30$ ways to do), followed by an ordering of $1$ through $13$ (which we have $67$ ways to do, independently of anything previous). Then this DAG has exactly $2010$ topological orderings, so we're done. $\blacksquare$ Remark: The motivation for believing the answer is "yes" is because it seems very difficult to somehow prove the answer is no. Initially one might think that if we have $n$ vertices, the number of topological sorts must divide $n!$, which would imply the desired result since $67$ is prime and greater than $20$. This seems to be true for quite a few small examples, but eventually I stumbled upon the $i=4$ version of the $13$-vertex DAG, which has $5$ orderings, so this claim isn't true. Indeed if we just naively extend this construction (so not including the $10 \to 1$) we get quite a few "strange" numbers, so it seems really hard to get a grasp on what we cannot do. There is also a DAG on $6$ vertices that can be topologically sorted in exactly $19$ ways, which indicates that we probably shouldn't be "scared" of "big" primes.

We claim that the answer is positive. Assign numbers $1,2,\dots ,20$ to singers, and divide them onto three blocks: $1-5,$ $6-18$ and $19-20.$ It's easy to make the situation, when blocks have to go consequently, so it's suffice to show individual order for every block. Let $x\rightarrow y$ means that $y$ wants to perforn after $x.$ 1st block. Set $1\rightarrow 2,3\rightarrow 4.$ Then there are $6$ ways to order $1,2,3,4$ and $5$ ways to place $5,$ so there are $30$ orders at all. 2nd block. Set $6\rightarrow 7\rightarrow 8\rightarrow \dots \rightarrow 16$ and $10\rightarrow 17,18\rightarrow 14$. Then there are $2!\cdot 4$ ways of order, if $17,18$ are adjacent, and $5\cdot 3+5\cdot 4+3\cdot 4+4\cdot 3=59$ other, so there are $67$ orders at all. 3rd block. Set $19\rightarrow 20.$ Then there is exactly one order. Finally, there are exactly $30\cdot 67\cdot 1=2010$ orders as desired.

Yes. Let the singers be $A,B,C,D,\dots,T.$ Let $X>Y$ denote $X$ wanting to perform later than $Y$. Let $A>B>C>D$, $A>E>F>G>H>I>J>K>L>M>N>O>P$, $B>I$, $A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P > Q,R,S > T$. We will show that this construction works. First, since $Q,R,S$ are essentially independent, they have $6$ ways to rearrange themselves. $T$ has to perform first, so there's only $1$ way there. Finally, consider the number of singers in the chain $EFGHIJKLMNOP$ that are below $B$. Since $I$ must be below $B$, the number can be $12,11,10,9,8$. If something goes above $B$, it is already sorted, so there is one way to sort the things above $B$. However, below $B$ and above $Q$, if there are $x$ singers left in the $EFGHIJKLMNOP$ chain, then they can rearrange themselves in $\binom{x+2}{2}$ ways because of the $C$ and $D$. This means that there are a total of $$\binom{10}{2}+\binom{11}{2}+\binom{12}{2}+\binom{13}{2}+\binom{14}{2}=\binom{15}{3}-\binom{10}{3}=455-120=335$$ways to rearrange things above $Q$ and below $B$. Therefore, the total number of ways to do this is $6\cdot1\cdot335=2010$, as wanted.

Beautiful, but horrendous. First, we construct 30, and we can do so by using 5 singers and making one be in front of any 3 of the others. This works, since we can order them in $3!+ 4!=30$ ways. To construct $67$ with 13 singers, fix the relative order of the first 11. One of the other singers goes after the 9th singer, while the other goes behind the 5th singer. This works by manually checking. The remaining two singers can be forced at the back in one way.

Yes. Consider five singers $A$, $B$, $C$, $D$, $E$ and order $A>B$, $C>D$. There are thirty ways to order $A,B,C,D,E$ and throw them as the last $5$ singers. It now suffices to find 15 singers such that there are $67$ ways to order them. Claim: $10+12+15+15+15=67$ Proof. Omitted. $\blacksquare$ Fix $8$ singers $A_1< A_2<\dots<A_8$. Then, let $A_1<A_9<A_6$ and $B_1<A_3,A_9$ and $B_2>A_4,A_9$. Then, if $A_9$ is directly before $3,4,5$ there are $3\cdot5$ choices for $B_1,B_2$. If $A_9$ is before $A_2$ then there are $2\cdot 5$ ways to order $B_1,B_2$ and $A_9$ before $A_6$ there are $3\cdot 4$ ways to order them. The claim finishes.

Yes, it is possible. First of all, we order the first five singers in $30$ ways by simply restricting $1 < 2$ and $3 < 4$. To ensure $1$, $2$, $3$, $4$ and $5$ go in the first 5 spots, just let $\{ 1, 2, 3, 4, 5 \}$ be a subset for all the other sets of the other singers. Thus, we just need to construct something for 67. The motivation for my approach is a sliding window: Fix the ordering of all the singers except for $2$ (so say we have $D_1 < D_2 < \dots < D_k$). Let's say we order $B > A$, but there's an additional restriction $B > D_i$ to "cap" the possibilities for $B$, and then slide singer $A$ to see how many spots singer $B$ can be placed. But also "cap" the possibilities of where singer $A$ can slide. So the sum of possibilities would look something like \[ k + k + \dots + k + (k-1) + (k-2) = 67 \]Or equivalently, $(a+3)k - 3 = 67$ for some integer $a$. This implies $k = 14$ or $k = 10$, which isn't possible with just 15 singers. So then, we consider \[ k + k + \dots + k + (k-1) + (k-2) + (k-3) + (k-4) = 67 \]which is equivalent to $(a+5)k - 10 = 67$ for some integer $a$. Then $k = 11$ works, as we would have \[ 11 + 11 + 11 + 10 + 9 + 8 + 7 = 67\] The corresponding construction would be to fix $12$ singers $D_1 < D_2 < \dots < D_{12}$. (Also, ensure that $D_{13}$ must go last, which is easy). Then we just make sure that $A < D_7$, and then $B > A$ but $B > D_2$. Then when $A$ is right before $D_i$ for $i = 1, 2, 3$ then $B$ has $11$ spots to go; right before $D_i$ for $3 \leq i \leq 13$. But then when $A$ is right before $D_i$ for $i = 4, 5, 6, 7$, the spots for $B_i$ decreases by one each time. Thus, the total possibilities is $11 + 11 + 11 + 10 + 9 + 8 + 7 = 67$, as desired. $\blacksquare$

We start by killing $8$ of the singers to force the rest of the singers to obey our ordering. Define the singers $A_1 < A_2 < A_3, B_1 < B_2 < \{B_3, B_4, B_5, B_6, B_7\}\}$. We define $B_3 < B_4, B_5 < B_6$. This gives us $\frac{5!}{4} = 30$ ways to sort $B_i$. Afterwards, we also let $A_3 < B_2, A_1 < B_1$. This forces three intersections of the form $A_2A_3B_1B_2, A_2B_1A_3B_2, B_1A_2A_3B_2$. Now, we create $C_1 < B_1, C_2 > A_3$, $C_1 < C_2$. By the intersections, this gives us $4 \cdot 8 + 3 \cdot 7 + 2 \cdot 7 = 67$ ways to place $C_1, C_2$. The result follows with the rest of $12$ singers. I think this is not minimal (asdf334's construction should give $11$ singers).

I'm wondering if someone could help me make sure I'm not messing something up. The official shortlist seems to claim the following 10-element poset achieves $2010$ (see attachment for picture; it's on page 23 of https://www.imo-official.org/problems/IMO2010SL.pdf). However, I tried to check this in Sage and got 2012 as the count instead. elms = ["a1", "a2", "a3", "a4", "a5", "a6", "b1", "b2", "b3", "b4"] rels = [ ["a1", "a2"], ["a2", "a3"], ["a3", "a4"], ["a4", "a5"], ["a1", "a6"], ["b1", "b2"], ["b2", "b3"], ["b2", "b4"], ["a1", "b3"], ["a1", "b4"], ["b1", "a5"], ] P = Poset((elms, rels)) print(P.linear_extensions().cardinality()) Did I mistake somewhere? It's unfortunately hard to debug "the proofs are left to the reader"

v_Enhance wrote: I'm wondering if someone could help me make sure I'm not messing something up. The official shortlist seems to claim the following 10-element poset achieves $2010$ (see attachment for picture; it's on page 23 of https://www.imo-official.org/problems/IMO2010SL.pdf). However, I tried to check this in Sage and got 2012 as the count instead. elms = ["a1", "a2", "a3", "a4", "a5", "a6", "b1", "b2", "b3", "b4"] rels = [ ["a1", "a2"], ["a2", "a3"], ["a3", "a4"], ["a4", "a5"], ["a1", "a6"], ["b1", "b2"], ["b2", "b3"], ["b2", "b4"], ["a1", "b3"], ["a1", "b4"], ["b1", "a5"], ] P = Poset((elms, rels)) print(P.linear_extensions().cardinality()) Did I mistake somewhere? It's unfortunately hard to debug "the proofs are left to the reader" Python also yields 2012 for this configuration(don't judge my bad python) import itertoolsdef check(a): if a[0]<a[1]<a[2]<a[3]<a[4] and a[0]<a[5] and a[6]<a[7]<a[8] and a[6]<a[7]<a[9] and a[0]<a[8] and a[0]<a[9] and a[6]<a[4]: return 1 return 0n=[1,2,3,4,5,6,7,8,9,10]count=0total=list(itertools.permutations(n))for k in range (3628800): if check(total[k])==1: count+=1print(count)import itertools def check(a): if a[0]<a[1]<a[2]<a[3]<a[4] and a[0]<a[5] and a[6]<a[7]<a[8] and a[6]<a[7]<a[9] and a[0]<a[8] and a[0]<a[9] and a[6]<a[4]: return 1 return 0 n=[1,2,3,4,5,6,7,8,9,10] count=0 total=list(itertools.permutations(n)) for k in range (3628800): if check(total[k])==1: count+=1 print(count)RunResetPop Out / Edit: AoPS doesn't support itertools

Could someone check if this is correct? Let the $20$ singers be represented by $A_1, A_2,\dots,A_5$, $B_1, B_2, \dots B_{10}$, $C_1, C_2, C_3$, $D$, $E$. For two singers $X$ and $Y$, let $X<Y$ denote that $Y$ wishes to perform after $X$. Here is the construction. We let $C_1<C_2<C_3$, and for all other singers $X$, $X<C_1$. Then for any $1\leq i \leq 5$ and $1\leq j \leq 10$, we have $A_i < B_j$. For $1\leq i \leq 9$, we have $B_i<B_{i+1}$. Then for any $1\leq i \leq 5$ we have $A_i < D$ and $E< B_1$. We also have $A_1< A_2$ and $A_3 < A_4$. Now we show that there are exactly $2010$ ways to satisfy all of the singers wishes. $C_1$, $C_2$, and $C_3$ are fixed as the last three singers, in that order. The $B$ singers are forced to go in order of number, but not necessarily consecutively. The $A$ singers must all come before all of the $B$ singers. The restrictions $A_1<A_2$ and $A_3 < A_4$ mean that there are $\frac12\cdot \frac12 \cdot 5!=30$ ways to determine the relative positions of the $A$ singers. Then we can calculate the number of ways to insert $D$ and $E$ into the sequence. If $E$ is before $D$, then that means that $E$ can be positioned anywhere among the $A$ singers, while $B$ can be positioned anywhere among the $B$ singers. This gives $(5+1)(10+1)=66$ ways. If $E$ is after $D$, then there is only one arrangement: the $A$ singers, $D$, $E$, then the $B$ singers. Thus, there are $30$ ways to order the $A$ singers and $67$ ways to insert $D$ and $E$ afterward, for a total of $30\cdot 67=2010$ orderings.

Let each singer be a number $1$ through $20.$ If we label a 20 vertice graph with these numbers, where an arrow is drawn from one singer to another if the latter singer wants to go after the prior singer, the problem is asking for a construction with $2010$ topological orders. Note that $67=\binom{13}{2}-\binom{5}{2}-1,$ so there is a construction for $67$ in $13$ vertices. Now, as $30=6*5$ there is also a construction for $30$ in $6$ singers. We have one singer left that is simply always going to be the last$.\blacksquare$

We may form $30$ by considering $1\leftarrow 2\quad 3\leftarrow 4\quad 5$. Then, for $67$, consider singers $1,2,\dots,11$, each following one another in a chain, and $a$ and $b$ such that $a\leftarrow 9$ and $5\leftarrow b$. Here, $a$ has $9$ possibilities, while $b$ has $7$ possibilities, and an extra $4$ when considering if either $a$ or $b$ goes first when they are both directly after the same numbered singer. This uses a total of $18$ singers.

bad formatting because i copied my solution from mathdash the answer is yes. let the singers be A_1 .. A_20. let A_16 .. A_20 want to be behind A_1 thru A_15, and let A_19 want to be behind A_16, A_17, A_18. then the number of ways to arrange A_16 to A_20 is 120/4 = 30, and all of them must be behind A_1 ... A_15, so it remains to show there is a way to ge 67 arrangements of A_1 .. A_15. ok, first off let A_4 .. A_13 want to be behind A_1 .. A_3, with A_3 wanting to be behind A_2, so we can arrange the A_1 , A_2 , A_3 in three possible spots, as they all must be want to be at the top, and A_1 can go in any of the three spots and the rest is fixed. now let A_14 want to be behind A_1, A_15 want to be behind A_14, A_9 want to be behind A_15, A_6 want to be behind A_14, and let A_{i + 1} want to be behind A_i for i between 3 and 12. now A_4 thru A_13 is fixed. we do casework on the location of A_1. if A_1 is in the first position amongs A_1, A_2, A_3, we can have A_14 is anywhere from in front of the second of A_1.. A_3, to all the way in front of A_6. in the first of these cases, we see A_15 can be anywhere from in fornt of the second of A_1 .. A_3, all the way to in front of A_9, which is 8 different places. if A_14 goes up one more spot, we lose one option, all the way until A_6, where we have 4 options. repeating this logic for the other cases gives the total sum as 8 + 7 + 6 + 5 + 4 + 7 + 6 + 5 + 4 + 6 + 5 + 4 = 30 + 22 + 15 = 67, hence done.

The answer is yes. Here is a solution with $18$ singers, using the fact that \[2010 = \binom 52 \cdot \left(\binom{12}{2} + \binom{11}{2} + \binom{10}{2} + \binom 92 - 1\right).\][asy][asy] size(16cm); dot((0,0)); dot((1,0)); dot((2,0)); dot((1,-1)); dot((2,-1)); for (int i = 3; i <= 12; ++i) { dot((i, 0)); } dot((3,-1)); dot((4,-1)); dot((5,-1)); for (int i = 0; i < 12; ++i) { draw((i,0)--(i + 1,0),black,EndArrow(TeXHead),Margin(1.5,1.5)); } draw((1,-1)--(2,-1),black,EndArrow(TeXHead),Margin(1.5,1.5)); draw((3,-1)--(4,-1),black,EndArrow(TeXHead),Margin(1.5,1.5)); draw((4,-1)--(5,-1),black,EndArrow(TeXHead),Margin(1.5,1.5)); draw((2,-1)--(3,-1),black,EndArrow(TeXHead),Margin(1.5,1.5)); draw((2,-1)--(3,0),black,EndArrow(TeXHead),Margin(1.5,1.5)); draw((2,0)--(3,-1),black,EndArrow(TeXHead),Margin(1.5,1.5)); draw((3,0)--(5,-1),black,EndArrow(TeXHead),Margin(1.5,1.5)); draw((3,-1)--(6,0),black,EndArrow(TeXHead),Margin(1.5,1.5)); draw((2.5,1.75)--(2.5,-1.75),black+dashed); label(scale(2)*"$10$",(1,1)); label(scale(2)*"$201$",(7.5,1)); [/asy][/asy]

The answer is yes. This solution takes advantage of the fact that ${10 \choose 2} + {11 \choose 2} + \cdots + {14 \choose 2} = 335 = 5 \cdot 67$. Let $S_i$ denote the set of singers that singer $i$ prefers to appear after. Consider the construction: \begin{align*} S_1 &= \emptyset \\ S_2 &= \{1\} \\ \vdots & \vdots \\ S_6 &= \{1, 2, 3, 4, 5\} \\ S_7 &= \{1, 2, 3, 4, 5\} \\ S_8 &= \{7\} \\ S_9 &= \{8\} \\ S_{10} &= \{9\} \\ S_{11} &= \{6\} \\ S_{12} &= \{11\} \\ S_{13} &= \{1, 2, 3, \dots, 12\} \\ S_{14} &= \{13\} \\ \vdots & \vdots \\ S_{18} &= \{17\} \\ S_{19} &= \{17\} \\ S_{20} &= \{17\}. \end{align*}Notice that in this construction, the numbers $1, 2, 3, 4, 5$ must appear first in that order. Now to decipher what is going on, first notice that singers $\{18, 19, 20\}$ must appear at the end of the chain and are indistinguishable otherwise, so we assume they appear in this order, dropping a factor of $6$. The key is to consider the side chain consisting of $\{7, 8, 9, 10\}$. We have five cases here: Singer $6$ appears in position $6$. Then the singers $7, 8, 9, 10, 13, \dots, 20$ must appear in this order and singer $12$ must appear before singer $11$. There are ${14 \choose 2}$ ways to choose positions for singers $11$ and $12$, and the positions of the remaining singers are then fixed. Singer $6$ appears in position $7$. The only singer that can appear in position $6$ is singer $7$, and the remaining $13$ positions work out similarly, with ${13 \choose 2}$ ways to pick positions for singers $11$ and $12$ and the positions of the remaining singers being fixed. Singer $6$ appears in position $8$. Once again, only singer $7$ can appear in position $6$, and only singer $8$ can appear in position $7$. By the same logic, we have ${12 \choose 2}$ cases. If singer $6$ appears in position $9$ or $10$, we have ${11 \choose 2}$ and ${10 \choose 2}$ cases respectively. Singer $6$ cannot appear in position $11$ or later, as all of singers $11$ through $20$ must appear after singer $6$. Thus, multiplying back by the factor of $6$, there are $6 \cdot 335 = 2010$ ways to pick the order of the singers, as needed. Remark: Pretty hard for C1, but awesome problem.