Take the graph interpretation. $\bullet$ A vertex cannot point to all other vertices. $\bullet $ Each vertex has a positive outdegree. We will induct on the number of vertices with base case $n=3$. Now assume contrary for $n$. We should be not able to throw a vertex away such that the conditions still hold. If throwing $A$ breaks up the first condition, then there must exist a vertex $B$ which points all other vertices different than $A$. Let $B$ point to $v_1,...,v_{k}$. If $A$ points a $v_i,$ then we can take the triple $\{A,B,v_i\}$. $A$ doesnot point a vertex different from $A,v_i$ thus, $A$ points to $B$ however in this case, we can take $\{A,B,v_1\}$. So this condition cannot be broken. If throwing $A$ away breaks up the second condition, then there must exist a vertex which points just $A$. Let $f(A)$ points to $A$. When we count pairs $(A,f(A)),$ there are at least $n$ (number of vertices) pairs since each vertex has an $f$. Also since an $f$ points to at most $1$ vertex, there can be at most $n$ pairs. Hence there are exactly $n$ pairs. Every vertex is in form $f$. So graph consists of seperate cycles. When we take three consecutive vertices if there is a cycle with length $\geq 3$. So the graph consists of pairs where the edges are in both directions. We can take a pair and any other vertex in this case.$\blacksquare$

What is a "clique" in this setup? I only know the concept for an undirected graph, but here we naturally have a directed graph.

Tintarn wrote: At a party, $25$ elves give each other presents. No elf gives a present to herself. Each elf gives a present to at least one other elf, but no elf gives a present to all other elves. Show that it is possible to choose a group of three elves including at least two elves who give a present to exactly one of the other two elves in the group. I would also use the graph interpretation. For convenience, we say $A_i\leftrightarrow A_j$ if and only if $A_i, A_j$ gives a present to each other and $A_i\rightarrow A_j$ if $A_i$ gives a present to $A_j$ but doesn't receive present from $A_j$. Assuming without loss of generality that there does not exist such a group satisfying the problem. Define $S_i$ as the set of all people who receive a present from $A_i$. With such assumption, these following claims hold: \begin{itemize} \item If $A_i\leftrightarrow A_j$, then $S_i\cup S_j=V$; \item If $A_i\rightarrow A_j$ then $S_j$ is a proper subset of $A_j$; \item For every $i$, $|S_i=\deg^+(A_i)$ is always not less then $2$, \end{itemize} with the last follows from proof by contradiction and the second claim. Now call $A_1$ to be the vertex with least outdegrees. From the second claim we deduce that $A_1\leftrightarrow A_\ell$ for every $A_\ell\in S_1$. Then we deduce that for each $A_m, A_n$ distinct in $S_1$ there is an arc between $A_m$ and $A_n$. Now split $V$ into two groups, which is $S_1$ and $A=V\text{ }\backslash\text{ }S_1$. Considering $(A_1, A_x, A_y)$ with $A_x\in S_1$ and $A_y\in A$, we have $A_y\in S_x$ for every choice of $x$ in $S_1$. Consider $(A_1, A_u, A_v)$ with $A_u, A_v$ both in $S_1$, we conclude that there is always an arc between two vertices in $S_1$. In particular, each $A_i\in S_1$ satisfies $A_j\rightarrow A_i$ for some $A_j\in S_1$, because if it doesn't happen then it follows that $|S_i|=|V|$. Now, choose $A_l$ to be the vertex with most outdegrees in $S_1$, then since there is some $w$ that $A_w\rightarrow A_l$, we have $|S_l|<|S_w|$, which is a contradiction. Hence the proof is done. Any corrections are welcome, if my solution is wrong then I may delete this

VicKmath7 wrote: If $D$ is non-empty, the only way the vertices from $D$ have non-zero outdegree is $C$ to be non-empty. I don't think this is correct. It could also happen that vertices from $D$ have outgoing edges to other vertices from $D$ (while $C$ is empty). Interestingly, the same flaw also appeared in the original version of the official solution to this problem... (and it is not too hard but also not entirely obvious how to fix the argument)