https://artofproblemsolving.com/wiki/index.php?title=2007_Indonesia_MO_Problems/Problem_5&feed=atom&action=history 2007 Indonesia MO Problems/Problem 5 - Revision history 2021-04-15T03:24:21Z Revision history for this page on the wiki MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2007_Indonesia_MO_Problems/Problem_5&diff=118550&oldid=prev Rockmanex3: Solution to Problem 5 -- easy problem with hard solution writing 2020-02-28T17:05:27Z <p>Solution to Problem 5 -- easy problem with hard solution writing</p> <p><b>New page</b></p><div>==Problem==<br /> <br /> Let &lt;math&gt; r&lt;/math&gt;, &lt;math&gt; s&lt;/math&gt; be two positive integers and &lt;math&gt; P&lt;/math&gt; a 'chessboard' with &lt;math&gt; r&lt;/math&gt; rows and &lt;math&gt; s&lt;/math&gt; columns. Let &lt;math&gt; M&lt;/math&gt; denote the maximum value of rooks placed on &lt;math&gt; P&lt;/math&gt; such that no two of them attack each other.<br /> <br /> (a) Determine &lt;math&gt; M&lt;/math&gt;.<br /> <br /> (b) How many ways to place &lt;math&gt; M&lt;/math&gt; rooks on &lt;math&gt; P&lt;/math&gt; such that no two of them attack each other?<br /> <br /> [Note: In chess, a rook moves and attacks in a straight line, horizontally or vertically.]<br /> <br /> ==Solution==<br /> <br /> For the first part, note that once one rook is placed, other rocks can not be in the same row or same column as the other rooks. Thus, the second rook can be in &lt;math&gt;r-1&lt;/math&gt; of the rows and in &lt;math&gt;s-1&lt;/math&gt; of the columns, and the &lt;math&gt;n^\text{th}&lt;/math&gt; rook can be in &lt;math&gt;r-n+1&lt;/math&gt; of the rows and in &lt;math&gt;s-n+1&lt;/math&gt; of the columns. Since &lt;math&gt;r-(n-1)&lt;/math&gt; and &lt;math&gt;s-(n-1)&lt;/math&gt; must be greater than &lt;math&gt;0&lt;/math&gt; for the rook to be on the board, &lt;math&gt;n&lt;/math&gt; can be at most &lt;math&gt;s&lt;/math&gt; or &lt;math&gt;r&lt;/math&gt;, and since a rook must be on a row and a column, &lt;math&gt;n&lt;/math&gt; must be at most the minimum of &lt;math&gt;s&lt;/math&gt; and &lt;math&gt;r&lt;/math&gt;. Thus, &lt;math&gt;M = \boxed{\min (r,s) }&lt;/math&gt;.<br /> <br /> &lt;br&gt;<br /> Because there are &lt;math&gt;M&lt;/math&gt; rooks on the board, the rooks would take up every row or column (whichever one is fewer), so we would consider the number of ways a rook can be on a given row or column (whichever one is fewer). For instance, if &lt;math&gt;r \ge s&lt;/math&gt;, then the rook in the first column can be in &lt;math&gt;r&lt;/math&gt; of the rows, the rook in the second column can be in &lt;math&gt;r-1&lt;/math&gt; of the rows, and so on. Similarly, if &lt;math&gt;r &lt; s&lt;/math&gt;, then the rook in the first row can be in &lt;math&gt;s&lt;/math&gt; of the columns, the rook in the second row can be in &lt;math&gt;s-1&lt;/math&gt; of the columns, and so on. Therefore, the number of ways to place &lt;math&gt;M&lt;/math&gt; rooks on the board is &lt;math&gt;\boxed{\frac{(\max (r,s) )!}{M!}}&lt;/math&gt;.<br /> <br /> ==See Also==<br /> {{Indonesia MO box|year=2007|num-b=4|num-a=6}}<br /> <br /> [[Category:Introductory Combinatorics Problems]]</div> Rockmanex3