Enigmatic Code

Programming Enigma Puzzles

Tantalizer 488: Dog’s life

From New Scientist #1039, 17th February 1977 [link]

The Smiths have ten children and a dog called Marmaduke. Every so often they buy a huge tin of toffees and them out after tea, one at a time starting with the oldest child. They never miss a child out but whether Marmaduke gets a toffee at every, some or any turn depends on the whim of the moment. Mr and Mrs Smith never take any toffee for themselves.

Now look at it from Marmaduke’s point of view. He never gets one of the first ten toffees. He may or may not get the 11th. He certainly won’t get the 12th, 13th, 14th etc, but he becomes eligible for one at the end of the round, exactly when depending on whether he was lucky or not on the first round.

Now go back to the start of the process with a fresh tin about to be broached. Which is the highest numbered toffee which Marmaduke will certainly not get?

[tantalizer488]

Advertisements

One response to “Tantalizer 488: Dog’s life

  1. Jim Randell 8 March 2017 at 7:33 am

    This Python program runs in 39ms.

    from enigma import irange, printf
    
    # number of children
    K = 10
    
    (a, b, m) = (1, K, 0)
    while a <= b:
      printf("[excluded {a} - {b}]")
      m = b
      a += K + 1
      b += K
    
    printf("max excluded = {m}")
    

    Solution: The highest numbered toffee that we can say for certain Marmaduke will not get is toffee 100.

    Analytically:

    If we consider a sequence of “rounds”, where each child gets a sweet, and then possibly the dog does too.

    In round 1 the dog is definitely not going to get toffees 1 – 10, as they all go to the children. But he may get toffee 11.

    In round 2:

    If the dog did not get toffee 11, then the children get 11 – 20, and the dog may get toffee 21.
    If the dog did get toffee 11, then the children get 12 – 21, and the dog may get toffee 22.

    So whatever happens he can never get toffees 12 – 20, but may get 21 or 22.

    In round 3:

    If the dog has had no toffees so far, then the children get 21 – 30 (and the dog may get 31).
    If the dog has had 1 toffee so far, then the children get 22 – 31 (and the dog may get 32).
    If the dog has had 2 toffees so far, then the children get 23 – 32 (and the dog may get 33).

    So the dog cannot get 23 – 30, but may get 31, 32, 33.

    And so we continue as summarised in the diagram below:

    (X represents a toffee that the dog definitely won’t get, ? represents a toffee that the dog may get).

    When we get to the 10th round, the dog cannot get toffee 100, but may get any of 101 – 110.

    And in the 11th round there are no toffees that we can say for certain the dog cannot get.

    In general, if there are k children, then the highest number toffee that we can say for certain the dog will not get is toffee .

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: