14
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ To clarify, the button for 24 does not toggle the light in room 42? $\endgroup$ – JonTheMon Jan 8 '15 at 19:14
  • $\begingroup$ @JonTheMon Nope :) $\endgroup$ – GOTO 0 Jan 8 '15 at 19:16
  • $\begingroup$ Can we assume the hotel is not absurdly large? $\endgroup$ – frodoskywalker Jan 8 '15 at 21:04
  • 3
    $\begingroup$ Empty the odd numbered rooms by sending the guest in room i to room 2i, then put the first coachload of guests in rooms 3^n, the second coachload in rooms 5^n; for coach number c we use the rooms p^n where p is the cth odd prime number. No - wait - wrong hotel. :) $\endgroup$ – A E Jan 9 '15 at 18:49
11
$\begingroup$

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)

enter image description here

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. enter image description here

$\endgroup$
  • $\begingroup$ What happens from 10k to 11k? $\endgroup$ – JonTheMon Jan 8 '15 at 21:51
  • $\begingroup$ Just what I was afraid of. At this point either there is a mathematical proof of how all numbers with length greater than X will result in a uniform direction (increasing/decreasing the on/off proportion), or it will fluctuate to infinity. $\endgroup$ – Quark Jan 8 '15 at 21:59
  • $\begingroup$ @GOTO0 Thanks for confirming, I'll take another look when I get home in a few hours. $\endgroup$ – frodoskywalker Jan 9 '15 at 7:37
4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ You found a repeating pattern in certain groups of 10 and 100 lights, that's great! You can use that symmetry to explore what happens with more than 3 digits without too many calculations. Be sure to double-check your logic for a few flaws. $\endgroup$ – GOTO 0 Jan 9 '15 at 7:03
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Not necessarily. Since you are playing with integers, it doesn't have to play nicely. It could go directly from 49.999% to 50.001% lightness. $\endgroup$ – DrLemniscate Jan 11 '15 at 21:27
  • $\begingroup$ @DrLem Whenever you increase $n$ by one, you either get one new lit room or one new dark room. None of the previous rooms change. Therefore, as you increase $n$, the quantity [# of lit rooms] - [# of dark rooms] changes by 1 at a time. So, since it goes from negative to positive, that quantity must at some point be 0. Thanks, I should have included this to start with. $\endgroup$ – Lopsy Jan 11 '15 at 21:32
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What was your upper bound? Do you have a mathematical proof that it is the highest possible number? $\endgroup$ – March Ho Jan 9 '15 at 18:44
  • $\begingroup$ I first tried till 1,000,000. That program executed in a few seconds. Then I tried 10,000,000. That makes me believe that my solution is the highest. But unfortunately I don't have a proof. And of course I could have made a mistake in my code $\endgroup$ – Ivo Beckers Jan 9 '15 at 18:46
  • 1
    $\begingroup$ Some numbers: for $n$=10^5, 10^6, 10^7, the excess of lights on is 3938, 11804, 166586 respectively. (This is # of lights on minus $n/2$.) So for very low values of $n$, there is a significant trend towards having an even number of light flips. Naively, I'd expect that for large $n$ (i.e. around a trillion digits), the long-term behavior looks like a random walk, and crosses 0 infinitely many times. I would be very interested in a proof or even a heuristic arguing otherwise. $\endgroup$ – Lopsy Jan 10 '15 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.