A280433 The mailbox manufacturer's problem, for the 2-mailbox case.

1, 3, 5, 7, 10, 14, 17, 20, 23, 28, 33, 37, 41, 45, 50, 55, 60, 66, 73, 78, 84, 89, 94, 99, 105, 114, 121, 127, 134, 140, 147, 154, 161, 167, 173, 183, 190, 202, 210, 218, 225, 232, 240, 247, 254, 261, 268, 276, 290, 301, 310, 318, 327, 335, 343, 353, 362, 371, 380, 390, 399, 408, 417, 430, 443, 455, 466, 476, 485, 496, 506

Offset: 1

Author

Christofer Ohlsson, Jan 03 2017

Keywords

• nonn

Comments

Given two identical mailboxes, each of which can hold up to n firecrackers, let M be the maximum number of firecrackers that can be simultaneously exploded in a mailbox without bursting it (and making it unusable for further testing). Assume that each mailbox can withstand an unlimited number of explosions of M or fewer firecrackers at a time. a(n) is the number of firecrackers needed to determine M, in the worst case, using an optimal strategy.

From Jon E. Schoenfield, Jan 11 2017: (Start)

As the number of mailboxes B increases without limit, the sequences appear to converge to A007078 (Optimal cost of search tree); the first 25 terms for cases B=1 (A000217), B=2 (this sequence), B=3 through B=6, and A007078 are as follows, where dots indicate a repeat of the value to the left:

.

n | B=1 B=2 B=3 B=4 B=5 B=6 A007078

---+------------------------ -------

1 | 1 .. .. .. .. .. 1

2 | 3 .. .. .. .. .. 3

3 | 6 5 .. .. .. .. 5

4 | 10 7 .. .. .. .. 7

5 | 15 10 9 .. .. .. 9

6 | 21 14 12 .. .. .. 12

7 | 28 17 16 15 .. .. 15

8 | 36 20 20 19 .. .. 19

9 | 45 23 .. .. .. .. 23

10 | 55 28 26 .. .. .. 26

11 | 66 33 29 .. .. .. 29

12 | 78 37 32 .. .. .. 32

13 | 91 41 35 .. .. .. 35

14 | 105 45 39 38 .. .. 38

15 | 120 50 45 41 .. .. 41

16 | 136 55 50 45 .. .. 45

17 | 153 60 55 49 .. .. 49

18 | 171 66 60 54 53 .. 53

19 | 190 73 65 61 57 .. 57

20 | 210 78 69 67 62 .. 62

21 | 231 84 73 .. 67 .. 67

22 | 253 89 77 .. 73 72 72

23 | 276 94 81 .. .. 77 77

24 | 300 99 85 .. .. 83 83

25 | 325 105 89 .. .. .. 89

(End)

Examples

			For n = 3, the optimal strategy uses 2 firecrackers for the first test, and in the worst case, the mailbox holds up and we need to try 3 firecrackers, for a(3) = 2 + 3 = 5 in total.
For n = 6, the optimal strategy uses 3 firecrackers for the first test. In the worst case, the mailbox holds up and we try a second test with 5. Again, the worst case is that the mailbox withstands the test, so the third test uses 6, for a final sum of a(6) = 3 + 5 + 6 = 14.
		

Links

• Joerg Arndt, Table of n, a(n) for n = 1..9999
• Kattis, The Mailbox Manufacturers Problem, from Norwegian/Swedish Championships 2002.

Crossrefs

Cf. A000217, A007078, A180975.

Programs

Python

seen = {}
def solve(start, end, boxes):
    tup = (start, end, boxes)
    if boxes == 1 or start >= end-1:
        val = (start + end) * (end-start+1) // 2
        seen[tup] = val
        return val
    lowest = 100000000000000000
    for x in range(end-1, start, -1):
        firstup = (x+1, end, boxes)
        first = seen[firstup] if firstup in seen else solve(x+1, end, boxes)
        if first >= lowest:
            break
        secondtup = (start, x-1, boxes-1)
        second = seen[secondtup] if secondtup in seen else solve(start, x-1, boxes-1)
        if second >= lowest:
            break
        lowest = min(lowest, x + max(first, second))
    seen[tup] = lowest
    return lowest
print([solve(1, n, 2) for n in range(1, 40)])

Formula

From Jon E. Schoenfield, Jan 10 2017: (Start)

Let f(L,U,B) be the number of firecrackers needed to determine M (in the worst case, using an optimal strategy), given that M is known to be in the closed interval [L, U] and B mailboxes remain available for testing. Then if B=1, we must sequentially test each integer number k of firecrackers from L+1 upward until the mailbox fails (since a failure will destroy our only remaining mailbox), and in the worst case (largest total number of firecrackers used) we will use L+1 + L+2 + ... + U firecrackers, so

f(L,U,1) = Sum_{k=L+1..U} k = (L+1+U)*(U-L)/2.

For B >= 2 and U > L, we have

f(L,U,B) = min_{k=L+1..U} (k + max(f(k,U,B), f(L,k-1,B-1)))

(where the minimum gives the best strategy (minimizing the total number of firecrackers needed), and max(f(k,U,B), f(L,k-1,B-1)) is the worst-case result from the outcomes of mailbox success and failure at a k-firecracker test)

and when L=U, we have

f(L,U,B) = 0 (since M has been determined).

Using the above recursive formula, we can compute

a(n) = f(0,n,2). (End)

It looks as though lim_{n->inf} a(n)/n^(3/2) = 0.818... - Jon E. Schoenfield, Jan 12 2017

Extensions

More terms from Joerg Arndt, Jan 11 2017