Enigmatic Code

Programming Enigma Puzzles

Enigma 1131: Numbers in boxes

From New Scientist #2287, 21st April 2001 [link]

I have a row of boxes numbered 1, 2, 3, …, in order, going on forever. Each box contains a piece of paper on which is written a positive fraction, for example box 1 contains 2/5. When I looked at the numbers in all the boxes I found the following was true:

If you chose any positive fraction then I can find a particular box so that all the numbers in the boxes after that particular box will be less than your fraction.

For example, if you choose 1/3 then all the numbers in the boxes after box 44 are less than 1/3.

This morning I was looking for 3 boxes containing numbers adding up to 1. In fact I made a list, L, of all such three’s of boxes.

Question: Which of the following statements can you say for certain are true?

(a) All the boxes on list L come before box 100;
(b) All the boxes on list L come before box 1,000,000;
(c) I can find a particular box so that all the boxes on list L come before my particular box.

[enigma1131]

Advertisements

3 responses to “Enigma 1131: Numbers in boxes

  1. Jim Randell 23 January 2017 at 8:41 am

    This seems to be a bit of an odd question. We’re not told anything specific about the collection of boxes less than 100, or less than 1,000,000, so unless we can prove all the boxes on L are less than box 44 it seems unlikely we will be able to say that (a) or (b) is definitely true. And if the list of boxes on list L is finite then it has a defined maximum value, and all boxes on the list will occur before any box that come after that maximum. So it seems likely that (c) will be true, unless we can show that L is not finite.

    If we consider three fractions a, b, c, such that 0 < a < b < c and a + b + c = 1. We observe that the fractions can’t all be chosen from boxes with numbers greater than 44, as then each fraction would be less than 1/3, so the sum would be less than 1.

    So c must come from a box numbered 1 to 44. Not all of these are necessarily greater than 1/3, but at least one of them is (we are told box 1 contains the fraction 2/5).

    So let’s consider what happens when c is 2/5, the fraction in box 1. We still need to find values for a and b, such that a + b = 3/5.

    This means b > 3/10 and a < 3/10.

    Now there is some box, numbered k, such that all boxes after box k contain values less than 3/10.

    So b must come from a box with a number at or below k.

    We can go through each box from 2 to k, and if that box contains a suitable fraction for b (i.e. b > 3/10) we can see if there is a corresponding box containing the suitable fraction (3/5 – b), if we find it (and we only have to search a finite number of boxes, as there is a specific box where we know all subsequent boxes will contain fractions less then our required value) we can write down the corresponding box numbers for (a, b, c) on a list.

    When we finish exhaustively considering possible values for b we will have added a finite number of box numbers to our list.

    We can then repeat this process for each box from 2 to 44. If the box contains a fraction of 1/3 or less, we skip it, otherwise we use this fraction as c, and repeat the process given above, adding a finite number box numbers to our list.

    At the end of the entire process we have written down a finite number of box numbers, and these box numbers are exactly those used on the list L as described in the puzzle text.

    As the list is finite there is a largest box number on the list, we can’t say if it is less than 100, or less than 1,000,000, but we do know that it is a specific defined value, and by choosing a box with a number greater than this we will have found a box such that all the box numbers on list L come before that.

    Solution: We can say for certain that (c) is true.

  2. Hugh Casement 23 January 2017 at 11:47 am

    I assume that “I can find a box such that all the numbers in the boxes after that particular box will be less than your fraction” is equivalent to saying that the fractions in successive boxes decrease monotonically (but never reach zero).  One plausible scheme would be for them to decrease fairly steadily, the mean ratio between the fractions in two neighbouring boxes being close to 241/242.
    In that case, if we take boxes 1 and 2, the fraction slightly more than 1/5, needed to make up 1, would be found in box 166 or somewhere near it.  Under that assumption, statement (a) is probably not true, but there’s a high probability that statement (b) is.  However, there are many other possible schemes …

    Incidentally, the word ‘forever’ does not mean what the people at NS think it means.  They’re forever getting that wrong.

    • Jim Randell 24 January 2017 at 6:50 pm

      The condition of the sequence of fractions being a decreasing sequence is stronger than that stated in the puzzle text. (It is a sufficient condition, but it is not necessary). The fractions in the sequence will tend to get smaller as we go along, they do not have to be in a strictly decreasing order.

      So, for example, box 2 could contain the fraction 1/2 (greater than 2/5 in box 1). But the construction still works. If we can find pairs of fractions in the other boxes that add up to 1/2 we can add them to list. So if we also used box 1 = 2/5 we would need to find a fraction of 1/10 to complete the sum. We know there is a box number where all fractions beyond that are less than 1/10, so we only have to examine a finite number of boxes to see if we can find one containing 1/10. If we can find a suitable box x, then we can add the triple (box 1, box 2, box x) to the list. But it could be that x is greater than 100, or greater than 1,000,000.

      If we can’t find a suitable box then we won’t be able to add a triple of the form (box 1, box 2, box x) to the list. But we can try again with another box to go with box 2 (e.g. box 3 if that contains a fraction less than 1/2), but somewhere along the line we will reach a box where all remaining boxes contain fractions less than 1/4, so no pair of them will ever make a triple with box 2.

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: