0

As ongoing trend, I have been solving old MAT past papers that do not have published solutions. I was wondering if anybody can verify my solution to the following question. enter image description here

My Solution

(i) We prove this by contradiction. Suppose that after one second there is exactly one bulb ON. This implies that only two consecutive light bulbs say $n$ and $n+1$, must have had different lights in the beginning. This implies that $n+3$ and $n+4$ had the same state since only one is ON after 1 second. Similarly, $n+4$ and $n+5$ must have had the same state and so on until we get that $n-1$ and $n$ have had the same state. This is a contradiction as $\text{state of } n \neq \text{state of } n+!$ and hence there could not be exactly one light bulb ON after one second.

(ii) Let $m$ be an odd number. Let there be $m$ many turned on lights after one second. Therefore, out of $N$ many lights m many consecutive pairs have different initial states. Let these pairs be

$$\{m_0,m_0 +1\},\{m_1,m_1 + 1\},\, ... , \{m_m, m_{m}+1\}$$

Say the initial state of $m_0$ is ON/OFF. By construction we will have, $m_0 +1, m_0 +2,\, ... ,m_1$ have the same initial signal. This implies that $m_2$ has a signal of ON/OFF. This can be done $m$ many times to show that $m_m$ is ON/OFF which implies that that $m_n +1, \, ..., m_0 -1$ are OFF/ON since $m$ is odd. This implies that $m_0 -1$ and $m_0$ have different initial values. This is a contradiction because if true this would imply that there are $m+1$ of these pairs. Thus there can not be odd many turned ON lights after the first second.

(iii) Let $b_n$ be the nth bulb. And let $v_i (b_n)$ be the status of the nth bulb after $i$ seconds have passed. The formula for $2$ seconds passed is $$ v_2(b_n) \begin{cases} \text{ON} & \text{if } v_1(b_n) \neq v_1(b_{n+2}) \\ \text{OFF} & \text{if } v_1(b_n) = v_1(b_{n+2}) \end{cases} $$ The work of which I have done but I really can not put in LaTeX as it would take a lot of time. From the equation we see that it is only dependent on $b_n$ and $b_{n+2}$ as required. (iv)

$$ v_4(b_n) \begin{cases} \text{ON} & \text{if } v_1(b_n) \neq v_1(b_{n+4}) \\ \text{OFF} & \text{if } v_1(b_n) = v_1(b_{n+4}) \end{cases}$$ again the proof of which I have on paper but I really can not write in LaTeX due to time.

(v) After 8 seconds.

Maths Wizzard
  • 2,259
  • ii) Presumably you want $ m_0 < m_1 < \ldots m_m$? Even then, there isn't a contradiction (as you stated) if we had $m_0 = 1, m_m = n$, as it agrees with $m_0 -1$ and $m_0$ have different initial values. You need to be more careful with your language. v) You need to prove this statement, not just state the numerical answer. – Calvin Lin Oct 30 '20 at 23:35
  • @CalvinLin thank you for the comment. Yes I meant $m_0 < m_1 < \cdots <m_m$. I am not sure about your second comment as I am talking about pairs. For the last bit I have proven it but as I said previously, I really do not have the time to write it out on LaTeX as I have to write multiple questions here since there are absolutely no mark schemes for more than 10 papers, apologies for which. – Maths Wizzard Oct 30 '20 at 23:55
  • ii) If $m_0 = 1, m_m = n$, then what is the contradiction? You're saying that "This implies $m_0-1 = n$ and $m_0=1$ have different initial values, but that's allowed since we have $m_m = n, m_m+1 = 1$ have different initial values. – Calvin Lin Oct 30 '20 at 23:59
  • iii, iv, v) We are not mind readers. If it's not written out, we cannot provide feedback on the solution. As currently written, you'd get partial credit. You may have a proof in your mind, but the difficulty of proof writing is in convincing someone else that your statements are indeed true. – Calvin Lin Oct 31 '20 at 00:03
  • @CalvinLin apologies for the unclarity. In future, I will aim to provide more of my workings (even if that means scanning pages). – Maths Wizzard Oct 31 '20 at 00:06

1 Answers1

2

There's a very clean way to present the problem.

Denote a bulb to be OFF by 1.
Denote a bulb to be ON by -1.

Let $ S_t (i)$ denote the state of the bulb $i$ at time $t$.
From the definition, verify that $S_t (i) = \frac{ S_{t-1} (i)}{ S_{t-1} (i+1)} $.

i, ii) Observe that for $ t \geq 1$, $ \prod S_t (i) = \prod \frac{S_{t-1} (i) } { S_{t-1} (i+1) } = 1 = (1) ^{ \text{number of OFF} } (-1) ^ { \text{ number of ON} }$.
Hence, the number bulbs that are ON is even.

iii, iv, v) It can be easily proven (E.g. by induction) that $S_{2^t} (i) = \frac{ S_0 (i) } { S_0 (i+2^t)}$, so the state at time $2^t$ only depends on $S_0 (i)$ and $S_0 (i+2^t)$.
Thus when $N= 2^t$, $S_N(i) = \frac{ S_0 (i) }{S_0 (i+N) } = 1$, so all bulbs are OFF.

Calvin Lin
  • 68,864
  • Re: Your last line: If $N$ is odd and $t>0,$ not all bulbs can be on by Part ii...... Also, if $N=3$ and if exactly one bulb is on at $t=0$, then at any time $t>0$ there will be $2$ bulbs on and $1$ off. – DanielWainfleet Oct 31 '20 at 02:39
  • @DanielWainfleet Good points. The induction only works for $2^t$ and the state of 1 is OFF, not ON. – Calvin Lin Oct 31 '20 at 18:11
  • +1........ Suppiemental: The Q "How long does this take?" could mean "What is the least $t$ such that all bulbs are off at time $t$, regardless of the initial state?" If $N$ is a power of $2$ then this least $t$ exists and is not more than $N$, but is it equal to $N$? – DanielWainfleet Oct 31 '20 at 22:47
  • 1
    @DanielWainfleet Yes to your supplemental question. The idea is at time $t< N$, the state of bulb $i$ depends only on the states $S_0(i), S_0(i+1), \ldots S_(i+t)$. Also, by the fraction multiplication, it depends on an even number of states, and $ S_0(i)$ appears exactly once. So, we can toggle $S_t(i)$ (and also a lot of other states at time t) by toggling $S_0(i)$. This potentially breaks down at time $ t = N$ because of how the bulb loops around, and definitely breaks down when $N = 2^k$. – Calvin Lin Nov 01 '20 at 14:32