Enigmatic Code

Programming Enigma Puzzles

Enigma 1237: Odd socks

From New Scientist #2393, 3rd May 2003 [link]

George recently suffered a nightmare involving a seemingly bottomless drawer containing large numbers of socks of each of the seven colours of the rainbow. Old Nick whispered in George’s ear that if he selected two socks at random from the drawer the odds were exactly even that they would be the same colour.

The ghost of George’s mother-in-law then appeared, declared a distaste for violet socks, and threw out all the socks of that colour. With six colours remaining, the devil repeated that two socks selected at random had a 50:50 chance of being the same colour.

Four more ghosts appeared and threw out in turn all the indigo, blue, green and yellow socks. The Devil repeated his assertion each time, with reducing numbers of colours, that a pair selected at random had a 50:50 chance of being the same colour.

“There are 25 socks left, but how many have been thrown out?” George asked the Devil.

“I don’t give straight answers,” replied the Devil, “but I can tell you that it is an exact multiple of the original number of socks of your favourite colour.”

What is that multiple, and what is George’s favourite colour?

[enigma1237]

Advertisements

6 responses to “Enigma 1237: Odd socks

  1. Jim Randell 29 April 2015 at 8:48 am

    This Python program runs in 527ms.

    from fractions import Fraction as F
    from itertools import count
    from enigma import irange, compare, printf
    
    # probability of choosing 2 socks with the same property
    # when x of N socks have that property
    def P(x, N):
      return F(x * (x - 1), N * (N - 1))
    
    # s - numbers of socks (in increasing order)
    # t - total number of socks
    # l - limit on the number of colours
    def solve(s, t, l):
      # are we done?
      if len(s) == l:
        return (s, t)
      else:
        # add in another colour
        for x in count(s[-1]):
          s2 = s + [x]
          t2 = t + x
          if 2 * sum(P(n, t2) for n in s2) == 1:
            return solve(s2, t2, l)
    
    # the number of red and orange socks = 25 but we can't distinguish them, 
    # so let them be A and B, where A < B, A + B = 25
    for A in irange(1, 12):
      B = 25 - A
      # the sum of the probabilities should be a half
      if 2 * (P(A, 25) + P(B, 25)) == 1:
        # find a sequence of length 7 starting with A and B
        (s, t) = solve([A, B], 25, 7)
        # the number of thrown away socks
        T = t - 25
        # consider favourite colours
        for (f, c) in zip(s, ('R/O', 'O/R', 'Y', 'G', 'B', 'I', 'V')):
          (m, r) = divmod(T, f)
          if r == 0:
            printf("multiple={m} colour={c} {s}")
    

    Solution: The multiple is 121. George’s favourite colour is yellow.

    There are 10 and 15 socks that are red and orange (but we don’t know which number is associated with which colour), 51 yellow socks, 153 green socks, 459 blue socks, 1377 indigo socks and 4131 violet socks. With all seven colours there are 6196 socks in total. 6171 (= 121×51) of them are thrown out to leave the 25 red and orange socks.

    So apart from the colour with 10 socks all the other colours have an odd number of socks.

  2. Brian Gladman 29 April 2015 at 5:14 pm
    # At a stage in the process, let there be a total of T socks and
    # n[i] socks of colour i (so that T = sum(n[i]). The probability
    # of choosing two socks of the same colour is:
    # 
    # (1)    p(same) = sum{n[i].(n[i] - 1]} / [T * (T - 1)]
    #
    # Equating this to 1/2 gives:
    #
    # (2)    2.sum{n[i]^2} = sum{n[i]}^2 + sum{n[i]}
    #
    # Evaluating the difference between this equation for i + 1 and i
    # gives:
    # 
    # (3)    n[i + 1] = 2.sum{n[i]} + 1
    #
    # Hence working upwards in sock numbers starting at two, we can
    # find the number of socks in the next higher colour that gives
    # an equal probability of picking two socks of the same colour
    
    clr = ('red', 'orange', 'yellow', 'green', 'blue', 'indigo', 'violet')
    
    # the numbers for each sock colour, starting with the numbers for
    # colours in round one and two (although we don't need to, we can
    # find these by solving (2) above for two colours)
    n = [10, 15]
    # the total numbers of socks at each stage
    t = [ 0, 25]
    for i in range(2, 7):
      n += [2 * t[-1] + 1]
      t += [n[-1] + t[-1]]
    
    # now look for a sock colour where the number for this 
    # colour divides the total number of socks removed
    for i in range(7):
      m, r = divmod(t[-1] - t[1], n[i])
      if not r:
        # we cannot determine red or orange as the favourite
        c = clr[i] if i > 1 else ' and '.join(clr[:2]) 
        fs = "The multiple is {}, George's favourite colour is {}."
        print(fs.format(m, c))
    
  3. Hugh Casement 29 April 2015 at 6:07 pm

    I think I’m right in saying that the numbers of red and orange socks must be two consecutive triangular numbers, summing to a square number.  The number of yellow socks is one more than twice that square.  After that, the number of each successive colour is three times the previous.  So the smallest set of numbers could be 1 red and 3 orange (4 socks remaining, rather than 25 in the puzzle as set), 9 yellow, 27 green, 81 blue, 243 indigo, 729 violet.  Sum 1093, of which 1089 = 121×9 are thrown out.  Not quite as nightmarish, but still a lot of socks for a man to possess.

    In this case it’s all odd numbers — rather like my sock drawer, in fact.

    • Tessa Fullwood 30 April 2015 at 9:28 am

      Hugh, your logic looks right to me. Perhaps the setter expected objections because you can no longer find a pair of red socks!

    • Jim Randell 30 April 2015 at 3:09 pm

      Continuing your analysis a bit…

      The sequence goes: S(n) = [T(n-1), T(n), (3^k)(2n² + 1), …] k=0..4, for n > 1.

      With the first two terms summing to n² (the remaining socks), and the other 5 terms, which are the discarded socks, are a geometric sequence that sums to (3^5 – 1)/2 × (2n² + 1) = 121(2n² + 1) = 121 × (the 3rd element of the sequence).

      So for any sequence S(n) the sum of the final 5 terms is always 121 times the third term, so we can arrive at an answer, without knowing n.

      For n=1 (S=[0, 1, 3, 9, 27, 81, 243]) and n=2 (S=[1, 3, 9, 27, 81, 243, 729]) are there multiple terms that divide the number of discarded socks ([1, 3] and [1, 3, 9] respectively).

      In the puzzle we are told there are 25 socks remaining, so n²=25, hence n=5, S=[10, 15, 51, 153, 459, 1377, 4131].

  4. Tessa Fullwood 30 April 2015 at 9:20 am

    3 stars it deserves a star for the entertaining text in the question.

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: