The statement is slightly hard to understand when posted in this forum. Please clarify it. About any two cards from the deck know which? And the players over the top card from his deck and one whose card? Please make the English slightly clearer.

I think this is the interpretation: There are some cards in a deck. For each pair of cards, there exists a winner; however, this winning relation is not transitive (like rock-paper-scissors; a card wins against some cards but loses against others). The deck is divided into two piles, the contents and orders of the cards are known to you. Each turn, one of the two cards at the top of the piles wins; you must move the two top cards to the bottom of the winning deck, but you may decide the order. Prove that you can collect all cards in a single pile. Example: Suppose that we play with cards Rock, Paper, sCissors, Lizard, Spock. At the beginning, the piles are (Paper, Lizard) and (Scissors, Spock, Rock), with topmost card at the left. PL | CSR: Scissors win, so Paper and Scissors go to the bottom of the right deck. We decide to put Paper on top of Scissors. L | SRPC: Lizard wins, so Lizard and Spock go to the bottom of the left deck. We decide to put Lizard on top of Spock. LS | RPC: Rock wins. Either order doesn't matter. S | PCLR: Paper wins. Now all cards are collected at the right pile. The question is that for any number of cards, any possible outcomes of each pair of cards, and any initial arrangement of the cards in the decks, you can always collect all cards into a pile.

mathuz wrote: Two players play a card game. They have a deck of $n$ distinct cards. About any two cards from the deck know which of them has a different (in this case, if $A$ beats $B$, and $B$ beats $C$, then it may be that $C$ beats $A$). The deck is split between players in an arbitrary manner. In each turn the players over the top card from his deck and one whose card has a card from another player takes both cards and puts them to the bottom of your deck in any order of their discretion. Prove that for any initial distribution of cards, the players can with knowing the location agree and act so that one of the players left without a card. It's mean: Card game; We have two players in the game; $n$ different cards. For any two cards $X,Y$ we have $X$ beats $Y$ $or$ $Y$ beats $X$. For some diffirent cards $a,b,c$ may be: if $a$ beats $b$, $b$ beats $c$ then $c$ beats $a$ or $a$ beats $c$ (it's mean: $c$ beats $a$ or $a$ beats $c$ is independent, it's unknown). The $n$ cards distribute between players in arbitrary order. If first player with a card beats another card of second player then first player take the two cards too.

Any Solution?

I don't normally post solutions, but I saw this during the IMO and thought it was so nice that I can't resist! My interpretation is the same as chaotic_iak's. Consider the graph G of possible deck arrangements. In other words, each vertex corresponds to an assignment of cards to players A and B, and an ordering of those cards. Draw an edge from vertex u to vertex v if it is possible to go from u to v in one turn. Call a vertex "terminal" if all cards are collected in one pile. Note that every non-terminal vertex has out-degree 2 since there are two ways to order the cards after a turn, and they are always different. Conversely, every vertex has in-degree at most 2. If player A won the last turn, then before last turn, the bottom two cards in A's deck must have been on the top of the two decks with the winning card on A's deck - this is a unique arrangement. The case where player B won the last turn is similar. The in-degree may also be less than 2 if one player has only 1 card left in their deck, but that's okay. Now, suppose the claim is false. Then consider the subgraph H of G that contains all vertices reachable from the initial vertex by making moves. Every vertex in H has out-degree 2 (since terminal vertices are assumed unreachable) and in-degree at most 2. Since sum of out-degrees equals sum of in-degrees, it follows that every vertex has in-degree exactly 2. Now consider a vertex where A's deck is as big as possible. Consider the incoming edge in G corresponding to B winning the previous turn. Then, the previous position would have had even more cards in A's deck. Thus, that vertex cannot be in H and so the vertex cannot have in-degree 2. Contradiction.

Very beautiful and hard! Worth to think for a long time.