European Mathematical Cup

We will for simplicity and clarity of presentation use some basic graph theoretic terms, this is in no way essential.
We represent the situation by a directed graph (abbr. digraph) $G(V, E)$ where each vertex $v \in V(G)$ represents a mathematician and each edge $e \in E(G)$ represents an admiration relation. Given $v \in V(G)$ we define out-degree of $v$ denoted $o(v)$ as the number of edges starting in $v$ (so the number of mathematicians $v$ admires) and in-degree $i(v)$ as the number of edges ending in $v$ (so the number of mathematicians who admire $v$). Given $X \subseteq V$ by $G(X)$ we denote the induced subgraph (a graph with vertex set $X$ and edges inherited from $G$). We say that a digraph is a $k$-digraph if for every $v \in V(G)$ we have $i(v) \ge k$ or $o(v) \ge k$.
So the question can be reformulated as: Given $G$ is a $3k+1$-digraph we can split its vertices into 2 vertex disjoint classes such that each induced subgraph on class is a $k$-digraph.
We call a subset $X$ of vertices of $G$ $k$-tight if for any $Y \subseteq X$ we have a vertex $v \in Y$ such that $i_{\{G(Y)\}}(v) \le k$ and $o_{\{G(Y)\}}(v) \le k$. A partition of $V$, $(A_1, A_2)$ is feasible if $A_1$ is $k$-tight and $A_2$ is $k$-tight.
We first assume there are no feasible partitions.
In this case consider a minimal size subset $A_1 \subseteq V(G)$ subject to $G(A_1)$ being a $k$-digraph, we define $A_2 = V(G) - A_1$. Given a subset $X \subset A_1$, $G(X)$ is not a $k$-digraph so there is a vertex $v \in X$ such that $o_{\{G(X)\}}(v) < k$ and $i_{\{G(X)\}}(v) < k$ which shows that any proper subset of $A_1$ satisfies the condition of $k$-tightness. For the case of $X = A_1$ by removing any vertex $v \in A_1$ the graph $G' = G(A_1 - \{v\})$, by minimality assumption on $A_1$, must contain a vertex $w$ such that $o_G(w) < k$ and $i_G(w) < k$ so as there is only one extra vertex in $G(A_1)$, namely $v$ $o_{\{G(A_1)\}}(w) \le k$, $i_{\{G(A_1)\}}(w) \le k$. In particular this shows $A_1$ is $k$-tight.
This implies $A_2$ is not $k$-tight by our assumption so there exists an $A_2' \subseteq A_2$ such that $A_2'$ is a $k+1$-digraph. Now applying the following proposition to extend the pair $(A_1, A_2')$ to a full partition which satisfies the condition of the problem.
Given disjoint subsets $A, B \subseteq V(G)$ we say $(A, B)$ is a solution pair if both $G(A)$ and $G(B)$ are $k$-digraphs.
Proposition. If a $2k+1$ digraph $G$ admits a solution pair it admits a partition with both induced graphs of both classes being $k$-digraphs.
Proof. Take a maximal solution pair $(A, B)$, the condition in the lemma guaranteeing it exists. Let $C = V(G) - (A \cup B)$, if $C$ is empty we are done so assume $|C| > 0$. By our assumption $(A, B \cup C)$ is not a solution pair so there is some $x \in C$ such that $o_{\{G(B \cup C)\}}(x), i_{\{G(B \cup C)\}}(x) < k$ so as $G$ is $2k+1$ digraph $i_G(x) \ge 2k+1$ or $o_G(x) \ge 2k+1$ so either $o_{\{G(A \cup \{x\})\}}(x) > k+1$ or $i_{\{G(A \cup \{x\})\}}(x) > k+1$ so in particular $(A \cup \{x\}, B)$ is a solution pair contradicting maximality and completing our argument.
Hence we are left with the case in which we have at least one feasible partition. We pick the feasible partition $(A, B)$ maximizing $w(A < B) = |E(G(A))| + |E(G(B))|$. The fact that $A$ is $k$-tight implies there is an $x$ with $o_{\{G(A)\}}(x) \le k$, $i_{\{G(A)\}}(x) \le k$ so $x$ needs to have at least $k+1$ edges in or out of $B$ so $|B| \ge k+1$ and by symmetry $|A| \ge k+1$.
We now prove that there exist an $X \subseteq A$ such that $G(X)$ is a $k$-digraph, by contradiction. Assuming the opposite we notice that for any $x \in B$, $B - \{x\}$ is still $k$-tight while $B$ being $k$-tight implies there is an $x \in B$ such that $o_{\{G(B)\}}(x) \le k$, $o_{\{G(B)\}}(x) \le k$ so for this $x$ we have $A \cup \{x\}$ is also $k$-tight. Hence, for $A' = A \cup \{x\}$ and $B' = B - \{x\}$, $(A', B')$ is a feasible partition. We considering the change in edges which moving $x$ causes we have $w(A', B') - w(A, B) \ge 3k+1 - k - k - k = 1$ as we know $i_{\{G(X)\}} \ge 3k+1$ or $o_{\{G(X)\}} \ge 3k+1$ so moving $x$ from $B$ to $A$ increases number of edges in $A$ by at least $3k+1-k$ while the choice of $x$ in $B$ means we lose at most $k+k$ edges in $B$. This is a contradiction to maximality of $(A, B)$.
Analogously we can find $Y \subseteq B$ with $G(Y)$ a $k$-digraph. Now applying the above proposition yet again we are done.