Difference between revisions of "1992 AIME Problems/Problem 12"
m (tagged) |
m |
||
| (11 intermediate revisions by 8 users not shown) | |||
| Line 1: | Line 1: | ||
| − | |||
== Problem == | == Problem == | ||
| + | In a game of <i>Chomp</i>, two players alternately take bites from a 5-by-7 grid of [[unit square]]s. To take a bite, a player chooses one of the remaining [[square (geometry) | squares]], then removes ("eats") all squares in the quadrant defined by the left edge (extended upward) and the lower edge (extended rightward) of the chosen square. For example, the bite determined by the shaded square in the diagram would remove the shaded square and the four squares marked by <math>\times.</math> (The squares with two or more dotted edges have been removed form the original board in previous moves.) | ||
| − | + | [[Image:AIME_1992_Problem_12.png]] | |
| − | |||
| − | == | + | The object of the game is to make one's opponent take the last bite. The diagram shows one of the many [[subset]]s of the [[set]] of 35 unit squares that can occur during the game of Chomp. How many different subsets are there in all? Include the full board and empty board in your count. |
| − | + | ||
| + | == Solution 1 == | ||
| + | By drawing possible examples of the subset, one can easily see that making one subset is the same as dividing the game board into two parts. | ||
| + | |||
| + | One can also see that it is the same as finding the shortest route from the upper left hand corner to the lower right hand corner; Such a route would require 5 lengths that go down, and 7 that go across, with the shape on the right "carved" out by the path a possible subset. | ||
| + | |||
| + | Therefore, the total number of such paths is <math>\binom{12}{5}=\boxed{792}</math> | ||
| + | |||
| + | == Solution 2 == | ||
| + | If any square is eaten, the squares to the right of it must also be eaten. Thus, if <math>a_i</math> is the number of squares remaining on row <math>i</math>, there is exactly one way the row can be configured (the leftmost <math>a_i</math> squares are uneaten and the ones to the right are eaten.) Additionally, the squares above an eaten square must be eaten, so <math>\{a_i\}</math> is nondecreasing. We can thus write <math>0 \leq a_1 \leq a_2 \leq \dots \leq a_5 \leq 7</math>; the number of sequences <math>\{a_i\}</math> satisfying this inequality may be found by Stars and Bars to be <math>\binom{7+6-1}{6-1} = \boxed{792}</math>. | ||
| + | |||
| + | ===Note=== | ||
| + | This game is similar to an AoPS book. | ||
| − | + | == Links to Branches of Mathematics == | |
| + | This question is one case of the problem of counting [[order ideal]]s or [[antichain]]s in [[poset]]s. Specifically, it ask for the number of order ideals of the [[product poset]] of the [[chain]] of length <math>4</math> and the chain of length <math>6</math>. | ||
| − | + | == See also == | |
| + | {{AIME box|year=1992|num-b=11|num-a=13}} | ||
| + | {{MAA Notice}} | ||
Latest revision as of 21:41, 22 December 2021
Problem
In a game of Chomp, two players alternately take bites from a 5-by-7 grid of unit squares. To take a bite, a player chooses one of the remaining squares, then removes ("eats") all squares in the quadrant defined by the left edge (extended upward) and the lower edge (extended rightward) of the chosen square. For example, the bite determined by the shaded square in the diagram would remove the shaded square and the four squares marked by 
(The squares with two or more dotted edges have been removed form the original board in previous moves.)
The object of the game is to make one's opponent take the last bite. The diagram shows one of the many subsets of the set of 35 unit squares that can occur during the game of Chomp. How many different subsets are there in all? Include the full board and empty board in your count.
Solution 1
By drawing possible examples of the subset, one can easily see that making one subset is the same as dividing the game board into two parts.
One can also see that it is the same as finding the shortest route from the upper left hand corner to the lower right hand corner; Such a route would require 5 lengths that go down, and 7 that go across, with the shape on the right "carved" out by the path a possible subset.
Therefore, the total number of such paths is 
Solution 2
If any square is eaten, the squares to the right of it must also be eaten. Thus, if 
is the number of squares remaining on row 
, there is exactly one way the row can be configured (the leftmost squares are uneaten and the ones to the right are eaten.) Additionally, the squares above an eaten square must be eaten, so 
is nondecreasing. We can thus write 
; the number of sequences satisfying this inequality may be found by Stars and Bars to be 
.
Note
This game is similar to an AoPS book.
Links to Branches of Mathematics
This question is one case of the problem of counting order ideals or antichains in posets. Specifically, it ask for the number of order ideals of the product poset of the chain of length 
and the chain of length 
.
See also
| 1992 AIME (Problems • Answer Key • Resources) | ||
| Preceded by Problem 11 |
Followed by Problem 13 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
