# Is 1100 a valid state for this machine?

A room starts out empty. Every hour, either 2 people enter or 4 people leave. In exactly a year, can there be exactly 1100 people in the room?

I think there can be because 1100 is even, but how do I prove/disprove it?

-
I think you have to take into account how many hours are in a year. For instance, in four hours, it is impossible for there to be $6$ people in the room. –  The Chaz 2.0 May 2 '12 at 15:22

A general advice: Whenever you have to distill a simple answer from a confusing medley of cases, look out for the invariant!

The remainder mod 6 increases by $2$ per hour; therefore it is periodic with period 3 hours. As 24 is divisible by $3$, after exactly one year the remainder mod $6$ will be $0$, whether we have a leap year or not. It follows that an occupancy of $1100$ is impossible then.

-
Thanks, though how did you come up with 6 to mod by? It seems a bit out of the blue for me. –  David Faux May 2 '12 at 15:41
@David Faux: We don't know whether $2$ are added or $4$ are subtracted in any given hour. Fortunately in both cases the remainder mod $6$ increases by $2$. –  Christian Blatter May 2 '12 at 15:46
Though cliché, I might add to the general advice (and was trying to induce such thinking in my comment above): sole a simpler problem! –  The Chaz 2.0 May 2 '12 at 16:35
@David: Because 2 and -4 are congruent mod 6 –  BlueRaja - Danny Pflughoeft May 2 '12 at 20:47

Exactly a year is $24*365=8760$ hours (or $8784$ for a leap year-maybe you need to try both). If there are $x$ times that two people enter and $y$ times that four people leave, you want $x+y=8760,\ 2x-4y=1100$. Two equations in two unknowns, and if the solution is integral you are there.

-

Here's a slightly different take on Christian's approach. There's almost nothing in it that isn't at least implicit in one or another of the other answers, but it may be of some use in showing one way in which one might approach the problem.

First, I notice that we can divide everything in the problem by $2$: each day either one person enters or two leave, and we want to know whether we can have $550$ people in the room after exactly one year. This makes no essential change in the problem, but sometimes it's easier to spot things when working with smaller numbers.

Then I ask myself after how many hours the room can be empty. Clearly if there were $n$ hours in which two people left, there must have been $2n$ hours in which one person entered, so $3n$ hours must have passed. In other words, the room can be empty only after a multiple of $3$ hours. This naturally makes me wonder what can happen after $3n+1$ or $3n+2$ hours. That in turn gets me to thinking mod $3$, and I realize that subtracting $2$ is the same as adding $1$ mod $3$. In other words, no matter what happens, every hour the population of the room increases by $1$ mod $3$. One regular year has $8760$ hours, so (mod $3$) at the end of a year the room must contain $8760\bmod 3=0$ people. Unfortunately, $550\bmod 3=1$, so we can't end up with $550$ people in the room at the end of a regular year. And since the extra day in a leap year adds another $24\bmod 3=0$ people, we can't end up with $550$ sardines people in the room at the end of a leap year, either.

-
Great walkthrough, but is it really fair to say that at the end of a year the room must contain 8760 mod 3 = 0 people, when in fact there are 8760 different possibilities? –  Milosz Wielondek May 2 '12 at 21:24
@Milosz: But mod $3$ there is only one possibility, and I was working entirely mod $3$. –  Brian M. Scott May 2 '12 at 21:29
I'm not very confident with modular notation, but wouldn't rephrasing it as "the room must contain $0\ (\text{mod } 3)$ people" be more correct/read more clearly? –  Milosz Wielondek May 2 '12 at 21:34
@Milosz: Probably, though I chose a different solution. –  Brian M. Scott May 2 '12 at 21:37
Nicely done, Brian. –  ThisIsNotAnId May 2 '12 at 22:43

The answer is no. Since there are 24 hours in the day, the number of hours in a year is multiple of 3.

It taakes a non-multiple of three hours to fill the room with 1100 people, and then a multiple of three hours to balance the room.

Alternately: $(2x-4y)-(x+y)$ is a multiple of three. Thus 1100- no of hours must be multiple of three....

-

No, there are $24\cdot 365$ hours in a year, you have $2x-4y=1100$, but solutions are not integers.

-

The process can be rephrased as making a required motion of $+2$ every time, with an optional additional motion of $-6$ at some steps. The forward part of that motion will reach $+2N$ in $N$ steps, plus some backward motion divisible by $6$ to attain the final total motion of $T=+1100$. Here $N$ and $T$ are given and the exact condition for a pair $(N,T)$ to be realizable is that $(2N - T)/6$ be a non-negative integer. That integer is equal to the number of backward moves, whether thought of as $-4$'s or $-6$'s.

This answer was found in reverse, by solving the linear $2 \times 2$ system for the number of $+2$ and $-4$ moves (given $N$ and $T$), and interpreting the condition for the numbers to be non-negative integers.

As explained in the previous answers, for the problem as posted, $2N = 2 \times 24 \times \text{(days in year)}$ is divisible by $6$ and $1100$ is not, so the conditions are not satisfied.

-