prove that![$\frac{a}{b} + \sqrt {\frac{b}{c}} + \sqrt[3]{{\frac{c}{a}}} > \frac{5}{2}$](http://latex.artofproblemsolving.com/6/a/6/6a657cb647e279b0745e3189c3f9d54aa25bf976.png)
with 
,
intersects the extension of 
at point 
.
is the midpoint of 
,
intersects the circumcircle of 
.
.
be positive real numbers such that 
.![\[ \frac{a_{1} a_{2} \cdots a_{n} \left[ 1 - (a_{1} + a_{2} + \cdots + a_{n}) \right] }{(a_{1} + a_{2} + \cdots + a_{n})( 1 - a_{1})(1 - a_{2}) \cdots (1 - a_{n})} \leq \frac{1}{ n^{n+1}}. \]](http://latex.artofproblemsolving.com/6/5/5/65558feba82e32266d3d3cbdfea85e079483403f.png)
with integer coefficients such that for all positive number 
and prime 
satisfying 
,
.
Y by Adventure10, Mango247, ihatemath123
You have a 
by 
grid of squares coloured in the same way as a standard checkerboard. Find the total number of ways to place 
counters on white squares so that each square contains at most one counter and no two counters are in diagonally adjacent white squares.
by 
grid of squares coloured in the same way as a standard checkerboard. Find the total number of ways to place 
counters on white squares so that each square contains at most one counter and no two counters are in diagonally adjacent white squares.
squares. Call these big squares. Each big square contains exactly 
counter as there are 
or 
if the counter is in the top-left/bottom-right square respectively.
big squares directly to the left, above and diagonally to the left and above also labeled 
rows is labelled:
If we label the rows 
where the top row is labelled 
So this is equivalent to finding a decreasing function 
which there are many ways to find for example consider 
and then observe a partition of 
parts uniquely determines the function so using stars and bars there are:
valid configurations
Split the entire grid into 
board, where we color a square blue if it's counter is in the bottom right position, and red otherwise. Observe that the amount of ways to color this grid bijects to a path taken from the bottom left corner to the top right corner, so the answer is 
as requested.
,
denotes the 
counter.
,
,
is there because of the starting permutations.
,
the number of ways for a grid of dimensions 
.
.
.
,
,
.
algorithm on the rows numbered with a odd number from 
(the 
from 
,
,
,
,
and does the 
This is now proven by induction, let's say that we have our formula 
.
.
,
Which is what we wanted to prove by induction.
.
grid into a 
grid of 
squares.
be the number of blue squares in the 
is non-increasing as 
.
,
with 
and 
.
,
.
.
grid into tiles, and give each a row number and column number from bottom to top and left to right respectively (row numbers are from 
)
one counter placed on it since the number of tiles is 
which is also the number of counters. Therefore, every tile must have exactly 
be the highest B tile in the last column (note that 
if there are no B tiles in the last column). We see that tile 
must also be a B tile since if it was an A tile we would have two diagonally adjacent white squares with counters in them. However, this also forces tile 
to be a B tile by the same logic. Repeatedly applying this logic yields that all tiles in the last column below the highest B tile must also be B tiles. We can apply similar logic to deduce that all tiles to the left of an A tile must also be A tiles.
,![\[\binom{x+n}{n}\]](http://latex.artofproblemsolving.com/4/b/9/4b97f0a2b15e8d381c90d3636727882c6661047b.png)
to ![\[\binom{n}{n} + \binom{n+1}{n} + \cdots + \binom{n+m}{n}.\]](http://latex.artofproblemsolving.com/4/6/0/460c525696150a314177505c0e9a1219ff7d6c50.png)
![\[\binom{(n+1)+m}{(n+1)}\]](http://latex.artofproblemsolving.com/d/e/7/de7c5fb2a61d6a73f33a39eb395a547e6e3befc1.png)
.
.
board, with each square of this 
and each column from left to right as 
Place a counter in all 
for 
and 
Suppose the top right corner, or 
is white. Notice that all possible configurations are reachable by some shift of counters in the current sequence. In each 
by 
be where the white cell 
has a counter and 
be the state where the white cell 
has a counter. Now, consider a 
and 
(each entry is the state of each 
This condition has a bijection between the number of right-down blockwalks with 
.
where 
denotes the row and 
denotes the column. We'll let 
be the upper left cell. WLOG let 
is even.
and 
for some 
and 
.
)
counters (from top down) are of the form 
and the rest are of the form 
,
.
denote this value of 
.
starting from left to right. The key claim is that the sequence 
must be nondecreasing, and that every such sequence will result in a valid arrangement.
,
for 
.
for 
.
and 
,
such that 
for all 
.
,
for all 
,
.
is nonnegative for all 
sequence corresponds to exactly one unique 
.
be the required number of ways. First, observe that every 
board and consider the top-right 
board can be tiled in 
ways. Similarly, if the bottom right square of the 
ways.
works by checking that 
and then inducting by using the common identity 
be the number of subgrids in column ![\[1 \leq a_1 \leq a_2... \leq a_m \leq n\]](http://latex.artofproblemsolving.com/8/1/e/81e858698de498d7c4a267e25677175da2a221e4.png)
and thus we need to find the number of solutions to this. However this bijects to, once again in an m x n grid, to the number of ways to move from the bottom-left corner to the top-right one. One can think of it like this: start at the bottom-left corner and move up until you are at row 
,
and so on, and once you are 
,
.
,
ways to do this, based on casework relating to the last tile se land on. This simplifies to 
by two applications of Pascal's identity, as desired.
.
.
square of the form ![\[\begin{bmatrix}
a&b \\ c&d
\end{bmatrix}\]](http://latex.artofproblemsolving.com/5/7/a/57a0d3f5d5e82d18821a97a808b5d4d80e276ce7.png)
where 
represents white cell and 
represents black cell. Let 
denote the number of placing 
grid. Also note that the entire grid can be covered with exactly 
is easy. If the top right corner block contains a counter in the 
cell then all the blocks below this block (in the same column) must have counters placed in the 
.
.
Expanding one of the terms
Note that 
can be easily proven via single variable induction on 
and adding both gives that
which completes the induction.
board, i.e. when 
.
represents a white square with a counter and 
denotes an unoccupied white square: 
Now, we have one extra 
ways to place it, as desired. Furthermore, it's easy to see the 
counters must be in the last 
.
for corresponding values of 
board. View the board as 
But we want 
where 
.
such that 
This is equivalent to the condition 
Since all pairwise terms of the form ![$a_i + ([m+1] - i)$](http://latex.artofproblemsolving.com/7/b/d/7bd29fe87d354e3a7560e6609c18440e492bd9c1.png)
are distinct in the previous inequality chain, we know there's 
![[asy]
size(3cm);
real d = 0.1;
path rect(int a, int b, int x, int y)
{
return (a+d,b+d)--(x-d,b+d)--(x-d,y-d)--(a+d,y-d)--cycle;
}
draw((0, 0)--(0, 2)--(2, 2)--(2, 0)--(0, 0));
draw((0, 1)--(2, 1));
draw((1, 0)--(1, 2));
fill(rect(0, 0, 1, 1), black);
[/asy]](http://latex.artofproblemsolving.com/f/6/a/f6ab5810c353105bf15588656b4a85445bdc9d49.png)
and 
and 
and 
are pretty obvious, so I won't go into much detail. Now assume that we want to prove that it works for some 
.
such that 
and 
.
row from the previous configuration. Now we will do some casework. Consider the newly added 
.
case. Thus the answer is 
.
case. Thus the answer is 
.
.![\[ \binom{m+n}{m}+\binom{m+n-1}{m}+\binom{m+n-2}{m}+\dots+\binom{m}{m}=\binom{m+n+1}{m+1} \]](http://latex.artofproblemsolving.com/1/9/0/1908b4c3430e590ca68b5c2c480418ea6af6b667.png)
as desired. 
grid of 2x2 squares to the bottom left. Everything below the path traced out is colored blue and everything above is colored red. These are in fact all the valid ways to color by the ``forcing rule" that the blue squares follow, so our answer is
.
be the number of ways to place counters on the 
is even, and black otherwise.
then 
.
then 
.
,
,
and proves the other result.
.
.
be the least integer such that 
(where 
means there is no occurrence of 
and by minimalism assumption, 
.
choices for 
.
is true by Lemma 2 as 
as desired.
for all 
which has corresponding matrix 
.
-
and 
.
.
with 
there is no restrictions and the number of ways to choose them is 
where for 
(essentially the whole array is ones). Summing over all 
applying the hockey stick identity in the last step. This completes the inductive step and proves the claim.
,
and the bottom right block be 
.
is red, then the rectangle with vertices 
,
and 
.
.
,
and 
to 
is simply 
squares, since this operation contains all the counters. In fact, this works since there are exactly 
.
.
grid into ![[asy]
size(3cm);
real d = 0.1;
path rect(int a, int b, int x, int y)
{
return (a+d,b+d)--(x-d,b+d)--(x-d,y-d)--(a+d,y-d)--cycle;
}
draw((0, 0)--(0, 2)--(2, 2)--(2, 0)--(0, 0));
draw((0, 1)--(2, 1));
draw((1, 0)--(1, 2));
fill(rect(0, 1, 1, 2), black);
fill(rect(1, 0, 2, 1), black);
filldraw(circle((1.5,1.5),0.4),cyan,linewidth(0.5));
[/asy]](http://latex.artofproblemsolving.com/5/8/3/5838be303743dd9efb7dd714fc16501e13938bb0.png)
denote the number of ways to place counters on a ![\[P(m,n)=P(m,n-1)+P(m-1,n-1)+\cdots+P(0,n-1).\]](http://latex.artofproblemsolving.com/e/8/a/e8a667fff974a31a2afcc60c5789fb7b267f34e2.png)
which suffices by performing strong induction and we are done.
grid because there is no chance that a counter from the bottom row will be adjacent to a counter from the upper 
grid.
ways to tile the grid. Similarly, for the UL case, there are 
ways to tile the grid. Hence, we get the equation 
.
and 
.![\[f(m,n)=\binom{m+n}{n} \text{ for all positive integers } m,n.\]](http://latex.artofproblemsolving.com/3/6/8/36855111c4f509642d0df5e67373d92133419819.png)
First, we have already mentioned the base 
and 
.
for all 
,
.
Then, by repeatedly applying Pascal's Identity, we get that 
for all 
.
if the counter is in the bottom and 
otherwise. Notice that if a certain square is red, every square to the right or below it must also be red.![\[\boxed{\binom{m+n}{m}.}\]](http://latex.artofproblemsolving.com/1/e/a/1ea1d9095689c46e52ce00123e04a62d5d4d505c.png)
it follows that we have to put exactly 1 counter in each 2x2 square.
must contain exactly one counter.
be the answer for 
Suppose that 
and WLOG, assume that the top-left square was black. Clearly if the top-left 
for 
Now, we calculate 
for positive integers 
Using similar logic as above will yield us 
for 
we have that 
Now, observe that 
and this can easily be shown to work.
or 
depending on the case. If a 
is immediate
ways to do so.
) Then, it is easy to see that each cell must contain exactly one counter by pigeonhole principle.
(for top) and 
.
,
,
,
such that for each of the 
squares of size 
is non-decreasing, and the number of ways to tile a grid in such a manner is equivalent to finding a path on the grid such that tiles below the path are bottom-right squares and tiles above the path are top-left squares. There are 
