Contrib Combo [LAMPS]

by DeathLlama9, Jul 14, 2016, 2:41 AM

Furious Readers wrote:
No posts in three days? It's problem of the day, not problem of the three-day period!

Shiningsunnyday, having noticed this, has asked me to post on his blog. As combo is my only good subject, I will post a combo problem.
2006 ISL C1, France wrote:
We have $ n \geq 2$ lamps $ L_{1}, . . . ,L_{n}$ in a row, each of them being either on or off. Every second we simultaneously modify the state of each lamp as follows: if the lamp $ L_{i}$ and its neighbours (only one neighbour for $ i = 1$ or $ i = n$, two neighbours for other $ i$) are in the same state, then $ L_{i}$ is switched off; – otherwise, $ L_{i}$ is switched on.
Initially all the lamps are off except the leftmost one which is on.

$ (a)$ Prove that there are infinitely many integers $ n$ for which all the lamps will eventually be off.
$ (b)$ Prove that there are infinitely many integers $ n$ for which the lamps will never be all off.

Part A

Part B
This post has been edited 2 times. Last edited by shiningsunnyday, Jul 14, 2016, 2:45 AM

Comment

3 Comments

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
^^THIS GUY IS BEAST.

I'll try this problem on the plane tomorrow or sometime. :P

by shiningsunnyday, Jul 14, 2016, 4:56 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
oops forgot motivation

Basically for both parts you just list a ton of sequences, get that 2/4/8 work (while 3/5/6/7) don't, so it's probably powers of two.

Trying sixteen, eventually you get to 0000000110000000, which is just two 10000000s stuck together! This forms a key component of our inductive proof.

For the second part I tried multiples of three, then numbers of the form $2^k + 1$, but this proof is probably the best. Just list out a bunch of sequences and note that they always have an even number of "on" lamps (e.g. 7 - 1000000, 1100000, 0110000, 1111000, 0001100, etc.)

by DeathLlama9, Jul 14, 2016, 7:22 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
When I saw the title, I thought the post would be about this problem.
Hooray for lamp problems!

by jam10307, Jul 14, 2016, 9:58 PM

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: 30957
  • Total comments: 579
Search Blog
a