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.
Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

		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. Email: info@maths.lse.ac.uk