AoPS - Problem

fwolth

25.07.2012 08:00

This problem is amazing. The following is excessively verbose for a very simple idea, but I tried to make everything rigorous. We'll term a card displaying the number of a pile as pointing to that pile. We claim that it's possible iff there doesn't exist a proper subset of the piles $S$ s.t. each card in $S$ points to a pile in $S$ (a self-contained subset). To prove necessity, notice that if we do have such an $S$, then since all $|S|k$ of the cards with numbers pointing to $S$, the complement of $S$ contains only cards that point to itself as well, so either way, pile 1 is in a self-contained subset. Then no matter how you order the cards in each pile of that subset, it's impossible to reach a card pointing to a pile outside of that subset from within the subset, so we can't flip over all the cards. To prove sufficiency, we show the more general result that if we're given $n$ piles with $a_1,a_2,\ldots, a_n$ cards to start s.t. the number $i$ appears exactly $a_i$ times and the first card is to be drawn from any given pile, the result still holds. From this point on, we assume WLOG Hamster is female. Since the "game" is predetermined, the real fun lies in the rearrangement of piles. Suppose our player lays out the piles in no particular order and lets herself flip whichever card from each pile she wants at each stage, starting from pile 1 as in the real game, and proceeding as according to normal rules. Our desired result is equivalent to her being able to flip all the cards, since once she has done this, she can go back and put the cards in each pile in the order she picked them, and if she can go back and put the cards in such an order, then she can likewise find the according sequence of picks. Notice that if she is unsuccessful and does end up running out of cards in pile $t$, then she must have picked up $t$ $a_t+1$ times unless $t$ is the pile she first picked from, so the last card picked is the index of the first pile picked from. We establish an isomorphism complete sequences of picks (complete or not) and $1,2,\ldots,n$ written around a circle s.t.: a) $t$ at exactly $a_t$ times b) The numbers directly following occurrences of $t$ around a circle are those in column $t$. Clearly, if we write a sequence of picks Hamster makes around a circle, they satisfy these conditions (note that the first pick follows the last pick, which again is the index of the first pile). Similarly, with any such sequence, we can pick a starting point and take a card with that value from any pile, then proceed according to the rules; clearly, we never run out of cards until all are chosen by a) and the successive cards according to b) can be chosen according to the rules, by construction. Notice that this gives a symmetry: any sequence of picks can be turned into a circle, which can then be turned back into a sequence starting at any point, meaning it doesn't matter what pile the starting point is. We now proceed by strong induction. When $n=1,\sum a_i=1$, then we just have the one possible sequence, which clearly works. Now suppose we have a configuration $C$ of $n$ piles with $a_1,\ldots,a_n$ cards with no self-contained subset, and assume that we can find a complete sequence of picks for any arrangement of cards according to the rules with piles and pile sizes identical to any proper subset of $C$. Pick a card from a given pile (doesn't matter by symmetry) and then keep picking at random according to constraints until it's impossible to pick any longer. If this sequence is complete, we're done. Else, partition $C$ into a configuration with the cards picked $C_1$ and a configuration with those unpicked, $C_2$, preserving the pile number of cards in both configurations. Our sequence from above then must be a complete sequence on $C_1$. But consider $C_2$. Each card valued $i$ not picked in the complete sequence on $C_1$ means that one card from column $i$ was not chosen in that sequence. Thus, the number of occurrences of $i$ in $C_2$ is equal to the number of cards in pile $i$, so by the inductive hypothesis there exists a complete sequence on $C_2$ as well. Lemma: We can "glue" together complete sequences on $C_1$ and $C_2$ to obtain a complete sequence on $C$. Proof: From the card-pile duality demonstrated from the circle isomorphism (each card value is followed by a column with that index, including the last card), if they share no values, that means they consist of disjoint sets of piles. But this violates the self-contained subset rule, contradiction. Thus, assume that $C_1$ and $C_2$ contain only at least common value, or equivalently that there's a pile $i$ they both contain cards from. But then in the construction of $C_1$, when the last value of $i$ is encountered, simply pick one of the values in that pile part of $C_2$ in the original construction. Then follow $C_2$'s cycle until the last value of $i$ encountered in $C_2$'s complete sequence is encountered. By the circle isomorphism, it's clear that this will entail all of $C_2$, since $i$ precedes that value picked in column $i$. Now pick the original value from $C_1$ in column $i$ and complete $C_1$ in the same way as before. The result follows. Therefore, by strong induction, Hamster wins unless there's a self-contained subset.

Kayak

27.04.2018 13:27

My solution is most probably wrong since it looks simple for an ELMO C7 Can anybody please check it ?

Lemma A directed multiedged graph $\mathfrak{G}$ is called shifu if it has the following properties: For each vertex $u \in V_{\mathfrak{G}}$, we have $\text{Indeegree}[u] = \text{Outdegree}[u]$ There are no edges from $u$ to itself. (Though there might be multiple edges from $u$ to $v$, where $u \neq v$. Then $\mathfrak{G}$ contains an Eulerian Circuit iff it's connectedConnected in the sense if you now treat $\mathfrak{G}$ as undirected, then you can go from any vertex to another commuting through edges ProofThis is well known. One implication is trivial - if it's not connected, then it clearly doesn't have any Eulerian Circuit. We prove the other implication, that if it's connected then it has a circuit. We proceed by induction on the number of edges, base case $|E_{\mathfrak{G}}| = 2$ is trivial. Now pick any vertex $u \in \mathfrak{G}$ then pick two vertices $v, w$ such that $\vec{vu}$ and $\vec{uw}$ exist. and consider the graph $\mathfrak{G'}$ obtained by taking $\mathfrak{G}$, deleting $\vec{vu}$ and $\vec{uw}$ and adding $\vec{vw}$. (Now if in $\mathfrak{G'}$, the vertex $u$ is disconnected, then change $\mathfrak{G'}$ to $\mathfrak{G'} - u$, otherwise do nothing). In either way, $\mathfrak{G'}$ is now shifu , and has one edge less than $\mathfrak{G}$, so by induction it has an Eulerian circuit $\mathfrak{C'}$. Now create $\mathfrak{C}$ from $\mathfrak{C'}$ by changing the $\cdots \rightarrow \vec{vw} \rightarrow \cdots $ in $\mathfrak{C'}$ to $\cdots \vec{vu} \rightarrow \vec{uw} \rightarrow \cdots$. Clearly, $\mathfrak{C}$ is an Eulerian circuit in $\mathfrak{G}$, so we're done. Now, in a distribution of cards, call it winnable if Hamster wins, and irreducible if it's impossible to partition the set $\{1, \cdots, n \}$ into two disjoint sets $S_1, S_2$ such that for any $i \in S_1, j \in S_2$, the $i$-th pile doesn't contain any card marked with the number $j$ or vice versa. Claim The configuration is winnable iff it's irreducible. ProofFirstly in this distribution, for each $1 \leq i \leq n$ call a card appearing on $i$-th pile useless if it has the value i on it, and suppose $i$ th pile has $0 \leq m_i \leq k$ useless cards. If on any rearrangement, if we operate on any useless card on a pile, we operate on that pile again, so taking away all the useless cards from each pile doesn't changes the outcome of the game. So we remove all the useless cards. Now after removing, note that for each $i$, $$\text{Number of cards on i-th pile} = k - m_i = \text{Total number of cards marked i on other piles}$$. So we create a directed graph $\mathfrak{G}$ with $n$ vertices $v_1, \cdots, v_n$, with the number of $\vec{v_iv_j}$ edges is equal to the number of cards marked with the number $j$ on $i$-th pile. Then $$\text{Indegree}[v_i] = \text{Total number of cards marked i on other piles} = k - m_i = \text{Number of cards in i th pile} = \text{Outdegree}[v_i]$$, so $\mathfrak{G}$ is shifu! Now note two things: $\mathfrak{G}$ is connected (in the sense mentioned in the lemma) iff the distribution is irreducible, and if the distribution is reducible, then we can't clearly win (because we then can never operate on any card in some piles). So suppose the configuration is irreducible, i.e $\mathfrak{G}$ is connected. Then by Lemma , it has an Eulerian Circuit $\mathfrak{C}$. Since it's a circuit which starts and ends at same vertex, we can WLOG choose that vertex to be $v_1$, so the circuit is like $\vec{v_1v_i} \rightarrow \vec{v_iv_j} \rightarrow \cdots \vec{v_1v_m} \cdots \vec{v_pv_q} \rightarrow \vec{v_qv_1}$. Now we construct the desired permutation from the circuit. Initially all the piles are empty. Now first add a card marked $1$ to $q$ th pile, then add a card marked $p$ to $q$ th pile, and commute the circuit backward like this and when you encounter $v_kv_l$ add a card marked $l$ to $k$ th pile on top of what is already there. Then add all the useless cards back. By the properties of the circuit, it's easy to see this construction works

FISHMJ25

16.09.2018 20:14

Kayak wrote: My solution is most probably wrong since it looks simple for an ELMO C7 Can anybody please check it ?

Lemma A directed multiedged graph $\mathfrak{G}$ is called shifu if it has the following properties: For each vertex $u \in V_{\mathfrak{G}}$, we have $\text{Indeegree}[u] = \text{Outdegree}[u]$ There are no edges from $u$ to itself. (Though there might be multiple edges from $u$ to $v$, where $u \neq v$. Then $\mathfrak{G}$ contains an Eulerian Circuit iff it's connectedConnected in the sense if you now treat $\mathfrak{G}$ as undirected, then you can go from any vertex to another commuting through edges ProofThis is well known. One implication is trivial - if it's not connected, then it clearly doesn't have any Eulerian Circuit. We prove the other implication, that if it's connected then it has a circuit. We proceed by induction on the number of edges, base case $|E_{\mathfrak{G}}| = 2$ is trivial. Now pick any vertex $u \in \mathfrak{G}$ then pick two vertices $v, w$ such that $\vec{vu}$ and $\vec{uw}$ exist. and consider the graph $\mathfrak{G'}$ obtained by taking $\mathfrak{G}$, deleting $\vec{vu}$ and $\vec{uw}$ and adding $\vec{vw}$. (Now if in $\mathfrak{G'}$, the vertex $u$ is disconnected, then change $\mathfrak{G'}$ to $\mathfrak{G'} - u$, otherwise do nothing). In either way, $\mathfrak{G'}$ is now shifu , and has one edge less than $\mathfrak{G}$, so by induction it has an Eulerian circuit $\mathfrak{C'}$. Now create $\mathfrak{C}$ from $\mathfrak{C'}$ by changing the $\cdots \rightarrow \vec{vw} \rightarrow \cdots $ in $\mathfrak{C'}$ to $\cdots \vec{vu} \rightarrow \vec{uw} \rightarrow \cdots$. Clearly, $\mathfrak{C}$ is an Eulerian circuit in $\mathfrak{G}$, so we're done. Now, in a distribution of cards, call it winnable if Hamster wins, and irreducible if it's impossible to partition the set $\{1, \cdots, n \}$ into two disjoint sets $S_1, S_2$ such that for any $i \in S_1, j \in S_2$, the $i$-th pile doesn't contain any card marked with the number $j$ or vice versa. Claim The configuration is winnable iff it's irreducible. ProofFirstly in this distribution, for each $1 \leq i \leq n$ call a card appearing on $i$-th pile useless if it has the value i on it, and suppose $i$ th pile has $0 \leq m_i \leq k$ useless cards. If on any rearrangement, if we operate on any useless card on a pile, we operate on that pile again, so taking away all the useless cards from each pile doesn't changes the outcome of the game. So we remove all the useless cards. Now after removing, note that for each $i$, $$\text{Number of cards on i-th pile} = k - m_i = \text{Total number of cards marked i on other piles}$$. So we create a directed graph $\mathfrak{G}$ with $n$ vertices $v_1, \cdots, v_n$, with the number of $\vec{v_iv_j}$ edges is equal to the number of cards marked with the number $j$ on $i$-th pile. Then $$\text{Indegree}[v_i] = \text{Total number of cards marked i on other piles} = k - m_i = \text{Number of cards in i th pile} = \text{Outdegree}[v_i]$$, so $\mathfrak{G}$ is shifu! Now note two things: $\mathfrak{G}$ is connected (in the sense mentioned in the lemma) iff the distribution is irreducible, and if the distribution is reducible, then we can't clearly win (because we then can never operate on any card in some piles). So suppose the configuration is irreducible, i.e $\mathfrak{G}$ is connected. Then by Lemma , it has an Eulerian Circuit $\mathfrak{C}$. Since it's a circuit which starts and ends at same vertex, we can WLOG choose that vertex to be $v_1$, so the circuit is like $\vec{v_1v_i} \rightarrow \vec{v_iv_j} \rightarrow \cdots \vec{v_1v_m} \cdots \vec{v_pv_q} \rightarrow \vec{v_qv_1}$. Now we construct the desired permutation from the circuit. Initially all the piles are empty. Now first add a card marked $1$ to $q$ th pile, then add a card marked $p$ to $q$ th pile, and commute the circuit backward like this and when you encounter $v_kv_l$ add a card marked $l$ to $k$ th pile on top of what is already there. Then add all the useless cards back. By the properties of the circuit, it's easy to see this construction works

It looks correct and i think it is realy nice.

K_Mirrorheart

02.04.2019 16:43

Well this is an easy C7, at least much easier than 2011's A1, which proved to be a catastrophe. Because the question nearly explicitly asks for a Eulerian Circuit and the condition of existing an EC in directed graph is quite well-known.

KI_HG

25.06.2023 17:29

Can someone explain the rule, I don't quite get it. If every card has been flipped, then there must exist a pile that all the cards have been flipped. Isn't it?

signifance

31.10.2023 04:18

redacted

Om245

20.04.2024 20:17

Consider graph $G$ with piles as vertex of $G$ with vertex set $V$ = ${V1,V_2,\cdots,V_k}$. .Let we assume $G$ is connected. Now note that indegree and outdegree of each vertex is $k$. (we consider multiple edges) hence degree of each vertex is even. It well know if all vertex of graph are even then there exists Eulerian circuit Now if there $i$ number card in $i$th pile, place it at top as it doesn't matter. If eulerian circuit is $V{a1} \rightarrow V{a2} \rightarrow \cdots \rightarrow V{al}$. Then rearrange card in that manner. (note as $V{ai} \rightarrow V{a{i+1}}$ there exit card of number $a{i+1}$ in $V{a_i}$ by construction of graph). hence we will have our arrgement. Now note if $G$ is not connected it is not posibble to reach all piles. So for $G$ to be connected, for any $m$ piles ${V{b1},V{b2},\cdots,V{b_m}}$ we should not have only number $b_1,b_2,\cdots,b_m$ in these plies. else there will no edge connected this set of $m$ plies with other. In cards sence we should not have set of plies which contain only there piles index number Hopefully not wrong