AoPS Academy
and 
satisfy 
, then 
is an even number.
+1 w
, not all equal to 
, the following inequality holds
for which the equality holds.
,
and 
are given, with 
. You play the following game against an evil wizard.
cards; for each 
, there are two cards labeled 
. Initially, the wizard places all cards face down in a row, in unknown order. of the cards. The wizard then turns those cards face up. If any two of the cards match, the game is over and you win. Otherwise, you must look away, while the wizard arbitrarily permutes the chosen cards and then turns them back face-down. Then, it is your turn again.
and some strategy that is guaranteed to win in at most moves, no matter how the wizard responds. and is the game winnable?
with real coefficients such that 
holds for all nonzero real numbers satisfying 
.
. It's nice.
to show that 
(
and 
) iff 
, where the base case is clear.
. Note that 
for all 
. Since![\[s_1 < s_{n+1} < \cdots < s_{n^2+1},\]](http://latex.artofproblemsolving.com/3/4/e/34efb4b0fc4a990d81b3c6b523020907f1c8f2f8.png)
we have 
for . In particular,![\[a_1=\cdots=a_n=0\wedge a_{n^2+1}+\cdots+a_{n^2+n}=1.\]](http://latex.artofproblemsolving.com/9/a/6/9a6906a0b41c7b242775e136274405fe20ed9ad3.png)
Thus
However, 
gives us ![$s_{kn+2}\in[k,k+1]$](http://latex.artofproblemsolving.com/6/e/6/6e68a7e15a87069ff1fcdc9854b17f1f6df3edf5.png)
for 
. If 
, though, we must have![\[A = s_2+s_{n+2}+\cdots+s_{(n-1)n+2} \le 1+2+\cdots+(n-1) < B,\]](http://latex.artofproblemsolving.com/c/5/6/c56d6d32fa9f28255e519b789f84cef46e070289.png)
a contradiction. So 
, whence![\[B-n = 1+2+\cdots+(n-2) \ge s_2+s_{n+2}+\cdots+s_{(n-2)n+2} = A-s_{(n-1)n+2} = A-n\]](http://latex.artofproblemsolving.com/9/6/4/964bd606b4964a6eac477e26aca6060892b531c9.png)
and so 
for 
. Letting range from to 
, we find that![\[0=a_1=a_{n+1}=\cdots=a_{(n-1)n+1}.\]](http://latex.artofproblemsolving.com/2/d/2/2d2b730f94bdd308a4d98b9b8aa646311f54bf2d.png)
But 
, so![\[a_{(n-1)n+2}=\cdots=a_{(n-1)n+n}=1.\]](http://latex.artofproblemsolving.com/e/9/c/e9cc9eaebcf6aa2048e696f370d1290195dbf045.png)
, for and 
satisfy the inductive hypothesis, so we're done. (Visualizing the numbers in a 
matrix also helps.)
Note the chain of inequalities ![\[ 0 \leq a_1+\dots+a_n < a_{n+1}+\dots+a_{2n} < \dots < a_{n^2+1}+\dots+a_{n^2+n} \leq n. \]](http://latex.artofproblemsolving.com/8/1/e/81ea993db5f7dd9939dad89618079084093c8276.png)
As those sums are all integers and there are exactly strict 'less than'-signs, we can conclude 
for 
. Furthermore, note ![\[ 0 \leq \sum_{i=j}^{n+j-1} a_i < \sum_{i=j}^{n+j-1} a_{n+i} < \dots < \sum_{i=j}^{n+j-1} a_{n^2+i} \leq n \]](http://latex.artofproblemsolving.com/3/b/3/3b39e476d5e56626952883e1d3788982d9d2b729.png)
for 
. Now those are exactly 
strict inequality signs. Thus 
. Now we'll induct.
, as 
.
where we have -times the 
.
with 
-times the . As for that, we'll induct again to show ![\[ a_{(k+1)n+1}=a_{(k+1)n+2}=\dots+a_{(k+1)n+n-k-1}=0. \]](http://latex.artofproblemsolving.com/c/8/7/c87957d228afcaec026ef10b4c493c9509f3a814.png)
By 
we'd be done. Assume 
. Then ![\[ k+1=a_{kn+2}+a_{kn+3}+\dots+a_{(k+1)n+1} < a_{(k+1)n+2}+a_{(k+1)n+3}+\dots+a_{(k+2)n}+a_{(k+2)n+1} \leq k+1 \]](http://latex.artofproblemsolving.com/5/d/a/5da8f131f20acebfad91cd174ec14daff6508b7d.png)
by the Induction Hypothesis. Contradiction. Thus 
. So now assume ![\[ a_{(k+1)n+1}=a_{(k+1)n+2}=\dots=a_{(k+1)n+i} = 0 \quad \text{for all} \quad i \leq N \leq n-k-2. \]](http://latex.artofproblemsolving.com/d/9/e/d9ee554abd0f4c356ee085d0d0e7976244e9ae4c.png)
Again assume 
. Then 
Here we've used that 
Thus 
. With that 
and thus 
and so on. But the last line suggest ![\[ a_{(k+i+2)n+1}+a_{(k+i+2)n+2}+\dots+a_{(k+i+2)n+i+1} = i+2. \]](http://latex.artofproblemsolving.com/5/c/0/5c0930742ce568b990f928004188aee711c7b146.png)
But those are just 
terms. Contradiction. It's easy the verify that those indizes are well-defined for what we need. That ends the induction and thus also the other induction. It's easy to check that the claimed sequence indeed is a solution.
, let 
. It follows from the conditions given that 
, but each of these numbers is an integer from to inclusive, hence all these integers appear exactly once, and 
. So the first terms of the sequence are and the last terms are .
for 
. This is a strictly increasing sequence of integers from to inclusive. Let their sum be 
. Also,
. Here we used the fact that the first terms are and the last terms are . Thus the missing element in 
is precisely 
. Now we have shown that each sum of consecutive terms is uniquely determined, so there's at most one such sequence.
works, where these are blocks of terms, and in 
everything is except for the last terms.
th block of terms from left consisting of 
zeros and then ones. 
's such that the first term 
of each block has 
. There are 
such blocks and since they are disjoint, the blocks must have sums 
respectively from left to right. such that first term of each block has 
. There are such blocks and by the previous observation the sums of all terms in these blocks is 
. The sums on these blocks are distinct and so it must be that their sums are 
respectively from left to right.'s and 's from right to left and we see that we are forced to have the said configuration.
![[asy]
int n = 6;
for (int i = 0; i < n; i += 1) {
draw((n-1, -i)--(0, -i-1), gray(0.6));
}
for (int i = 0; i <= n; i += 1) {
draw((0, -i)--(n-1, -i), gray(0.6));
}
for (int i = 0; i < n; i += 1) {
for (int j = 0; j <= n; j += 1) {
label(string(i + j >= n ? 1 : 0), (i, -j));
}
}
[/asy]](http://latex.artofproblemsolving.com/b/c/4/bc4c8b8be268f08d59580ca97e9dfc762b36d7fe.png)
matrix as above; then by condition the row sums are 
in order. In particular the top row is all-zero while the bottom row is all-one.
, and let 
be an integer. Then the nonnegative integers![\[s_{i+n} - s_i, s_{i+2n} - s_{i+n}, \dots, s_{i+n^2} - s_{i+n^2-n}\]](http://latex.artofproblemsolving.com/e/2/b/e2b712c605a669c2fb314e2e119207cfdfcd50d9.png)
form a strictly increasing sequence and sum to![\[s_{i+n^2} - s_i = (0 + 1 + \dots + n) - (n - i)\]](http://latex.artofproblemsolving.com/2/7/6/27692627ef942936afa69edace78550cc28fde02.png)
and so must be exactly 
in order.
is forced, so in light of 
the entire sequence is forced.
be an integer. Find all sequences 
satisfying the following conditions:![\[ \text{ (a) } a_i \in \left\{0,1\right\} \text{ for all } 1 \leq i \leq n^2 + n;
\]](http://latex.artofproblemsolving.com/3/c/5/3c509ec2e9013e8d3be492c8eb44a7c33841b74e.png)
![\[ \text{ (b) } a_{i + 1} + a_{i + 2} + \ldots + a_{i + n} < a_{i + n + 1} + a_{i + n + 2} + \ldots + a_{i + 2n} \text{ for all } 0 \leq i \leq n^2 - n.
\]](http://latex.artofproblemsolving.com/9/7/d/97d2a467d1c0dc8594ec024c3bb9b8c87ee85b19.png)
Author: Dusan Dukic, Serbia
It is not hard to see that this works. Now we show that this is the only possibility.
denote the number of s in the block ![$[a_{k}, a_{k+n+1}].$](http://latex.artofproblemsolving.com/4/b/9/4b98e155b95afdee31c90ce0ddc42b227738b9c5.png)
Then the condition translates to 
for all 
For simplitcity, define 
by 
For instance, when 
has a unique value. Since the solution given before works, hence it would be the only solution.
for all 
In particular the first elements are zeros while the last elements are s. Thus by comparing terms we see
Noting that 
for all 
gives a unique value designation to each of 
In fact, this is 
for all 
and 
and hence conclude the result. 
Since there are only possible values of the sum of any consecutive terms of the sequence, this implies that 
In particular, the first terms must be and the last terms must be 
we have 
To show this, we induct backwards on 
let 
for 
Using our work before and the given inequality, we have 
Since 
for all 
the only solution to this inequality is 
for all implying the claim.
and let 
for By the given inequality, 
But by the inductive hypothesis, we know 
if 
and 
if 
and 
for 
implying the claim.
numbers from 
to 
, define 2-blocks, etc analogously. Additionally, let 
be the sum of the numbers from indices to 
. Notice that 
There are 
blocks total, and the only possible sums are to . Thus, 1-block has sum 0, 2-block has sum 1, and so forth.s in the 3-block would be pushed to 
and 
. in the 
-block appears at index 
, where 
for contradiction. Then, draw new boxes from 
to , and so forth. Evidently, 
which forces there to be 
ones in each of the new boxes. Observe now that 
is all ones for a total of 
ones (this is because the n+1-block is all ones). By similar logic, we need 
, but then this forces 
and so forth which is a contradiction.
th block has its earliest at 
, and as a result the boxes we draw in the inductive step will contain all the pushed-forward ones in the th block.
. The dashes represent the new boxes we draw in the inductive step, call them Crates 1, 2, and 3. Crate 1 has a sum of , and because there are three crates total, we know from the givens that Crate 2 must have a sum of 3, and Crate 3 has a sum of 4.
. However, because we know that box 4 must contain 
ones total, we know that the parenthesed area can only contain one at maximum. As a result, we are forced to draw the following: 
, which is a contradiction since Box 3 here has a sum of which is too much.
. There are sums, so the first is , the next is , etc. In particular, 
and 
.
is the sole nonzero 
among . This is because otherwise considering the sums 
for implies that each successive sum contains all nonzero elements of 
. A similar argument implies that only 
and 
of 
are nonzero. Continuing on this way, we can uniquely characterize the sequence as the one for which each with is nonzero iff 
. It is not hard to check this sequence works, so done.
,the base case is trivial and we obviously have one unique solution (
).
. Then, note that we have![\[0\leq s_0 < s_n < \cdots s_{(n-1)\cdot n} < s_{n^2} \leq n\]](http://latex.artofproblemsolving.com/b/b/c/bbca5bcc8fd6b213e48e04d4f41dfbe25e00b2bf.png)
Thus, since these values are integers, and we have choices and values, we have 
for all . be the smallest such that 
. Note that we are guaranteed that 
. Thus,![\[1\leq s_{i-n}< s_i < s_{i+n}\ldots s_{i+(n-2)n}\leq n\]](http://latex.artofproblemsolving.com/c/0/c/c0ce8be58fe14085a4ca7a927e7bc065eb1e1200.png)
There are choices, and values, so we have 
. Importantly,![\[\sum_{k=0}^{n} s_{nk} = \sum_{r=-1}^{n-2} s_{i+nr}\]](http://latex.artofproblemsolving.com/6/d/b/6dbf373c099ce9d89468fc127f1f97d525fd9a61.png)
Thus, since the LHS represents all 1s, all 1s must also be in the 
ranges, so there cannot be any 1s in between 
and 
, but this is absurd because 
guarantees that for all 
, 
. Thus, we must have that ![\[i+(n-2)n=n^2 \Longrightarrow i=2n\]](http://latex.artofproblemsolving.com/d/b/8/db897d78d55ee791e1e7068ddbfd6d9ea8b58626.png)
By considering 
![\[2\leq s_{2n-1} < s_{3n-1} < \ldots < s_{n^2-1} \leq n\]](http://latex.artofproblemsolving.com/f/a/0/fa06d605f9f7bce7d6b25db53c978fc5f37c61d1.png)
we get that 
. Thus, we must have that 
and so on so that 
for all 
. Thus, we can now remove 
and 
, at which point we have reduced to the case because we've removed exactly 1 from each series of . Thus, by the inductive hypothesis there is exactly one solution.
for 
if and only if 
.
groups of numbers each. Using the second condition for multiples of , we get that the amount of s in a group increases with the position of the group. As there are only possible values for the number of s in a group, the th group will have 
ones.th group consisting of ones at the end of the group, and zeros at the beginning where needed. This can be shown to work. We will prove this using induction. It is easy to show this for 
.
. We will prove the statement for 
., the last number of every group other than the first must be a .th group is , where 
. Plugging in 
into the second condition gives us that the sum of the last number of the 
th group and the first numbers of the th group is less than the sum of the last number of the th group and the first numbers of the 
st group. However, the former is at least and the latter is at most , so equality must hold, meaning all the ones in the st group are in the first numbers. This means that the last number in the th group is .
, is , which is impossible. 
numbers 
for 
in order. We claim that this sequence satisfies both conditions for . Indeed, the first condition is obviously satisfied. The second condition is equivalent to the second condition for the sequence because we simply take out the last number out of a group (for the sequence) for each side, which is by the claim. for . All other values are already determined, and combining these with the fixed values for for , we get the answer stated above. The induction is complete, and we are done.
. Trivially, we obtain 
, due to the second condition. It follows that 
or that for all 
. Now, we have that![\[\sum_{k=0}^nb_{kn+1}=\sum_{k=1}^{n^2+n}a_k=\frac{n(n+1)}{2}=s_1\]](http://latex.artofproblemsolving.com/2/7/2/27271df64009c03f170809a76ae35f913d8032e1.png)
![\[\sum_{k=0}^{n-1}b_{kn+2}=\sum_{k=2}^{n^2+1}a_k=s_1-(n-1)=s_2\]](http://latex.artofproblemsolving.com/4/5/4/454f43b9cbcf5b9fdd4fdabe612e9d14b70e0324.png)
![\[\vdots\]](http://latex.artofproblemsolving.com/7/6/4/76403adfdd35fb846675aaeaac92daec680a4fba.png)
![\[\sum_{k=0}^{n-1}b_{kn+n}=\sum_{k=n}^{n^2+n-1}a_k=s_1-1=s_n.\]](http://latex.artofproblemsolving.com/8/b/2/8b20375e3617fdbf89727ca08c08509c4f0ab86f.png)
Now, consider the sequence 
for some 
. It's easy to see that this sequence contains every number from to , inclusive, except for one. From our sums earlier, we obtain that this number is actually 
.
to 
contains copies of and 
copies of , in sorted order. We show this by induction. The base case (
) is trivial. Now, suppose that 
satisfies the given. Then clearly we have 
for all except for 
, in which case we obtain 
. This implies the result.
. We show this by induction; the base case is trivial. Consider 
and the sequence 
to 
. Clearly this sequence contains all of the s that contribute to the sum in . It follows that all values from 
to 
are equal to . However, is equal to , which implies that the elements from 
to 
are equal to . Therefore, we are done. 
Note that 
so 
In particular, 
Let 
, then 
and 
which means that this sequence contains every integer from to excluding 
Thus, from we get the same construction everyone else has posted.
terms are all 0, in the next , only the last term is 1, in the next , only the last 2 terms are 1, and so on, until in the last , all terms are 1. This sequence clearly works. must contain strictly more 1's than the previous block. This implies that there must be no 1's in the first , one 1 in the next , two 1s in the next , and so on until ones in the last . rows of each so that when the grid is read by rows, it gives the prefix sum sequence. Note that by our earlier observation, the last column must contain 
Additionally, condition (b) is equivalent to each column forming a strictly convex sequence. Now, consider the second to last column of these prefix sums. This column must end in 
since the final terms are all 1's, so the final row of this grid contains consecutive integers. However, note that the minimal convex sequence starting with 
with a length of ends with 
, contradiction, so the second to last column must start with 
instead. Note that consecutive prefix sums can differ by no more than 1, so the second to last column must be 
We can then repeat this argument with previous columns. For example, in the third to last column, it must start with 
since the minimal convex sequence starting in 
reaches 
on term , but it needs to end in 
so it must start in , and we can also use the argument that it can never fall behind the second to last column by more than 1. Repeating this argument with all previous columns, we get a unique possible grid of prefix sums, from which we can uniquely recover the original sequence, and since the sequence we showed earlier works, we are done.
, 
, and so on. The only such sequences are those with 
, where there are ones consecutively.
contains a strictly greater number of ones than any previous subsequence; by Pigeonhole it follows that it must contain exactly ones. Now, suppose for the sake of contradiction that there exists a minimal index for which 
contains a one before index 
in that subsequence. Call this index . digits leading up to index (spanning two subsequences) contains at least ones because due to the condition 
, all zeroes at the tail of the previous subsequence are contained in these digits. This means that there are at least ones in the digits immediately following; in other words, all ones in the subsequence 
must fall in these digits, and thus strictly before the index in that sequence. also satisfies the aforementioned condition, so inductively, the list 
must also satisfy this condition. But this is absurd, because clearly there are no elements of that are before the element indexed 
.
blocks of digits. The first block will be of zeros, the next will be of zeros with the last digit being , and the second block will have the last two digits as , and so on and so forth. E.g. for 
, we have the sequence 
. numbers from any block of numbers(not necessarily the ones specified in the previous definition, a "block" could mean index to index ), we "exchange" a zero for a , adding one to the sum. numbers into disjoint blocks of (there is only one way to do this), we have that the sum of the first block must be , the next is , and so on and so forth, since these sums must be increasing. Using this and filling out the sequence from left to right, we find that we must have the configuration, and we are done. 
for 
denote the sum 
. Notice that![\[S_{1,n}<S_{n+1,2n}<S_{2n+1,3n}<\dots{}S_{n^2+1,n^2+n}\]](http://latex.artofproblemsolving.com/8/4/c/84c066be728a7e4840786c4c5648c19f98e65c7d.png)
which means that 
for any integer from to inclusive.
, and 
. Notice that since 
, we have that exactly one of the values between 
and 
is , and because 
, we also must have that 
.
. From the condition, we have that![\[S_{2,n+1}<S_{n+2,2n+1}<\dots{}S_{n^2-n+2,n^2+1}\]](http://latex.artofproblemsolving.com/8/d/3/8d3fa6a7dd534bf12d63859529c3a5addb15ff4d.png)
and since 
, we must have that 
. However, this implies that 
, a clear contradiction.
for some 
, we will find that it implies that 
, a contradiction. Therefore, we must have that . Similarly, we can do this for the other blocks of binary with sums , , 
, by focusing on the first that appears in that block, and we can conclude that it will always be 
. Therefore there is only one sequence, and we are done. 
groups of integers from beginning to the end. We can see that since there are possible values of the sum, the th group must sum to . We claim that the only configuration is when those 's are at the end of that group. Specifically, for 
our configuration is: ![\[00000001001101111111\]](http://latex.artofproblemsolving.com/1/c/9/1c9791d1f54645ffd0fd17af102863bc9a1f1e16.png)
where 
where 
and 
are integers with 
and 
.
, then we can compare the groups of numbers from ![\[ \{a_{z+1} \ldots a_{n+z} \}, \{a_{n+z+1} \ldots a_{2n+z} \} , \ldots \{a_{n^2 - n +z+1} \ldots a_{n^2 + z} \} \]](http://latex.artofproblemsolving.com/d/7/7/d77b1951056de106d8eb24fbde60e175b45c08f0.png)
. We can see from our inductive step that for each of first 
terms they equal every integer from to 
we can see that the term that contains is (also from our inductive step). Since there are terms in total, we can see that the next 
terms must occupy every integer from 
to .'s would be 
. Simplifying this we can see that this is equal to 
. However, we know that the total number of 's is 
. Contradiction. 
. The condition implies ; in particular, since these values range from 0 to n, and there are n+1 groups, each group corresponds s.t. 
(rigid!). We proceed by induction to show that there is one unique sequence, namely the sequence starting with the first n numbers 0, then the next string of n numbers having n-1 0s, with the last number being a 1, etc. by increasing the number of 1s that end in a string with length n. It's easy to check that this works. The base case n=1 is easily verified because the condition only needs to hold for i=0, meaning so it's just unique. (rigid!), along with 
implying 
. Also, noting that the value of i makes 
contain , meaning it's at least 1, we get 
since there are n choices and n values for 
; in particular, there cannot be any 1s in ![$(i+(n-2)n,n^2+n]$](http://latex.artofproblemsolving.com/e/8/6/e86be9ae5be9549c593417d2e67b4c44d2568c18.png)
(since otherwise the sums are nonequivalent), which implies, along with the fact that 
, that we must have 
(otherwise there is a 1 in between).
contains and another 1, since it has at least as many 1s as 
minus 1 (if were to equal 1). So we have the bound 
in the same manner inductively (next we would take 
), we can get that 
. Now, we can erase 
, which doesn't effect the condition, so we are done, because this has reduced the problem by 2n, which is indeed 
into the hypothesis 
. We already know that the terms that we erased did satisfy our claimed sequence, whence nothing changes. 
, which is why i used base case n=1; probably n=2 shouldn't be too nontrivial though even though its SIX VARIABLES.
It is clear that this sequence clearly satisfies the required condition since if 
are 1s for 
, then so are 
an in addition so is 
confirming the strict inequality. We shall then show that this is the only sequence which satisfies the given conditions.
. There exists no terms such that 
. such that . Let be the minimum such index. Let 
(
).![\[a_1+\dots+a_n < a_{n+1}+\dots + a_{2n} < \dots < a_{n^2}+\dots + a_{n^2+n}\]](http://latex.artofproblemsolving.com/e/b/b/ebb6195fa75f14514173340c6ba3fa0e2f40dde2.png)
This means that since we only have 0s and 1s as terms, 
for all 
. is the minimum such index, and 
,![\[a_{m-n+1} + \dots + a_{m-1} + a_m = (k-2)+a_{(k-1)n+1}+\dots + a_m = k-1\]](http://latex.artofproblemsolving.com/8/8/d/88db29d850a9a850a3f89e88595d6c0087930c2a.png)
Then, we have the following chain of inequalities,
Note that since these are strict inequalities the value of each sum must be atleast 1 more than the previous (this is what we use below).
as 
. This then gives us that![\[a_{kn+1} + \dots + a_{m+n} > 2\]](http://latex.artofproblemsolving.com/4/b/f/4bfa50e1aa814420cf2c7b33b0f7f0d1cb10a739.png)
Since the sum 
again this gives![\[a_{m+n+1} + \dots + a_{(k+1)n} < k-2\]](http://latex.artofproblemsolving.com/f/e/8/fe88e37f29e47840f33daeccfd785d7677580da1.png)
Again using the sum of 
we must have![\[ a_{(k+1)n +1} + \dots + a_{m+2n} > 3\]](http://latex.artofproblemsolving.com/0/2/f/02f6376151e72695925db7ac3bea047ee38abafa.png)
we then continue likewise. If it is indeed possible to have 
, then there must exist possible values for all when . Thus, this continues until the last bath of terms, giving us that![\[a_{n^2} + a_{n^2+1} + \dots + a_{n(n-k+1)+m} > n-k+2\]](http://latex.artofproblemsolving.com/1/1/b/11b17aac60c41fc190d7ef0b681325d8421b7a39.png)
But, note that since , we also have![\[a_{n^2} + a_{n^2+1} + \dots + a_{n(n-k+1)+m} < 1(m-nk+n)+1 = kn -n + p -nk + n +1 = p+1 \leq n-k+2\]](http://latex.artofproblemsolving.com/8/1/e/81edd92330aacecd491c3521e59573fd3e4a1837.png)
which is a clear contradiction to the previous inequality. Thus, clear there cannot exist such .
:![\[0000~0001~0011~0111~1111.\]](http://latex.artofproblemsolving.com/3/3/b/33b67572f216994b0ecd8be0640eb830aee33669.png)
block as a block of consecutive terms starting with , where 
. Notice the 
blocks are fixed up to permutation, as the minimum possible sum is 0 and the maximum is . blocks are also fixed up to permutation. Since the first/last blocks must be all 0s/1s, the total sum of all blocks, for each 
, will be 
, which can only be written as the sum of distinct integers between 0 and , inclusive, as![\[0+1+2+\ldots+(n-k-1)+(n-k+1)+\ldots+n.\]](http://latex.artofproblemsolving.com/3/6/5/3659a01bfc336f3b64a4b65c3c4cb7a3dde5192c.png)
to be refer to the consecutive elements of the sequence 
starting at .
being 
0s followed by 1s., if is then 
is also , if is we only have 
if 
. We see that for each element of the block, the corresponding element in the next block is at least the current element, and we are also guaranteed to have an element with index 
in each block, since it's just things that are mod 
, so the inequality is strict.
. We see all the blocks of starting with have distinct sums, so they must be 
in that order, so each block of that form has 1s. We show each of these blocks must end with . Call these block ending indices "good". Consider the first good index that is not a and is not index . If the index is 
for 
, we know the block starting with 
contains 
1s, and the block starting at contains at most the number of 1s as the block starting with 
, which is , so the property cannot be satisfied. If 
, let the position of the unique in that block be 
. Now we inductively prove that each block starting at 
has 1s, as well as all elements from 
to 
being 0. The base case of 
is obvious, then clearly if it is true for 
we need at least 1s in the block , we know cannot have anything positive from to 
, but for the sum to be at least we then need all 1s in the block starting at 
to be in the block starting at , meaning that there is nothing in the range 
to , since all 1s were used up in the first elements of the block, which also forces the sum to be exactly . Now at some point we end up with all the s in the block starting at in the first elements of the block, but there is eventually going to be more than 1s in the block, contradiction. Thus no good indices can have a . elements. The property still must hold for the remaining indices, and note that each block contains exactly one good index, so we can just remove all good indices and the property should still hold for blocks of size . Since we are also left with 
elements, we can just induct.
"blocks" of numbers, with the th block having 's at its end. For, example, for it would be: 
Then 
for 
Therefore there is a total of 
's in the sequence. Meanwhile, for 
we have that 
so this list is the list 
but with one of these numbers not appearing. However, note that their sum is 
hence because 
goes up to index 
there are still 
's at the end (since 
). Therefore, 
is the list 
but with 
missing. is a sequence with 's, then 's, 's, etc. until 's, and finally one 
so the increment depends on the difference between consecutive 
s. Then, going through the sequence manually would finish. QED
if 
for some 
and 
otherwise. For concreteness, we provide the sequence for 
below; splitting the sequence into "chunks" will make the construction more clear: 
One can check (say by making a table) that this works.
These sums hence take on distinct values, but there are only possible values for each sum, those being the integers between and inclusive. Hence 
and 
As such, for 
and for 
Additionally, we see that each sum counts the number of ones in the sum, so there are a total of 
ones.
we can say something similar about the sums 
These sums take on distinct integers between and 
inclusive. For brevity, let 
Then 
Given that the 
are integers in strictly increasing order, this implies that there is exactly one way to assign values to each of the . As such, this implies that for all 
we have that is always equal to a fixed value. From this, since 
implies for 
we uniquely determine the sequence 
matrix with the elements in order. Then, the only sequences that work are ones where the last elements of the th row are 1 and everywhere else is 0. For example, for we have
, we have the inequality 
This means that we must have 
th row must contain 1s for all 
. Now, we start with the second row. If the is in some entry 
, then we must have 
which means that both of the 1s must be in the first 
entries of the second row. We can then repeat the process with 
and we would get that the three 1s in row 4 must all be in the first entries. Repeating, eventually we arrive at row 
where all 1s in row are in the first entries, then repeating the process we must have 
1s in the first entries of the 
nd row and that is impossible. Thus, the first 1 must be in the th entry of the 2nd row. Then, if 
we could consider the shortest sequence of length ending at 
and take the replica of that sequence shifted up by . Then, we get that the 4th row must contain 4 1s, and that's impossible. Thus the th entry of row 3 must be a 1. Similarly, the th entry of every row besides the first one must be a 1.
where the th row has sum for all . Now, for any 
in the original matrix, we have that there is exactly one element (the one in the last column) removed from the left side of the inequality, and one element (the one in the last column) removed from the right side of the inequality. Since we have established that those must both be 1, the inequality still holds without them. Thus this smaller matrix must satisfy every condition in the problem. We can now see that this is the only possible construction by induction.
grid so that each row of the grid has elements and represents a consecutive sum. We write 
for 
.
if and only if 
, which gives a pyramid of s whose first row is all s and last row is all s.
for all 
, which allows us to induct downward on the condition by deleting the first row and last column. rows and only possible row sums, the sums of the numbers in the th row must be .
for some . Then take maximal such that . Then we have that![\[
i = a_{i,1} + \dots + a_{i,j} + a_{i-1,j+1} + \dots + a_{i-1,n} <
a_{i+1,1} + \dots + a_{i+1,j} + a_{i,j+1} + \dots + a_{i,n} =
a_{i+1,1} + \dots + a_{i+1,j}
\]](http://latex.artofproblemsolving.com/5/4/2/542edd199214e21a6173116203e8b8031db9f7ee.png)
so 
, and remains the sum. Repeating this, we get a contradiction when 
. This finishes.
if 
if 
is greatest element satisfy 
and 
because 
Contradiction!!
1's from 
to 
.
,
,
,
.
would be![\[00000\text{ }00001\text{ }00011\text{ }00111\text{ }01111\text{ }11111\]](http://latex.artofproblemsolving.com/e/9/3/e93001cf781f87dfeb61989e59d331ac865cd0ec.png)
since everything is 
,
.
to 
.
denote the number of ones from 
to 
.
1s. In particular, 
.
.
1's from 
to 
.
1's from 
to 
ones from 
to 
.
as desired, completing our induction.
.
.
,
places since everything is 0's and 1's by the first condition. Hence, we get a contradiction, and 
.
to be the remainder when 
.
is nonnegative.
to be 
and let 
denote the minimal amount 
.
give 
.
.
.
and 
,
.
and thus 
.
and 
(
,
,
,
with equality iff 
.
,
.![$[(k-1)n+1, kn]$](http://latex.artofproblemsolving.com/3/6/c/36cb12a4d2f5e5e1c6a1025ce92751256bc23232.png)
,
and there must be exactly 
for all 
,
.
,
,
.
is the minimal value 
from above. Thus, 
(
,
,
for all 
Therefore, 
from the second condition. We also have 
and so on. This implies that the sequence 
is increasing. However, the lower bound of 
is 
,
where 
We also know that 
This means that for all positive integers 
,![$$b_{y}+b_{n+y}+\dots+b_{n^2-n+y}=\sum_{j=1}^{n^2+n}[a_j]-\sum_{k=1}^{y}[a_k]-\sum_{l=n^2+y+1}^{n^2+n}[a_l]$$](http://latex.artofproblemsolving.com/2/f/4/2f44314057dff9ff882f942b08d062947d21effb.png)
because 
Because we have that 
and they are all integers, the lower bound is 
This means that 
if 
and 
This means that, for any nonnegative integer 
,
,
because 
if 
,
because 
This means that 
to 
for nonnegative 
This means that 
except for 
,
is 
with 
and 
and positive integer 
,
As we have constructed and proven all 
-- it's the one with 
,
,
,
,
.
,
is all zeroes until one point, and then it switches to all ones. Thus, for any 
,
.
,
,
,
.
for some nonnegative integers 
with 
Since 
,
.
are the same as 
,
and 
,
(consequently, 
)
,
and 
are the same. However, 
and 
,
must be of this form. Firstly, note that 
Thus, since the 
,
,
.
,
,
,
for 
and 
for 
since we have proven that 
,
for which 
.
for which 
for 
are all 
for 
are all 
)
Then, we have that 
so since the 
,
.
is 
,
are all zero, and 
,
,
.
,
absurd since 
as established before. Thus,