|
Search: id:A155940
|
|
|
| A155940 |
|
Array, read by antidiagonals, containing Vardi's optimal solution to the glove problem. |
|
+0
1
|
|
| 1, 2, 2, 3, 2, 2, 3, 3, 3, 4, 4, 3, 4, 4, 3, 4, 4, 4, 5, 5, 5, 5, 4, 5, 5, 5, 5, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 7, 7, 5, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7
(list; table; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
When n <= m, this is Vardi's optimal solution to what Weisstein politely calls the glove problem. For this sequence, we allow the array A[m,n] to have any nonnegative values of m and n. The rule governing the n=1 row prevents what would otherwise be monotonicity by row and by column.
|
|
REFERENCES
|
Hajnal, A. and Lovasz, L. "An Algorithm to Prevent the Propagation of Certain Diseases at Minimum Cost." Section 10.1 in Interfaces Between Computer Science and Operations Research: Proceedings of a Symposium Held at the Mathematisch Centrum, Amsterdam, September 7-10, 1976 (Ed. J. K. Lenstra, A. H. G. Rinnooy Kan and P. van Emde Boas). Amsterdam: Matematisch Centrum, 1978.
Vardi, I. "The Condom Problem." Ch. 10 in Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 203-222, 1991.
|
|
LINKS
|
Eric W. Weisstein, Glove Problem.
|
|
FORMULA
|
A[m,n] = 2 when m = n = 2. A[m,n] = (m+1)/2 when n = 1 and m = 2*k+1. A[m,n] = ceiling((m/2) + (2*n/3)) otherwise.
|
|
CROSSREFS
|
Sequence in context: A135975 A136032 A140361 this_sequence A153095 A054483 A108939
Adjacent sequences: A155937 A155938 A155939 this_sequence A155941 A155942 A155943
|
|
KEYWORD
|
easy,more,nonn,tabl
|
|
AUTHOR
|
Jonathan Vos Post (jvospost3(AT)gmail.com), Jan 31 2009
|
|
|
Search completed in 0.002 seconds
|
