and 
Prove that
,
,
,
,
are odd primes and![\[2^ap^b=(p+2)^c-1.\]](http://latex.artofproblemsolving.com/5/8/5/58518a8ebed14836b72af743ff100eae2efba5e2.png)
and 
are given. Let 
be the midpoint of the segment joining their centers, 
,
be arbitrary points on 
.
.
of points in the plane is balanced if, for any two different points 
in 
.
in 
.
,
Y by Amir Hossein, mssmath, Davi-8191, AopsUser101, Adventure10, megarnie, Mango247
Let 
be a positive integer. Each point 
in the plane, where 
and 
are non-negative integers with 
, is coloured red or blue, subject to the following condition: if a point is red, then so are all points 
with 
and 
. Let 
be the number of ways to choose blue points with distinct -coordinates, and let 
be the number of ways to choose blue points with distinct -coordinates. Prove that 
.
be a positive integer. Each point 
in the plane, where 
and 
are non-negative integers with 
, is coloured red or blue, subject to the following condition: if a point is red, then so are all points 
with 
and 
. Let 
be the number of ways to choose blue points with distinct -coordinates, and let 
be the number of ways to choose blue points with distinct -coordinates. Prove that 
.Attachments:
This post has been edited 4 times. Last edited by orl, Sep 27, 2005, 4:57 PM
.
.
go down as far as you can without taking any red points. Now go to the right until you meet the diagonal again. The maximal triangles of this set are the ones we're looking for.
is equal to the number of blue rows of length 
,
is the same as the number of blue rows of length 
.
the number 
.
the number of blue points labeled with number 
.
,
,
(draw a diagram and do the number assignment to see why).
,
)
be the number of blue points in column 
be the number of blue points in diagonal 
.
is a permutation of 
.
any coloring is good. Suppose for some 
,
above the set 
.
above the set 
.
to each column and diagonal so it is also good. Now suppose we color a point red in the row 
is equivalent to coloring 
and 
and 
are 
.
.
,
are blue and the points 
are red. Then you just switch the 
coordinate by the 
coordinate in each point. It's easy to see that all the points that were in the original line 
are in the transformed line 
)
and 
,
degrees counter-clockwise and then reflecting it over the 
Also remember that in the early days of the IMO, there was not much combinatorics at all.
be red point with 
be the point with 
maximal among red point. 
is blue iff 
or 
.
coordinates 
it necessarily that : ![\[n>k_0>q, n-1>k_1>q,...,n-p>k_p>q\]](http://latex.artofproblemsolving.com/a/2/4/a24c8a075faa48e68dbfc8c40df1a32be3e9072a.png)
and ![\[k_{p+1}<n-(p+1),...,k_{n-1}<n-(n-1)\]](http://latex.artofproblemsolving.com/b/0/3/b0381887f5f6a5e98113fe5b55dae3180e7cdaf0.png)
which gives a number (if it is not equal to zero i.e 
not large enough) of possible configurations ![\[\prod_{i=1}^{p+1}(n-i-q)\prod_{i=p+1}^{n-1}(n-i)=\frac{(n-(q+1))!(n-(p+1))!}{(n-p-q-2)!}\]](http://latex.artofproblemsolving.com/9/c/d/9cda0ac632874f45ff4449728f0e42f082a59c51.png)
coordinates.
denote the number of blue points with coordinate 
denote the number of blue points with coordinate 
denote the rightmost red point of the form 
is 
(since 
,
or 
,
be the maximum possible 
be the maximum possible 
.
,
and ends at 
,
,
.
,
to 
.
,
,
,
.
.
.
,
): This problem is quite easy, but expressing the whole idea in words is quite difficult tbh (as you can see from my solution 
denote the number of blue points with a given 
similarly.
and 
are equal.
.
red. Before the coloring, we have 
;
and no other numbers change, as desired. Since every permissible set of red points can be built inductively this way (indeed it's a Young tableaux!) this implies the result. ![\[ A = \prod_{x=0}^{n-1} a_x = \prod_{y=0}^{n-1} b_y = B. \]](http://latex.artofproblemsolving.com/3/5/5/355418d3cf66912ff055dbb4e7b1f4ad1349e5d6.png)
,
and 
denote the number of blue points with 
.
,
was now marked red; except 
and 
,
and 
but 
,
being fairly obvious.
There are 2 cases:
Then just shift one to the left and apply the inductive hypothesis; this does not affect the ordering of the blue points.
as desired.
be the number of blue points with x (resp. y) coordinates k; we'll prove that 
by showing the sequence b is a permutation of the sequence a using strong induction, with base case n=1 trivial, so assume now the inductive hypotheses, and for convenience let 
denote permutation of each other. If all points on the line x+y=n are blue, we're done since 
,
due to inductive hypothesis and just adding 1 for every point (since there's an extra blue point now on every horizontal/vertical line). However, if some point (m,n-m) is red, then 
,
.
and 
denote the number of blue points of column 
be red with 
.
.
is trivial. Assume now that 
for all 
.
turns the product
so that 
.
as an all blue line also finishes this problem.
,
.
.
to the entire triangle increases the number of blue in each row and column increases by 
,
as the number of blue points with 
as the number of blue points with 
and 
are permutations of each other through induction on 
.
satisfies the condition, we claim that adding the 
points on the line 
to prove the case 
,![\[(a_0+1) \cdot \ldots \cdot (a_k+1) \cdot 1 = (b_0+1) \cdot \ldots \cdot (b_k+1) \cdot 1.\]](http://latex.artofproblemsolving.com/3/2/d/32d8b29e021124fb51a40a7cf802b34b6a96283a.png)
,
to 
,
being true. We can do induction by adding in the set of points on the line 
.
is the number of blue points on row 
is the number of blue points on column 
.
.
be the number of blue points in each row and column. It satisfies to prove multisets 
as 
We prove this by induction. The base case of 
and consider 
Observe that for 
bounded by 
with row/column blue values 
,
Now for each point 
,
or 
were blue, then 
In the latter, 
Either way, the inductive step is complete as the multisets 
and 
to the the number of 
and 
to be the number of points with 
and 
all the time, over all 
and 
respectively.
we have the set of points with 
)
be the function that sums a point's coordinates.
this is just a case from the inductive hypothesis. Now the points with coordinate sum higher than 
to each 
.
.
is obvious by symmetry, its just 
.
where 
originally be 
,
options to 
options for that column, and no other columns changed. An identical argument on row 
is trivial by casework. Now, assume that our proposition holds for 
Clearly, we are essentially adding another line below the grid for 
On this row, let the number of blue points be 
Then clearly the first 
points are red. By our inductive hypothesis, the product of the number of blue points in the first 
By adding the new row, the product of the number of blue points in the rows is increased by a factor of 
columns, it is clear that the number of blue points in column 
)
Thus, 
by telescoping, so our induction is complete. QED
and 
are equal, which obviously proves the desired statement. We prove this with induction on 
.
are increased by 
or 
for the corresponding 
invariant.
and 
for the 
grid. We will prove the result by induction on 
.
,
similarly, such that 
and 
.
where 
is a positive integer. (If 
,
is vacuous.) Observe that since 
and 
for 
,![\[A_{n-1} = A_n \cdot \frac 12\cdot \frac 23 \cdots \frac{k-1}k = \frac{A_n}k\]](http://latex.artofproblemsolving.com/a/7/4/a748501d9479239f73c102ee7bf4cbbeb0d8084e.png)
and clearly 
as there are 
,
follows, which completes the induction.
