The lights in the hotel

Question

A hotel has $n$ rooms, numbered 1, 2, 3, etc. until $n$. At the hotel reception there are $n$ buttons, one for each room, also numbered 1, 2, 3, ..., $n$. Button 1 switches the light from on to off or from off to on in all rooms whose number contains a "1", hence in rooms 1, 10, 11, 12, etc. Button 2 switches the light on or off in all rooms whose number contains a "2", hence 2, 12, 20, 21, etc. The same thing happens with all other buttons, so for example button 42 switches the light in rooms 42, 142, 242, etc.

The receptionist sees that all rooms have the lights on, so she pushes all buttons from 1 to $n$ in sequence. At the end of the process she notices that there are just as many rooms with the light on as there are rooms with the light off.

How many rooms are there in the hotel at most?

Answer 1

There might be a problem. It looks like Quark's answer of

306

is correct, given this plot for up to 1000 rooms (excess of lights on over lights off)

But if we extend that range a little...

We see that the initial trend reverses, crossing the y-axis several times after 8000 rooms. It's not clear to me that this back-and-forth trend ends.

Answer 2

The answer (assuming I didn't mess up somewhere) is:

306

I sort of brute forced the problem because it seemed faster that way.

To still be on, the number has to be called an odd number of times before its own button is pushed. So, since the first hundred numbers can only be called twice max (once for each digit), the only ones that stay on are 10/11, 20/22, etc up to 90/99 (18 on 81 off).

Then,

After three digits, it changes a bit. There are now 5 ways a 3 digit number can be called, one of its numbers, the first two, or the last two. There are no "1"s (even 100 has 1 and 10), so 3's are 102-110(9 on) and are only possible with the "0" second digit.

So,

For 5's, from 120 on there are 7 per set of 10, the 3 not included are 1*0, 1*1, and 1**, so for the set from 100-199, 65 are on and 35 are off (9+7*8). Another way to think of this is +30 to the original -63.

From here,

Every hundred from here on will be another +30 with symmetry. So by 300 the "count" will be -3

And finally,

300(3 and 30) is -1, 301 and 302 are +1, 303 is -1, 304-309 are +1 but by 306 the -3 from before is reached (-1+2-1+3), leaving a final answer of 306. It will never back track far enough to go negative again up to a thousand.

It may be explained a bit messily, I'm not a math proofs guy but you can generalize my statements for any number of digits. (There's probably a better way to spoiler a paragraph than to add random words in between sentences, I'm still new at this)

I just considered the possibility that in the 4 digit numbers it could loop back to being more negative but my brain is starting to hurt and I wouldn't be able to focus long enough to figure it out anyway if that was the case (because then the solution would be in the 5 digit numbers).

Answer 3

There is a solution between $10^{11}$ and $10^{12}$.

For $n=10^{11}$, the total number of lights off is 50563019008. Just over half.
For $n=10^{12}$, the total number of lights off is 499476031551. Just under half.

So, somewhere between $10^{11}$ and $10^{12}$ there is an $n$ where exactly half of the lights are off.

I found this using a computer program. To cut the number of cases, I used symmetry. Permuting the digits 1-9 does not change whether a room is on or off, for example "377377009" is the same lightness as "899899001". This reduces the number of essentially different 12-digit numbers to only ~27 million.

I doubt this puzzle has a nice answer. I would be very impressed/surprised if GOTO 0 has a solution.

Answer 4

I think it's

12072

I brute forced it with a Java program that I wrote.

EDIT:

This is the program that I wrote:

import java.util.HashSet;

public class Main {

    public static void main(String[] args) {
        long i = 1;
        long even = 0;
        while (i < 1000000) {
            even += check(i) ? 1 : -1;
            if (even == 0) System.out.println(i);
            i++;
        }
    }

    private static boolean check(long i) {
        HashSet<String> subs = new HashSet<String>();
        String string = String.valueOf(i);
        for (int beginIndex = 0; beginIndex < string.length(); beginIndex++) {
            for (int endIndex = beginIndex; endIndex <= string.length(); endIndex++) {
                if (!string.substring(beginIndex, endIndex).startsWith("0")) {
                    subs.add(string.substring(beginIndex, endIndex));
                }
            }
        }
        return subs.size() % 2 == 0;
    }

}

I am sure there must be more efficient ways but this is how it works. For each number I check how many light switches there exists. I do this by checking how many distinct sub strings there are that do not begin with 0. I keep track of a variable even that is raised by one on an even amount of these substrings and substracted by one on an odd amount. Every time this variable is 0 there must be an equal amount of lights that are on and off. The 306 mentioned in another answer is the first it finds so it gives me confidence that this method works.