Enigmatic Code

Programming Enigma Puzzles

Enigma 163: Common occurrences

From New Scientist #1308, 3rd June 1982 [link]

The number of people in the room was a perfect square. We were numbered consecutively from 0 upwards. We each had to think of a number which was chosen from 0, 1 or any power of 2 giving a number less than the number of people in the room. It turned out that the person number 0’s choice of number coincided with number of 0s chosen; the person number 1’s choice of number coincided with the number of 1s chosen; the person number 2’s choice of number coincided with the number of 2s chosen; the person number 3’s choice of number coincided with the number of 3s chosen (which of course was zero); and so on for all the people in the room.

How many people in the room?

[enigma163]

Advertisements

One response to “Enigma 163: Common occurrences

  1. Jim Randell 22 January 2014 at 7:58 am

    This Python 3 program runs in 52ms.

    from collections import Counter
    from enigma import irange, printf
    
    # numbers - numbers to choose from
    # count - choices so far
    # t - total we are aiming for
    # ms - dictionary of minimum values
    def solve(numbers, count, t, ms):
      # are we done?
      if len(count) == len(numbers):
        if t == 0:
          # count the assigned numbers
          s = Counter(ms)
          s.update(count)
          # now check the actual counts
          d = dict(zip(numbers, count))
          if all(s[i] == d[i] for i in numbers):
            yield d
      else:
        for i in numbers:
          if i < ms.get(numbers[len(count)], 0): continue
          if not(i > t):
            yield from solve(numbers, count + [i], t - i, ms)
    
    for i in irange(1, 8):
      n = i ** 2
    
      # determine possible choices
      numbers = [0]
      p = 1
      while p < n:
        numbers.append(p)
        p *= 2
    
      # find working combinations
      for d in solve(numbers, [], n, {0: n - len(numbers)}):
        printf("n={n} {d}")
    

    Solution: There were 36 people in the room.

    The people who chose a non-zero number are shown below. The remaining 32 people all chose 0.

    person:  0  1  2  32
    number: 32  2  1   1

    There are actually two further solutions with 4 people in the room:

    person: 0 1 2 3
    number: 1 2 1 0
    person: 0 1 2 3
    number: 2 0 2 0

    But we’ll be generous and suppose that the “and so on…” after person number 3 implies there are more than 4 people, which gives a unique solution. Although I think the puzzle could have made this clear.

    For 49 people there are 7 possible numbers each person can choose from (0, 1, 2, 4, 8, 16, 32), so there are 42 people whose numbers don’t coincide with the choice numbers and must chose 0, hence there are at least 42 zeros. But this is more than the largest possible choice number. So there cannot be 49 people in the room.

    For 64 people there are now 8 possible choice numbers (0, 1, 2, 4, 8, 16, 32, 64), so there must be at least 56 zeros, and the only choice number at least as large as this is 64. But there cannot be 64 zeros, as person number 0 would have to choose 64. So there cannot be 64 people in the room.

    In fact by considering when:

    \sqrt{x}\; >\; 2\; +\; \log _{2}\left( x \right)

    or equivalently when the following equation is greater than zero:

    y = 4x\; -\; 2^{\sqrt{x}}

    we can see that there can be no solutions for greater than 64 people.

    Of course, if you don’t trust the analysis, you can let the program consider squares up to 70710², at which point the number of people in the room would exceed 5×109, which is greater than the number of people on the planet in 1982. This only takes 1.5s with the program above (or 168ms with an equivalent program running under PyPy).

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: