For positive integers $a$ and $b$, an $(a,b)$-shuffle of a deck of $a+b$ cards is any shuffle that preserves the relative order of the top $a$ cards and the relative order of the bottom $b$ cards. Let $n$, $k$, $a_1$, $a_2$, $\dots$, $a_k$, $b_1$, $b_2$, $\dots$, $b_k$ be fixed positive integers such that $a_i+b_i=n$ for all $1\leq i\leq k$. Big Bird has a deck of $n$ cards and will perform an $(a_i,b_i)$-shuffle for each $1\leq i\leq k$, in ascending order of $i$. Suppose that Big Bird can reverse the order of the deck. Prove that Big Bird can also achieve any of the $n!$ permutations of the cards. Linus Tang
Problem
Source: ELMO 2024/2
Tags: combinatorics, Elmo
21.06.2024 19:22
There's one key claim of this problem. Claim: Suppose it's possible to top shuffle $1234 \dots n$ to some permutation $P$ which contains $p_1, p_2, \dots, p_n$ such that $p_i > p_{i+1}$ is an inversion. Then it's possible to top shuffle to $P'$ such that $p_i$ and $p_{i+1}$ are swapped. Proof. The existence of a top shuffle and the inversion means that there exists a top shuffle that inverts the order of $p_i, p_{i+1}$. If the inversion also puts $p_i, p_{i+1}$ adjacent to each other replace the top shuffle with one where they are put in a different order. Else, do that to the first top shuffle which does put $p_i, p_{i+1}$ adjacent to each other in that order. $\blacksquare$ We can then place this operation to selectively turn $n, n-1, \dots, 2, 1$ into any other permutation $p_1, \dots, p_n$ by moving $p_n$ in the original array down and so forth. Here's an example for constructing $1432$ from $1234$: \[ 1234 \to 1324 \to 1342 \to 1432. \]
21.06.2024 21:36
https://dgrozev.wordpress.com/2024/06/19/shuffling-cards-elmo-2024-problem-2/ EDIT Let me tell you my opinion about this circus. You posted a set of problems publicly. It has been seen by thousands of thousands of students. And you can’t say… well, don’t comment on them unless we let you! And it lasted more than two weeks! This is ridiculous. It’s like forbidding a forest to grow.
21.06.2024 23:29
dgrozev wrote: https://dgrozev.wordpress.com/2024/06/19/shuffling-cards-elmo-2024-problem-2/ EDIT Let me tell you my opinion about this circus. You posted a set of problems publicly. It has been seen by thousands of thousands of students. And you can’t say… well, don’t comment on them unless we let you! And it lasted more than two weeks! This is ridiculous. It’s like forbidding a forest to grow. USAMTS:
22.06.2024 00:11
dgrozev wrote: https://dgrozev.wordpress.com/2024/06/19/shuffling-cards-elmo-2024-problem-2/ EDIT Let me tell you my opinion about this circus. You posted a set of problems publicly. It has been seen by thousands of thousands of students. And you can’t say… well, don’t comment on them unless we let you! And it lasted more than two weeks! This is ridiculous. It’s like forbidding a forest to grow. Isn’t Kömal kind of the same thing? I mean if the contest (or in this case I’m assuming the appeal process) is still going on, I think it’s fair to ask not to discuss them publicly. In other case, they will just postpone posting problems next year, which doesn’t benefit anyone.
22.06.2024 05:11
Anyone did this using permutation graph ?
22.06.2024 17:59