### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 177,972 hits

Advertisements

Programming Enigma Puzzles

23 January 2017

Posted by on **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

%d bloggers like this:

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

Lare 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 listLis 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 thatLis not finite.If we consider three fractions

a, b, c, such that0 < a < b < canda + 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

cmust 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

cis 2/5, the fraction in box 1. We still need to find values foraandb, such thata + b = 3/5.This means

b > 3/10anda < 3/10.Now there is some box, numbered

k, such that all boxes after boxkcontain values less than 3/10.So

bmust come from a box with a number at or belowk.We can go through each box from 2 to

k, and if that box contains a suitable fraction forb(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

bwe 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

Las 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

Lcome before that.Solution:We can say for certain that (c) is true.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.

The condition of the sequence of fractions being a decreasing sequence is stronger than that stated in the puzzle text. (It is a

sufficientcondition, but it is notnecessary). 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, boxx) to the list. But it could be thatxis 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.