Let n > 1 be an integer.
Find all sequences a[1], a[2], ..., a[n^2+n] satisfying the following conditions:
(a) a[i] in {0, 1} for all 1 <= i <= n^2+n
(b) a[i+1] + a[i+2] + ... + a[i+n] < a[i+n+1] + a[i+n+2] + ... +a[i+2n]
    for all 0 <= i <= n^2−n.

---------------------------------------------

(a) just states they are binary sequences.
(b) is can be phrased as
* count(a[i : i+n+1]) < count (a[i+n+1 : i+2n+1]) (python slice notation)
* Let's reindex it from zero, for convience, b[0] =def= a[1], b[i] =def= a[i+1], and
  count(i,j) =def= count(b[i:j])
* It can be chained:
  * count(i, i+n) < count(i+n, i+2n) < count(i+2n, i+3n) < ...
  * count(0,n) < count(n,2n) < ... < count(n^2, n^2+1)
  * There are n+1 numbers in the chain, all must have different (strictly increasing) values,
  * so count(in, (i+1)n) = i.

All the other chains have only length 'n', so one number can be missing in them.
Let's try n=2, separated by | in multiples of n, first just to satisfy the basic chain:
(1) 0 0 | 0 1 | 1 1
or
(2) 0 0 | 1 0 | 1 1
Does these sequences satisfy the other chain: count(1,3) < count(3,5)?
Sequence (1) does, sequence (2) does not.

n=3, the analogous to the working case in n=2:
0 0 0 | 0 0 1 | 0 1 1 | 1 1 1
does it work in general:
* count(1,4)=0 < count(4,7)=1 < count(7,10)=3: True
* count(2,5)=0 < count(5,8)=2 < count(8,11)=3: True
It works.

Questions:
Q1: Is this "first zeroes, then ones" working in general? (looks as an easy check)
Q2: Is there any other sequence satisfying the condition?

Let's look on Q2, it seems more interesting.
If I start with
0 0 0 | 0 1 0 | ...
Then by moving the window from
0 0 0 | 0 1 0 | ? ? ? |
         ^-------^
to
0 0 0 | 0 1 0 | ? ? ? |
           ^-------^
I cannot increase the count, maybe it has decreased.
Case analysis:
* the count stayed the same, then b[7] = 0:
  0 0 0 | 0 1 0 | 1 0 1 | 1 1 1
  the rest of the sequence is forced.
  Does it satisfy the condition?
  * count(1,4)=0 < count(4,7)=2 < count(7,10)=2: False
  * count(2,5)=1 < count(5,8)=1 < count(8,11)=3: False
  Hm, even both chains are broken.
* the count decreased, we know
  * count(4,7), count(5,8) in {1, 2}
  * so count(4,7) = 2, and count(5,8) = 1 -> count(5,8) = 1
  0 0 0 | 0 1 0 | 1 ? ? | 1 1 1
  * count(4,7) = 2, so count(7,10) = 3
  0 0 0 | 0 1 0 | 0 1 1 | 1 1 1
  contradiction.

Alternative approach to n=3, b[4]=1:
* count(2,5)=1 < count(5,8) < count(8,11):
  count(2,5) forces the other values:
  count(5,8)=2, count(8,11)=3
* count(8,11)=3, so b[8] = 1
* count(5,8)=2, count(6,9)=2, so b[5] = b[8], so b[5] = 1
  0 0 0 | 0 1 1 | ? ? 1 | 1 1 1
  contradiction, b[5] must be 0.

This could work for general n.
Assume b[n+i]=1 for 0 <= i < n-1.
* count(i+1, i+1+n) = 1, it forces the chain
  count(i+1+n, i+1+2n) = 2,
  ...
  count(i+1+kn, i+1+(k+1)n) = k+1,
  ...
  count(i+1+(n-1)n, i+1+n^2) = n,
  Therefore, b[i+1+(n-1)n : i+1+n^2] = 1,1,...,1
  Since
  * count(i+1+kn, i+1+(k+1)n) = k+1 = count((k+1), (k+2)n),
  we get
  * count(i+1+kn, (k+1)n) = k+1 = count(i+1+(k+1)n, (k+2)n),
  using this, we get (by induction from the end)
  * b[i+1+kn : (k+1)n] = 1,1,...,1
  until we reach b[i+1+n : 2n], leading to b[2n-1]=1, contradicting b[n+1]=1.

So in general case, we are guaranteed to have b[2n-1]=1.
And now the third block... it seems harder.
Couldn't we use some induction? Convert it to the previous case with n -> n-1?
* It can be possible if we prove that for general k: b[kn-1] = 1
  * then the same sequence without the last bit (equal to one) in every block,
    and without the last block
    satisfies the requirements for (n-1)-sequence.
* We have already proven that b[kn-1] cannot be zero for k=2.
  Now, we want to prove something similar for arbitrary k>=2.

Suppose b[kn-1]=0.
Then count((k-1)n-1, kn-1)...
* well, we can assume that we have already proven that b[(k-1)n-1]=0 (we use induction).
... count((k-1)n-1, kn-1) = count((k-1)n, kn) = k-1.
* this forces: count((k'-1)n, k'n) = count((k'-1)n, k'n) for every k' >= k.
* therefore b[n^2-1] = 1
* but also the equality:
  count((k'-1)n, k'n) = count((k'-1)n, k'n)
  guarantees: b[(k'-1)n-1] = b[k'n-1]
  which leads to a contradiction.

It is proved but it still seems overly complicated
* induction for n (I like this part)
  * induction from the beginning (b[kn-1]=0)
    * then count((k'-1)n, k'n) = count((k'-1)n, k'n)
    * then induction from the end (b[kn-1]=1), or from the beginning, whatever...

Couldn't we simplify the inner part?
* For example, proving in general, that b[kn]=0 for k < n?
  (it is dual to proving that b[kn-1]=1)
* If not, take the first k where b[kn]=1.
  so count((k-1)n+1, kn+1) = count((k-1)n, kn)+1 = k-1+1 = k
  I don't see how it is helping with simplification.
  I will just keep the original proof

I should also verify that the construction is valid.
In the construction, it is true for almost all 'i' that 
b[i+n] = b[i] with the exceptions of
i = n-1, 2n-2, 3n-3, ... k(n-1) ... n^2-n
For every i from the exception set, we have b[i+n] > b[i]
So it is sufficient to check that every slice
b[j : j+n] contains at least one 'i' from the exception set.
It is actually obvious, every such slice has an equal size n,
and the distances within the exception set (and its borders) are
n-1.

Could we use the approach of the exception set for finding a nicer proof
of the uniqueness of the solution?
But in general, it does not have to hold that b[i+n] = b[i] with some
exceptions where b[i+n] > b[i]. We could also have
b[i]=1, b[i+n]=0.
So, let's define a sequence c of length n^2 by: c[i] = b[i+n]-b[i].
for i within 0 <= i < n, we know b[i] = 0, b[n^2+i] = 1.
Therefore c[i]+c[i+n]+...+c[n(n-1)+i] = 1.
In total, the sum of c is equal to n.
How do we translate the condition count(i, i+n) < count(i+n, i+2n) to c?
* sum(c[i:i+n] >= 1) for i = 0,1,...,n^2-n.
* so the sum on an interval of c is require 'c' to have a big total sum
  while we know that the overall sum is only n. That is
  sum(c[in:(i+1)n]) = 1.
  * (note that we are just translating facts that we already knew about b so far)
* if we knew that there are no -1's in c, it is clear that the ones must be distributed
  in (n-1) intervals. But there hypothetically could be -1's allowing also more than n ones.
* possibly, I should also translate the rule that the original sequence contains only 0 or 1.
  it can be expressed as c[0]+c[1]+...+c[k] in {0,1} which is not so beautiful condition.
* but if I ignore the condition on binary original sequence, can I find a counterexample?
  -1 1 1 | 0 0 1 | 1 0 0
  yes. Wait, what? I don't even need -1's, the "clear" fact was untrue.
  0 0 1 | 0 0 1 | 1 0 0
  * Ah, it is because there are ones with the difference exactly 'n', which is breaking
    the (a) condition (original sequence is binary).
  * but once I forbid ones distant exactly 'n', then it is really "clear" that they have to have
    distance n-1.
* Is there a counterexample on c with the only condition that two ones cannot have distance n?
  -1 1 1 | 0 1 ...
  I am failing to find a coutnerexample for n=3, what about n=4? Start with the working solution.
  0 0 0 1 | 0 0 1 0 | 0 1 0 0 | 1 0 0 0
  and try to modify it.
  -1 1 0 1 | 0 0 1 0 | 0 1 0 0 | 1 0 0 0
  This works. No ones with distance n, but there are ones with distance 2n
  -1 1 0 1 | 0 0 1 0 | 0 1 0 0 | 1 0 0 0
     ^                   ^
  So is this the right condition? No ones with distance kn without a -1 in between
  (also in a distance of a multiple of n)
  * Yes, this condition guarantees the original condition (a)
* Hm... no clean solution poping out of it so far. I will stick with the "ugly" one.