MathDB

3

Part of 2009 Rioplatense Mathematical Olympiad, Level 3

Problems(2)

Number of decreasing subsequences of 1,2,...,n permutation

Source: XVIII Olimpíada Matemática Rioplatense (2009)

7/23/2011
Call a permutation of the integers (1,2,…,n)(1,2,\ldots,n) dd-ordered if it does not contains a decreasing subsequence of length dd. Prove that for every d=2,3,…,nd=2,3,\ldots,n, the number of dd-ordered permutations of (1,2,…,n)(1,2,\ldots,n) is at most (d−1)2n(d-1)^{2n}.
combinatorics unsolvedcombinatorics
Game: Combining rectangles to make bigger rectangles

Source: XVIII Olimpíada Matemática Rioplatense (2009)

7/23/2011
Alice and Bob play the following game. It begins with a set of 10001000 1×21\times 2 rectangles. A move consists of choosing two rectangles (a rectangle may consist of one or several 1×21\times 2 rectangles combined together) that share a common side length and combining those two rectangles into one rectangle along those sides sharing that common length. The first player who cannot make a move loses. Alice moves first. Describe a winning strategy for Bob.
geometryrectanglecombinatorics unsolvedcombinatorics