A sequence of 0s and 1s

by jdeaks1000, Oct 27, 2016, 9:55 AM

ISL 2007 C1 wrote:
Let $ n > 1$ be an integer. Find all sequences $ a_1, a_2, \ldots a_{n^2 + n}$ satisfying the following conditions:
\[ \text{ (a) } a_i \in \left\{0,1\right\} \text{ for all } 1 \leq i \leq n^2 + n;
\]
\[ \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.
\]Author: Dusan Dukic, Serbia

For $1\leq k\leq n^2-n+1$, let $b_k = a_k + a_{k+1} + \cdots + a_{k+n-1}$. It follows from the conditions given that $b_1<b_{n+1}<\cdots <b_{n^2+1}$, but each of these numbers is an integer from $0$ to $n$ inclusive, hence all these integers appear exactly once, and $b_1=0, b_{n^2+1} = n$. So the first $n$ terms of the sequence are $0$ and the last $n$ terms are $1$.

Let $S_i = \{ b_i, b_{i+n}, \cdots b_{i+n^2-n}\}$ for $2\leq i \leq n$. This is a strictly increasing sequence of $n$ integers from $0$ to $n$ inclusive. Let their sum be $T$. Also,
$a_1+a_2+\cdots +a_{n^2+n} = 0+1+\cdots +n= T + (n-i+1)$. Here we used the fact that the first $n$ terms are $0$ and the last $n$ terms are $1$. Thus the missing element in $S_i$ is precisely $n-i+1$. Now we have shown that each sum of $n$ consecutive terms is uniquely determined, so there's at most one such sequence.

It is obvious that $B_1B_2\cdots B_{n+1}$ works, where these are blocks of $n$ terms, and in $B_i$ everything is $0$ except for the last $i-1$ terms.

Comment

2 Comments

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Darn the partial sums idea is pretty clever. Good job jdeak :coolspeak:

by shiningsunnyday, Oct 30, 2016, 4:39 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Thanks :) I also solved the C2 on that Shortlist, it's easier than the C1 I think! Will try get a solution typed up soon. C3 looks hard :(

by jdeaks1000, Nov 2, 2016, 6:16 AM

To share with readers my favorite problem I came across today :) (Shout for contrib.)

avatar

shiningsunnyday
Archives
- May 2017
Shouts
Submit
  • this guy is an absolute legend. much love wherever you are Michael

    by LeonidasTheConquerer, Aug 5, 2024, 9:37 PM

  • amazing blog

    by anurag27826, Jun 17, 2023, 7:20 AM

  • hi i randomly found this

    by purplepenguin2, Mar 1, 2023, 8:43 AM

  • can i be a contributor please?

    by cinnamon_e, Mar 10, 2022, 6:58 PM

  • orzorzorzorzorzorozo

    by samrocksnature, Jul 16, 2021, 8:25 PM

  • 2021 post

    by the_mathmagician, May 5, 2021, 3:28 PM

  • Let $ ABC$ be an equilateral triangle of side length $ 1$. Let $ D$ be the point such that $ C$ is the midpoint of $ BD$, and let $ I$ be the incenter of triangle $ ACD$. Let $ E$ be the point on line $ AB$ such that $ DE$ and $ BI$ are perpendicular. $ \

    by ARay10, Aug 25, 2020, 5:55 PM

  • Nice blog! :)

    by User526797, Jan 12, 2020, 4:48 PM

  • oh my gosh it's been so longggggg.... contrib? what does that mean?

    by adiarasel, Dec 1, 2019, 8:31 PM

  • 2019 post

    by piphi, Aug 10, 2019, 6:32 AM

  • hi contrib please

    by Emathmaster, Dec 27, 2018, 5:38 PM

  • hihihihihi contrib plzzzzz

    by haha0201, Aug 20, 2018, 3:58 PM

  • contrib please

    by Max0815, Aug 1, 2018, 12:35 AM

  • contrib /charmander

    by mathmaster2000, Apr 16, 2017, 4:59 PM

  • for contrib

    by SomethingNeutral, Mar 30, 2017, 7:57 PM

270 shouts
Tags
About Owner
  • Posts: 1350
  • Joined: Dec 19, 2014
Blog Stats
  • Blog created: Jun 11, 2016
  • Total entries: 193
  • Total visits: 30959
  • Total comments: 579
Search Blog
a