MathDB
2008 PUMaC Combinatorics A10

Source:

October 4, 2019
combinatorics

Problem Statement

In his youth, Professor John Horton Conway lived on a farm with 20092009 cows. Conway wishes to move the cows from the negative xx axis to the positive xx axis. The cows are initially lined up in order 1,2,...,20091, 2, . . . , 2009 on the negative xx axis. Conway can give two possible commands to the cows. One is the PUSH command, upon which the first cow from the negative xx axis moves to the lowest position on the positive yy axis. The other is the POP command, upon which the cow in the lowest position on the yy axis moves to the positive xx axis. For example, if Conway says PUSH POP 20092009 times, then the resulting permutation of cows is the same, 1,2,...,20091, 2, . . . , 2009. If Conway says PUSH 20092009 times followed by POP 20092009 times, the resulting permutation of cows is 2009,...,2,12009, . . . , 2, 1. How many output permutations are possible after Conway finishes moving all the cows from the negative xx axis to the positive xx axis?
Back to ProblemsView on AoPS