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

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

Report

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

Report

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
all contrib requests added I usually get to posting every night after running on the treadmill and showering, posting my favorite problem(s) I did during the day.
by shiningsunnyday, Jun 16, 2016, 4:37 AM
Since problems is plural, he might post multiple problems through different posts in one day...
by zephyrcrush78, Jun 15, 2016, 8:37 PM
hi can i have contrib?
by wu2481632, Jun 15, 2016, 8:36 PM
Hello it is called problems of the DAY
by Temp456, Jun 15, 2016, 8:17 PM
10th shout lol
How often will this blog be updated?
by zephyrcrush78, Jun 15, 2016, 5:24 PM
why are we counting shouts

contrib pls
by MathAwesome123, Jun 15, 2016, 2:55 PM
eighth shout
contrib pls
by skipiano, Jun 15, 2016, 2:21 PM
seventh shout
Can I be contrib?
Though probably not because it's not like I'll post anything anyways :/ :/
by zephyrcrush78, Jun 15, 2016, 1:20 AM
sixth shout

new goal: get the shouts that are congruent to 1 mod 5
by DeathLlama9, Jun 15, 2016, 12:33 AM
fifth shout >
by budu, Jun 14, 2016, 10:04 PM
4th yay
by EpicSkills32, Jun 14, 2016, 9:10 PM
third shout
by skipiano, Jun 14, 2016, 2:35 PM
Second shout
by zephyrcrush78, Jun 14, 2016, 12:06 AM
omg yesssss
by DeathLlama9, Jun 13, 2016, 2:19 PM

270 shouts

Problems of the day

A sequence of 0s and 1s

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

2 Comments