CDAM: Computational, Discrete and Applicable Mathematics@LSE

 CDAM Research Report, LSE-CDAM-2008-20

September 2008

On Ruckle's Conjecture on Accumulation Games

Steve Alpern, Robbert Fokkink, and Kensaku Kikuta

In an accumulation game, the Hider secretly distributes his given total wealth h among n locations, while the Searcher picks r locations and confiscates the material placed there. The Hider wins if what is left at the remaining n-r locations is at least 1; otherwise the Searcher wins. Ruckle's Conjecture says that an optimal Hider strategy is to put an equal amount h=k at k randomly chosen locations, for some k: We extend the work of Kikuta and Ruckle by proving the Conjecture for the following cases, among others: r = 2 or n-2; n≤ 7; n = 2r -1; h < 2 + 1/(n-r-1) and n ≤ 2r. The last result uses the Erdos-Ko-Rado theorem. We establish a connection between Ruckle's Conjecture and the difficult Hoeffding problem of bounding tail probabilities of sums of random variables.

A PDF file (244 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2008-20, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7494.
Fax: +44(0)-20-7955 6877.

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2007