Enigmatic Code

Programming Enigma Puzzles

Enigma 1192: Class division

From New Scientist #2348, 22nd June 2002 [link]

The schoolteacher wanted to choose a certain small number of boys from his class. “In how many ways can I choose that number of boys?” he asked. The answer was a three-figure number. He then wanted to choose a certain smaller number of girls from the class. “In how many way can I choose that number of girls?” he asked. The answer was a three-figure number.

The teacher then wanted to choose a certain smaller number of children from the class as a whole. “In how many ways can I choose that number of children?” he asked. The answer was a three-figure number.

The three-figure answers above between them use all of the digits 1 to 9.

How many children were in the class?

[enigma1192]

Advertisements

2 responses to “Enigma 1192: Class division

  1. Jim Randell 23 November 2015 at 7:24 am

    The solution depends on your interpretation of “a small number” of children.

    This Python program considers class sizes up to 100. It runs in 93ms.

    from enigma import irange, C, printf
    
    # generate pairs (n, c) where n is between m and M and c = C(N, n) is
    # a 3-digit number composed of different non-zero digits
    # n is returned as an integer, c is returned as a decimal string
    def generate(N, m, M):
      for n in irange(m, M):
        c = str(C(N, n))
        if len(c) == 3 and '0' not in c and len(set(c)) == 3:
          yield (n, c)
    
    # consider the size of the class
    for N in irange(7, 100):
      # choose n from the whole class
      for (n, cn) in generate(N, 2, N):
    
        # choose the number of boys in the class
        for B in irange(4, N - 3):
          # choose b from the boys (n < g < b)
          for (b, cb) in generate(B, n + 2, B):
    
            # the number of girls in the class
            G = N - B
            # choose g from the girls (n < g < b)
            for (g, cg) in generate(G, n + 1, min(b - 1, G)):
    
              # and the three combinations use the digits 1 - 9
              if len(set(cn + cb + cg)) != 9: continue
          
              printf("B={B} b={b} cb={cb}, G={G} g={g} cg={cg}, N={N} n={n} cn={cn}")
    

    Solution: There were 30 children in the class.

    The program examines class sizes up to 100, and comes up with several solutions. The smallest possible class size is 30 children.

    There are 435 ways to choose 2 of the children from the class of 30.

    One way to split up the class is into 12 boys and 18 girls.

    There are 816 ways to choose 3 of the girls from the 18 girls in the class.

    There are 792 ways to choose 5 of the boys from the 12 boys in the class.

    This seems to be the most reasonable solution. The class is a reasonable size, and 5 could be considered a “small number” of boys.

    However, there is a similar solution if we choose 7 of the 12 boys (as this is the same as choosing 5 of the boys not to include in the group).

    We could also split the class into 18 boys and 12 girls, choose 5 (or 7) of the girls, and 15 of the boys. Although we are beginning to stretch the definition of “a small number” of boys.

    The next smallest class size is 42, consisting of 30 boys and 12 girls. We choose 2 children from the whole class, 5 (or 7) of the girls, and 28 of the boys. I don’t think 28 (of 30) can really be considered “a small number”.

    If we interpret the choice of children as implying there must be at least 2 children in the selected groups, then these are the only solutions.

  2. Brian Gladman 23 November 2015 at 2:35 pm
    from math import factorial
    from collections import defaultdict
    
    limit = 101
    
    # store the number of ways r items can be selected from n items
    # such that the answer has three different non-zero digits
    nCr = defaultdict(dict)
    for n in range(1, limit):
      for r in range(1, n + 1):
        if r < n - r:
          ncr = factorial(n) // (factorial(r) * factorial(n - r))
          set_ncr = set(str(ncr))
          if 100 <= ncr < 1000 and len(set_ncr) == 3 and '0' not in set_ncr:
            nCr[n][r] = (ncr, set_ncr)
    
    # the number of boys in the class           
    for B in range(1, limit):
      # the number of boys selected and the ways this can be done
      for b, (BCb, sBCb) in nCr[B].items():
        # the number of girls in the class           
        for G in range(1, limit):
          # the number of girls selected and the ways this can be done
          for g, (GCg, sGCg) in nCr[G].items():
            # the numbers of ways for boys and girls have no shared digits
            if g < b and not sBCb & sGCg:
              # now select a number of children bg 
              for bg, (BGCbg, sBGCbg) in nCr[B + G].items():
                # for which the number of possible selections cannot 
                # share any digits with those for boys and girls alone
                if not sBGCbg & (sBCb | sGCg):
                  print(B + G, (b, B, BCb), (g, G, GCg), (bg, B + G, BGCbg))
    

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: