Limit theory of discrete mathematics problems
Endre Cs�ka
{\normalsize Alfr�d R�nyi Institute of Mathematics
Budapest
Hungary
%We analyse and generalize the Manickam--Mikl�s--Singhi Conjecture and the Kikuta--Ruckle Conjecture using limit theory, an advanced version of asymptotic analysis. %{\color{red (Abstract for the case of I unify the two papers.) Limit theory means an advanced analysis of the asymptotic behavior of discrete problems when some finite parameter tends to infinity. Namely, we are looking for limits of finite problems for which we can prove that the solutions of the finite problems converge to the solution of the limit problem. We show this simple but powerful technique on three problems: the Manickam--Mikl�s--Singhi Conjecture, the Kikuta--Ruckle Conjecture and Alpern's Caching Game. %We will have a significant progress with these problems, especially with Alpern's Caching Game. %We purify and generalize some techniques which were successful in the limit theory of graphs and other discrete structures. We demonstrate how this technique can be used for solving different combinatorial problems, by defining the limit problems of the Manickam--Mikl�s--Singhi Conjecture, the Kikuta�-Ruckle Conjecture and Alpern's Caching Game.
comblimit.tex
% UK incentivise modelling maximise -ize -> -ise
% setup or setting?
% transfer not t

\documentclass[12pt,a4paper]{article}

%\documentclass[smallextended]{svjour3}

\usepackage[margin=20mm]{geometry}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{ae}
\usepackage{graphicx}
\usepackage[american]{babel}
\usepackage{amsfonts}
\let\proof\relax
\let\endproof\relax
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{enumitem}
\usepackage{wasysym}
\usepackage{paralist}
\usepackage{multirow}
\usepackage{cite}
\usepackage{pifont}
\usepackage{imakeidx}
\usepackage{arydshln}


\makeindex
\bibliographystyle{plain}
%\bibliographystyle{spbasic}%apalike}

%\usepackage{parskip}
%\setlength{\parskip}{3pt}

\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Def}[Theorem]{Definition}
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Question}[Theorem]{Question}
\newtheorem{Conjecture}[Theorem]{Conjecture}
\newtheorem{Problem}[Theorem]{Problem}
\newtheorem{Note}[Theorem]{Note}


\renewcommand{\d}{\ {\rm d}}
%\newcommand{\deg}{\text{deg}}
\newcommand{\E}{{\sf E}}
\newcommand{\eps}{{\varepsilon}}
\newcommand{\G}{\mathbb G}
\newcommand{\I}{\mu}
\newcommand{\N}{\mathbb N}
\renewcommand{\P}{{\sf P}}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\renewcommand{\:}{\colon}
\newcommand{\where}{\ |\ }
\newcommand{\bigwhere}{\ \big|\ }
\newcommand{\Bigwhere}{\ \Big|\ }

\usepackage{color}
\definecolor{red}{rgb}{0.8,0,0}
\definecolor{green}{rgb}{0,0.6,0}



\title{Limit theory of discrete mathematics problems}
% and a counterconjecture \\ on Alpern's Caching Game}
\author{Endre Cs�ka\\{\normalsize Alfr�d R�nyi Institute of Mathematics, Budapest, Hungary}}
%Supported by ERC grant 306493, MTA Renyi ``Lendulet" Groups and Graphs Research Group, ERC Advanced Research Grant No. 227701 and KTIA-OTKA grant No. 77780.}}
\date{}

\begin{document}
\maketitle
\begin{abstract}
%We analyse and generalize the Manickam--Mikl�s--Singhi Conjecture and the Kikuta--Ruckle Conjecture using limit theory, an advanced version of asymptotic analysis.

%{\color{red} (Abstract for the case of I unify the two papers.)}

Limit theory means an advanced analysis of the asymptotic behavior of discrete problems when some finite parameter tends to infinity.
Namely, we are looking for limits of finite problems for which we can prove that the solutions of the finite problems converge to the solution of the limit problem.
We show this simple but powerful technique on three problems: the Manickam--Mikl�s--Singhi Conjecture, the Kikuta--Ruckle Conjecture and Alpern's Caching Game.
%We will have a significant progress with these problems, especially with Alpern's Caching Game.


%We purify and generalize some techniques which were successful in the limit theory of graphs and other discrete structures. We demonstrate how this technique can be used for solving different combinatorial problems, by defining the limit problems of the Manickam--Mikl�s--Singhi Conjecture, the Kikuta�-Ruckle Conjecture and Alpern's Caching Game.

\end{abstract}

\section{Introduction}

When we want to solve a problem with a finite parameter, then one of the techniques we often try is to define and solve an infinite version of the problem, hoping that it helps with the original problem.
Here, an infinite version is defined by just exchanging some finite parameters to infinity and making the necessary modifications so as to get a meaningful problem.
But we have a suggestion how to do it better. Namely, we are looking for a problem for which we can prove that its solution is the same as the limit of the solutions of the finite problems. We emphasize that we should not care at all about whether this problem looks similar to the original problem, but all we should care about is this convergence. We call this technique the limit theory for discrete problems.

Limit theory techniques were used probably for the first time by Lov�sz and Szegedy (2006, \cite{lovasz2006limits}) introducing limit graphs called graphons.
This research followed the plan that they built a new language for graphs, a general theory about their limiting structures when their size tends to infinity.
Then the understanding of the space of graphons helped in the understanding of graphs.
This research resulted in a deep and successful theory\cite{lovasz2012large}, and provided a useful tool for solving a large class of graph theory problems.
Later, the same research plan was followed for the theories of many other discrete structures.

Now we are using the same technique with a slightly different plan.
Namely, we build a limit theory only for one unsolved discrete problem rather than a discrete structure.
We will apply this technique on three problems, demonstrating that limit theory is also be used as a general problem-solving technique.
We start with a simple story which is just a bit more than an asymptotic analysis: we generalize the Manickam--Mikl�s--Singhi Conjecture. Then we apply the same technique on the Kikuta--Ruckle Conjecture, where we will use the technique more deeply. Finally, we will show a very interesting, surprising and difficult application for Alpern's Caching Game, which shows the real power of the technique. We will also show how did our understanding of limit problems facilitated our understanding of the original problem, especially about Alpern's Caching Game.

%From a different point of view,

%Building limit theories for each problem might seem to require too much energy. But this is not the case because of the following reasons.

%\begin{trivlist}
  %\item
%   1. Graph limit theory was a very complex story, but limit theories are typically not that difficult. E.g. we should deal with the Central Limit Theorem rather than the Szemer�di Regularity Lemma.
  %\item

%   2. We are using the theory only for one problem, so we do not need to prove many technical lemmas if we do not use them in the final proof. If we finally manage to solve the original finite problem, then we do not need to prove any of these lemmas at all. Accordingly, we will only sketch the proofs in this paper, because we will not really need the full proofs.
  %\item

%  3. Building the first theory of a kind is always much more difficult than building a theory using the experience about the previous ones.
%\end{trivlist}


\section{Manickam--Mikl�s--Singhi Conjecture}

%These limit theory techniques can be applied in other combinatorial problems,

In our first and simplest example, we show an easy way to generalize a well-known conjecture.

\begin{Problem}[MMS-Problem] \label{MMS-problem}
For a fix $n, k \in \N$, find a sequence $a_i \in \R$, $a_1 + a_2 + ... + a_n = 0$ such that if $\{i_1, i_2, ..., i_k\} \subset \{1, 2, ..., n\}$ is a uniform random subset with cardinality $k$, then $\Pr\big( a_{i_1} + a_{i_2} + ... + a_{i_k} > 0 \big)$ is the largest possible.
\end{Problem}

Denote this maximum probability by $M(n, k)$. Two sequences are equivalent if after applying a permutation on one sequence, the two events that the sum is positive are the same.

\begin{Conjecture}[Manickam--Mikl�s--Singhi]
If $4k \le n$, then $M(n, k) = \frac{n-k}{n}$. The only optimal solution up to equivalence is $1-n, 1, 1, 1, ..., 1$.
\end{Conjecture}

The Manickam--Mikl�s--Singhi Conjecture is introduced in 1987 in \cite{manickam1987number}, and it has recently received a lot of attention, especially because of its connection to the Erd�s matching conjecture\cite{erdHos1965problem}.
In 2013, Huang and Sudakov\cite{huang2014minimum} proved it for $33k^2 < n$. In 2014, Chowdhury, Sarkis and Shahriari\cite{chowdhury2014manickam} proved for $8k^2 < n$. Then in 2015, Pokrovskiy\cite{pokrovskiy2015linear} proved for $k < \eps \cdot n$, but this improves the previous results only for $k > 10^{45}$.

\medskip

We consider an ``advanced asymptotic analysis'' of the problem when $n \rightarrow \infty$, and $\frac{k}{n}$ converges. Finding the right limit problem is not an obvious task. One of the problems is that the solution $1-n, 1, 1, 1, ..., 1$ does not have a limit when $n \rightarrow \infty$. We resolve this problem by dropping the condition $a_1 + a_2 + ... + a_n = 0$, but we want to maximize $\Pr\big( a_{i_1} + a_{i_2} + ... + a_{i_k} > \frac{k}{n}\sum a_i \big)$. This is clearly equivalent to the original problem. Now $-1, 0, 0, ..., 0$ is an equivalent form of the conjectured optimal solution, and we can say that the infinite sequence $-1, 0, 0, ...$ is a limit of it. We needed a few more observations to define the following limit problem.

\begin{Problem} \label{limitproblem}
For a fix $p \in (0, 1)$, we are looking for a countable sequence $a_1, a_2, ...$ of real numbers with $\sum a_i^2 < \infty$ and a real number $d$ which maximizes $\Pr\big( \sum a_i (x_i - p) + d x_0 > 0 \big)$, where $x_1, x_2, ...$ are indicator variables with probability $p$, and $x_0$ is a variable with standard normal distribution, and $x_0, x_1, x_2, ...$ are independent.
\end{Problem}

Denote this supremum probability by $M(p)$. (Which is a maximum, but we do not prove it here.)
We call this problem a limit problem of the Manickam--Mikl�s--Singhi Conjecure, because the following theorem holds.

\begin{Theorem} \label{MMS-limit}
For any sequence $(n_i, k_i)$, $n_i \rightarrow \infty$ and $\frac{k_i}{n_i} \rightarrow p \in (0, 1)$,
\begin{equation*}
\liminf_{\delta \rightarrow 0} M(p + \delta) \le \liminf M(n_i, k_i) \le
%\end{equation*}
%\begin{equation*}
\limsup M(n_i, k_i) \le \limsup_{\delta \rightarrow 0} M(p + \delta).
\end{equation*}
\end{Theorem}

\begin{proof}[Sketch of proof]
We can naturally convert a solution of the finite problem to a solution of the limit problem and vice versa. We only need to prove that the conversion error tends to 0 when $n \rightarrow \infty$.

The conversion of a solution of the finite problem (with large $n$ and $k$) to a solution of the limit game is essentially the following. We normalize the finite sequence by making its median $0$. The rest of the terms is $0$ and $d = 0$.

The conversion of a solution of the limit problem to a solution of a large finite problem is a bit more tricky. We keep a finite number of terms $a_i$ with the largest absolute values. Half of the rest of the terms will be $\eps$ and the other half will be $-\eps$, where the value $\eps$ is chosen so as to keep the total variance the same as it was in the limit problem. Using the following version of the Central Limit Theorem, we can deduce that this conversion error also tends to 0.

\begin{Lemma} \label{CLT}
For every $p \in (0, 1)$ and $\eps > 0$, there exists $\delta > 0$ such that for any sequence $-\delta < a_1, a_2, ..., a_n < \delta$
% with $\sum\limits_{i = 1}^n a_i = 0$ and $p(1-p) \sum\limits_{i = 1}^n a_i^2 = 1$
and $\big| \frac{k}{n} - p \big| < \delta$ and $t \in \mathbb{R}$, the following holds.
If $\{i_1, i_2, ..., i_k\} \subset \{1, 2, ..., n\}$ is a uniform random subset with cardinality $k$, then
\begin{equation*}
\Phi\big(\sigma(t - \eps)\big) - \eps < \Pr\Big( a_{i_1} + a_{i_2} + ... + a_{i_k} < \frac{k}{n} \sum_{i = 1}^n a_i + t \Big) < \Phi\big(\sigma(t + \eps)\big) + \eps,
\end{equation*}
where $\sigma^2 = \operatorname{Var}\big(a_{i_1} + a_{i_2} + ... + a_{i_k}\big)$ and $\Phi$ is the distribution function of the standard normal distribution. \qedhere
\end{Lemma}
\end{proof}

We analyzed the limit problem for all values of $p$, the results are summarized in Figure~1. This leads to a new conjecture as follows.

\begin{figure}[] \label{MMS-figure}
{\scriptsize M(p)}
\begin{center}
\includegraphics[width=0.97\textwidth]{MMS.pdf}{\scriptsize \ p}
\end{center}
\textbf{Figure 1.} $M(p)$ is the maximum of the functions in the figure. If $p$ is between 0 and $0.317...$ (or exactly $1/3$), then $-1$ is the best (and the other coefficients are 0), between $0.317...$ and $1/3$ the sequence $1, 1, 1$ is the best, between $1/3$ and $0.395...$ (and at $0.4$) the sequence $-1, -1, -1$, between $0.395...$ and $0.4$ the sequence $1, 1, 1, 1, 1$, between $0.4$ and $0.414...$ the sequence $-1, -1, -1, -1, -1$, and between $0.414...$ and $0.5$ the sequence $1, 1$.
\end{figure}

\begin{Conjecture}
The optimal solution of the limit game has the form $a_1 = a_2 = ... = a_q$ where $q \in \{1, 2, 3, 5\}$, and all other coefficients are 0. This is the only optimal solution up to equivalence.
\end{Conjecture}

Now we are ready to form the corresponding conjecture for the original problem.

\begin{Conjecture}
The optimal solution of the original finite game has the form $a_1 = a_2 = ... = a_q$ where $q \in \{1, 2, 3, 5\}$, and $a_{q+1} = a_{q+2} = ... = a_n = - \frac{q}{n-q} a_1$. This is the only optimal solution up to equivalence.
\end{Conjecture}


Now we show a possible way to prove the conjecture by analysing a very large but finite number of cases (most probably using a computer).
We say that a feasible normalized solution, or in short, a \emph{solution} for the limit problem (Problem~\ref{limitproblem}) is a sequence and a number $\big((a_i)_{i \in \N}, d \big)$, where
\begin{equation*}
\operatorname{Var}\Big(\sum a_i (x_i - p) + d x_0 \Big) = p(1-p)\sum_{i \in \N} a_i^2 + d^2 = 1.
\end{equation*}

\begin{Lemma}
We define the distance between two strategies $\big((a_i), d_{\alpha}\big)$ and $\big((b_i), d_{\beta}\big)$ by
\begin{equation*}
  \inf_{\pi_1, \pi_2, k} \Big(\sum_{i=1}^{k} \big|a_{\pi_i} - b_{\pi_i}\big| + \sup_{i>k}\big|a_{\pi_i}\big| + \sup_{i>k}\big|b_{\pi_i}\big|\Big),
\end{equation*}
where $\pi_1$ and $\pi_2$ are permutations on $\Z^+$. The topological space of the strategies induced by this distance function is compact.
\end{Lemma}

\begin{Lemma}
If for a solution $s = \big((a_i), d\big)$, $\Pr\big( \sum a_i (x_i - p) + d x_0 > -\eps \big) < v$, then there exists a neighborhood of $s$ in which for every solution $\big((a_i'), d'\big)$, we have $\Pr\big( \sum a_i' (x_i - p) + d' x_0 > 0 \big) < v$.
\end{Lemma}

With these two lemmas, we can hope that we can cover the solution space with a finite number of regions (open sets) so that we can show the conjectured inequality in each of these regions. Then we could modify these proofs for the limit problem so as to make it valid for the original discrete problem, as well.
For this, we would also need a version of Lemma~\ref{CLT} which gives an explicit $\delta > 0$ for each $\eps > 0$.



\section{Kikuta--Ruckle Conjecture}

We can use the same technique for the following generalization of the MMS-Problem, defined by Kikuta and Ruckle.\cite{kikuta2002continuous, alpern2013search}

\begin{Problem}[KR-Problem] \label{Kikuta}
$n, k \in \N$, and $d \in (0,1)$ are given. We want to find nonnegative real numbers $a_1, a_2, ..., a_n \ge 0$ with $a_1 + a_2 + ... + a_n = 1$ which maximizes $\Pr\big( a_{i_1} + a_{i_2} + ... + a_{i_k} > d \big)$, where $\{i_1, i_2, ..., i_k\} \subset \{1, 2, ..., n\}$ is a uniform random $k$-element subset.
\end{Problem}

Denote this supremum\footnote{We believe that this is a maximum. If we use ``$\ge d$'' rather than ``$> d$'', than due to the compactness of the space of solutions, we can even prove it.} probability by $K(k, n, d)$. Notice that if $d < \frac{k}{n}$, then $a_i = \frac{1}{n}$ provides $K(k, n, d) = 1$ and if $d = \frac{k}{n}$, then we get back the MMS-Problem.

\begin{Conjecture}[Kikuta--Ruckle]
For all $n, k \in \N$, and $d \in (0, 1)$, there is an optimal solution for the KR-Problem of the form $a_1 = a_2 = ... = a_s = \frac{1}{s}$ and $a_{s+1} = a_{s+2} = ... = a_n = 0$ for some $s \in \{1, 2, ..., n\}$.
\end{Conjecture}

The conjecture says nothing about the optimal value $s$, but this would be useful to know for proving the conjecture. Searching for the optimal values for small constant values $n, k$ did not really help, we will shortly see the reason of it. Instead, we will consider what happens if $n \rightarrow \infty$ and hereby we form a conjecture about the value of $s$.

The KR-Problem has one more parameter than the MMS-Problem, therefore, we have a larger freedom about defining limit problems of it. One of the most important limits is the case of $n \rightarrow \infty$, $\frac{k}{n} \rightarrow p \in (0, 1)$, $d = \frac{k}{n}$, which is just Problem~\ref{limitproblem}. But if $d > \frac{k}{n-1}$, then $s = n - 1$, or the corresponding solution $-1, 0, 0, ...$ for the MMS-problem is no longer good. Moreover, if $d > \frac{k}{n-c}$ for any constant $c$, then $s \le n - c$ provides probability 0. Therefore, if $n \rightarrow \infty$, $\frac{k}{n} \rightarrow p \in (0, 1)$, $d \rightarrow p$ and $n - \frac{k}{d} \rightarrow \infty$, then this leads to the following limit problem.

\begin{Problem} \label{Kikuta-limit}
For a fix $p \in (0, 1)$, we are looking for a countable sequence $0 \le a_1, a_2, ...$ of \emph{nonnegative} real numbers with $\sum a_i^2 < \infty$ and a real number $\sigma$ which maximizes $\Pr\big( \sum a_i (x_i - p) + \sigma x_0 > 0 \big)$, where $x_1, x_2, ...$ are indicator variables with probability $p$, and $x_0$ is a variable with standard normal distribution, and $x_0, x_1, x_2, ...$ are independent.
\end{Problem}

Denote this supremum probability by $K(p)$.
Figure~1 shows the efficiency of the conjectured optimal strategies.

\begin{figure}[] \label{MMS-figure}
{\scriptsize K(p)}
\begin{center}
\includegraphics[width=0.97\textwidth]{limit2.pdf}{\scriptsize \ p}
\end{center}
\end{figure}

Again, the reason why we consider it a true limit problem is the following theorem.

\begin{Theorem}
For any sequence $(n_i, k_i, d_i)$, $n_i \rightarrow \infty$ and $\frac{k_i}{n_i} \rightarrow p \in (0, 1)$, $d_i \rightarrow p$ and $n_i - \frac{k_i}{d_i} \rightarrow \infty$,
\begin{equation*}
\liminf_{\delta \rightarrow 0} K(p + \delta) \le \liminf K(n_i, k_i, d_i) \le
%\end{equation*}
%\begin{equation*}
\limsup K(n_i, k_i, d_i) \le \limsup_{\delta \rightarrow 0} K(p + \delta).
\end{equation*}
\end{Theorem}

The sketch of proof is the same as for Theorem~\ref{MMS-limit} with the additional observation that the median is at most $\frac{2}{n}$, and changing a few terms $a_i$ by $O\big(\frac{1}{n}\big)$ has a negligible effect.

There are some other interesting limit cases which are useful to analyse. The most important and interesting ones are the following.
\begin{itemize}
  \item $0 < \frac{k_i}{n_i} < d_i \rightarrow 0$, with different values of $\lim n_i - \frac{k_i}{d_i}$
  \item $\frac{1}{2} < \frac{k_i}{n_i} < d_i \rightarrow \frac{1}{2}$, with different values of $n_i - \frac{k_i}{d_i}$
  \item $n_i \rightarrow \infty$, $\frac{k_i}{n_i} \rightarrow p+$, $p \in \big\{\frac{1}{4}, \frac{1}{3}\big\}$, $d_i \rightarrow p$ and $n_i - \frac{k_i}{d_i} \rightarrow 1$
\end{itemize}

After analysing them, we were make a conjecture about how $s$ depends on $n$ and $d$. The full characterization is very long, but almost all information about it is summarized in the following stronger version of the Kikuta--Ruckle Conjecture.

\begin{Conjecture}
For all $n, k \in \N$, and $d \in (0, 1)$, there is an optimal solution for the KR-Problem of the form $a_1 = a_2 = ... = a_s = \frac{1}{s}$ and $a_{s+1} = a_{s+2} = ... = a_n = 0$, where\footnote{$\lfloor x \rfloor = \max \{y \in \Z : y < x\}$ and $\lfloor x \rfloor_{\text{odd}} = \max \{ y \equiv 1 \ (\text{mod }2), y < x\}$ and $\lfloor x \rfloor_{\equiv n \ (\text{mod }2)} = \max \{ y \equiv n \ (\text{mod }2), y < x\}$. If we define the KR-Problem with "$\le$" instead of "$<$", then here we have $y \le x$.}

\begin{equation*}
s \in \Big\{ \Big\lfloor \frac{1}{d} \Big\rfloor, \Big\lfloor \frac{1}{2d - 1} \Big\rfloor_{\textnormal{odd}}, 5, 7, 8, 11, 14, 17, 20, 23, 26, \Big\lfloor \frac{k}{d} \Big\rfloor, \Big\lfloor \frac{2k-n}{2d-1} \Big\rfloor_{\equiv n \ (\textnormal{mod }2)},
\end{equation*}
\begin{equation*}
n - 24, n - 21, n - 18, n - 15, n - 13, n - 12, n - 10, n - 9, n - 7, n - 6, n - 5, n - 4, n - 3, n\Big\}.
\end{equation*}
\end{Conjecture}

We show two interesting cases from the analysis.

\begin{itemize}
\item $s = n - 24$ is the best solution if $\frac{n}{3} < k < 0.3341... \cdot n + o(n)$ and $\frac{k-7}{n-21} \le d \le \frac{k-8}{n-24}$. The smallest example for this is $n = 413$, $k = 138$, $d \in \big[\frac{131}{392}, \frac{130}{389}\big)$. We note that the length of this interval is $\frac{1}{152488}$, and this solution beats $s = n - 4$ by less than $5 \cdot 10^{-6}$. The same does not work with $s = n - 27$, because it is beaten by $s = n - 4$.
\item When $\frac{10}{29} > d > \frac{k}{n} \rightarrow \frac{10}{29}$, then $s = 29$ provides probability $0.5694$, but $s = 2$ provides a very slightly higher probability $0.5707$. However, when $n$ is small, then the solution $s = 29$ slightly beats $s = 2$, thanks to the negative correlations between the events of choosing the different terms. But this happens only in some cases when $n$ is not too large and $\frac{k}{n}$ is very close to $\frac{10}{29}$. But in all of these cases, $\frac{k-1}{n-4} > \frac{10}{29}$ holds, and therefore, $s = n - 4$ beats both strategies. To sum up, the solution $s = 29$ was the only serious candidate for being optimal only in a finite number of cases (where $\frac{k}{n}, d \approx \frac{10}{29}$), but either $s = n - 4$ or $s = 2$ always beats it.
\end{itemize}

The author found this technique very useful for seeking for counterexamples, as well. Now he strongly believes that the conjecture is true, but it is rather ``accidentally true" and he doubts that there exists a simple proof. He found that the best candidates for counterexamples use the terms $\frac{2}{s}$, $\frac{1}{s}$ and $0$ for some $s$. Showing that there is no counterexample of this form is already a very difficult task, we need different arguments for the different cases.


\subsection{A new related question}

\begin{Problem} \label{problem-vectors}
There are $n, k \in \N$, and a vector space $V$ over $\R$ and $T \subset V$ is a convex closed set. We want to find vectors $a_1, a_2, ..., a_n$ with $a_1 + a_2 + ... + a_n = 0$ which maximizes $\Pr\big( a_{i_1} + a_{i_2} + ... + a_{i_k} \in T \big)$, where $\{i_1, i_2, ..., i_k\} \subset \{1, 2, ..., n\}$ is a uniform random $k$-element subset.
\end{Problem}

This problem can be traced back to the following problem.

\begin{Problem} \label{problem-numbers}
For a fix $n, k \in \N$ and $1 < M \in \R$, find a sequence $a_i \in \R$, $a_1 + a_2 + ... + a_n = 0$ such that if $\{i_1, i_2, ..., i_k\} \subset \{1, 2, ..., n\}$ is a uniform random subset with cardinality $k$, then $\Pr\big( 1 \le a_{i_1} + a_{i_2} + ... + a_{i_k} \le M \big)$ is the largest possible.
\end{Problem}

The key lemma to show the equivalence of these problems is the following.

\begin{Lemma}
For each convex closed set $S \subset V$, $0 \notin S$, there exists two vectors $v, w \in V$ and positive real numbers $\lambda_1, \lambda_2 \in \R^+$ such that
%\begin{equation*}
$\lambda_1 v, \lambda_2 v \in S$ and $\forall x \in S\: x \cdot w \in [\lambda_1, \lambda_2]$.
%\end{equation*}
\end{Lemma}

Problems \ref{problem-vectors} and \ref{problem-numbers} with $M = \lambda_2 / \lambda_1$ are equivalent because of the following reason. On one hand, for a sequence for Problem~\ref{problem-vectors}, the scalar product of the vectors with $w / \lambda_1$ provides a equally good sequence for Problem~\ref{problem-numbers}. On the other hand, a sequence for Problem~\ref{problem-numbers} multiplied by $\lambda_1 \cdot v$ provides an equally good solution for Problem~\ref{problem-vectors}.

Using the limit theory techniques in the same was as in the previous examples (we omit the details), we can form the following conjecture.

\begin{Conjecture}
The optimal solution for Problem~\ref{problem-numbers} has the form $a_1 = a_2 = ... = a_q$ and $a_{q+1} = a_{q+2} = ... = a_n = - \frac{q}{n-q} a_1$. $q$ is bounded on $\frac{k}{n} \in [0, 1]\ \setminus [\frac{1}{2} - \eps, \frac{1}{2} + \eps]$ for all $\eps > 0$.
\end{Conjecture}



\section{Alpern's Caching Game}

This section will be the most difficult one, but it will show the real power of the techniques and will provide very surprising results.

\begin{Def}
Alpern's Caching Game $G$ is defined as follows.
There are $n$ (potential) holes and $k$ nuts. The hider places (caches) each of $k$ nuts into one of the holes in a positive depth, so that the sum of the depths of the deepest nuts in the different holes (0 if no nut in the hole) must be at most 1. The searcher cannot observe anything about the placement, but he can dig at most depth $h$ in total. A nut is found if the searcher dug at least as much in that hole as the depth of the nut. The searcher can choose an adaptive digging strategy, continuously observing what and where he already found during the digging.
The searcher wins if he finds at least $j$ out of the $k$ nuts. Otherwise the hider wins.

%Formally, the hider chooses $H = (x, y) \in \big(\{1, 2, ..., n\} \times [0, 1]\big)^k$ so that $\sum\limits_{q=1}^n \max\limits_{i = 1}^k \big(\chi(x_i = q) \cdot y_i\big) \le 1$. Independently, the searcher chooses a function $d(H, t, q): \big(\{1, 2, ..., n\} \times [0, 1]\big)^k \times [0, h] \cdot \{1, 2, ..., n\} \rightarrow [0, 1]$ such that
%\begin{equation*}
%\forall H = (x, y) \in \big(\{1, 2, ..., n\} \times [0, 1]\big)^k,\ \forall t \in [0, h]\: \sum ...
%\end{equation*}
\end{Def}

We note that we need a measurability criterion for the strategy of the searcher, otherwise the winning probability might be not defined. We omit these technical details throughout the paper, including that ``all'' might mean ``all but a 0-measure set''. Strategy will mean mixed strategy.

\medskip

This problem was introduced by Alpern, Fokkink, Lidbetter and Clayton in \cite{alpern2012search}, a summary about the results and related questions of Alpern's Caching Game can be found in the survey book by Alpern, Fokkink, Leszek, Lindelauf \cite{alpern2013search}. More recent results are presented in \cite{csoka2016solution}.
We note that if we modify the problem so that the hider has no restriction on his caching time but he cannot use a depth more than 1, and $k \rightarrow \infty$ and $\frac{k}{n} \rightarrow d$, then we get back the Kikuta-Ruckle Problem.

This is a 2-player 0-sum game, therefore, there is a \textbf{value of the game} $v = v(k, j, n, h)$ with the following properties. Hider has a strategy so that for any strategy of the searcher, the searcher wins with probability at most $v$. Similarly, the searcher has a strategy so that he wins with probability at least $v$ against any strategy of the hider. These are called optimal strategies.

This problem is solved for $k = j = 2$, $n \le 4$.\cite{alpern2012search, csoka2016solution} The solution for $k = j = 2$, $n = 4$ is the following stepfunction.

\begin{center}
\noindent
{\scriptsize
\begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|c|c|}
  \hline
  \phantom{\Big( } $h$ & $[0, 1)$ & $\big[1, \frac{3}{2}\big)$ & $\big[\frac{3}{2}, \frac{5}{3}\big)$ & $\big[\frac{5}{3}, \frac{7}{4}\big)$ & $\big[\frac{7}{4}, \frac{9}{5}\big)$ & $\big[\frac{9}{5}, \frac{11}{6}\big)$ & $ \big[\frac{11}{6}, 2\big)$ & $\big[2, \frac{11}{5}\big)$ & $\big[\frac{11}{5}, \frac{7}{3}\big)$ & $\big[\frac{7}{3}, 3\big)$ & $[3, 4)$ & 4 \\
  \hline
  \phantom{\Big( }$v(2, 2, 4, h)$ & $0$ & $\frac{1}{10}$ & $\frac{3}{20}$ & $\frac{1}{5}$ & $\frac{9}{40}$ & $\frac{7}{30}$ & $\frac{1}{4}$ & $\frac{2}{5}$ & $\frac{9}{20}$ & $\frac{1}{2}$ & $\frac{3}{4}$ & 1 \\
  \hline
\end{tabular}
}
\end{center}

The optimal strategies show an even more chaotic picture. This suggested that the solution even for $k = j = 2$ is very irregular, and it is probably hopeless to characterize. However, using limit theory, we will show that it is not the case. First, we show a surprising property of the solution, and then we will partially solve the problem for $k = j = 2$. Some of the results will apply for $k = j > 2$ and $k = j + 1 > 2$.

There was a conjecture presented in \cite{alpern2013search} about a property of the optimal strategies of the hider. We do not define it here, but we will disprove a much weaker conjecture, i.e. Question~\ref{QX}. The answer was believed to be so obviously true that it was not even stated as a conjecture.\footnote{According to personal discussions with some of the authors.}

\begin{Def}
In Alpern's Caching Game, we say that a placement of the nuts is \textbf{extremal} if this requires total digging depth $1$, and any less is not enough. In other words, the sum of the depths of the deepest nuts in the different holes is exactly 1. A hiding strategy is called extremal if it is supported on extremal placements. The extremal version of the game means that the hider must use an extremal strategy.
\end{Def}

\begin{Question} \label{QX}
Does the hider always have an extremal strategy which is optimal? \\ Or (equivalently) are the values of the game and its extremal version the same?
\end{Question}



%\begin{Lemma} Consider all optimal (minimax value) strategies of the searcher in an extremal game. If there exists a non-extremal hiding strategy that is a strictly better response to all of them, then this implies a negative answer to question~\ref{QX}.
%\end{Lemma}

Now we define the limit of the game when the number of nuts to hide $k$ and to find $j$ are fixed, but the number of holes and the digging time $n, h \rightarrow \infty$.

\begin{Def}
The \textbf{limit game} with parameter $\lambda$ is defined as follows. The hider chooses a partitioning $a_1, a_2, ..., a_{k'} \in \Z^+$ where $\sum a_i = k$, and he chooses values (depths) $y_1, y_2, ... y_{k'} \in [0, 1]$ with $\sum y_i \le 1$ in the original, $\sum y_i = 1$ in the extremal version. Then for $k'$ independent uniform random numbers $x_1, x_2, ... x_{k'} \in [0, \lambda]$, $a_i$ number of nuts are placed at $(x_i, y_i)$. The searcher observes nothing. Now the searcher should define a function $f_t(x): [0, 1] \times [0, \lambda] \rightarrow [0, 1]$ which is monotone increasing in both parameters and $\int f_1(x) \d x \le 1$. Then we evaluate $f$ meaning that the searcher gets to know the smallest $t^*$ so that $f_{t^*}(x_i) \ge y_i$ for some $i$. If there is no such a nut position even for $f_1$, then the game ends. Otherwise the nuts at $(x_i, y_i)$ are found by the searcher, he gets to know their position and the number of them, and we remove these nuts. Then the searcher can change his function in the parameter interval $t \in (t^*, 1]$, and we re-evaluate $f$. The searcher wins if he finds at least $j$ nuts in total.
\end{Def}

We can also assume that $\int f_t(x) \d x = t$ for all $t \in [0, 1]$. This will be convenient to assume when we are showing lower bounds on the value of the game, and not to assume for upper bounds.

\begin{Theorem} \label{limitthm}
Consider the game with parameters $k, j, n, h$ and consider the limit game with $k, j, \lambda = \frac{n}{h}$. The ratio of the values of these two games $\in \big[\big(\frac{h-j}{h}\big)^j, 1\big]$.
\end{Theorem}

\begin{proof}[Sketch of proof]
Notice first that both players can apply on his strategy a uniform random permutation of the holes. If either of them does so, then whether the other player does it makes no difference in the expected result. Therefore, if we add to the rules that either or both players must use this randomization does not change the value of the game, as both players can secure himself this expected score.

%About the limit game, the searcher can apply the rule that if he finds a nut in a hole, he digs that hole until depth 1, so

About the limit game, notice that if two holes have the same depth, and nothing was found in them so far, then it does not matter which one the searcher continues digging. Therefore, we can assume that according to the random ordering of the holes, the depths remain monotone decreasing during the search.

Now let us see why does the value of the discrete problem with randomization and monotonicity converge to the value of the limit problem.

On one hand, any strategy of the searcher in the discrete game can be applied in the limit game by choosing $f_t$ in the interval $\big[\frac{i-1}{n},\frac{i}{n}\big)$ as the depth of the $i$th deepest hole after a total amount of digging $t$. This way the searcher can get at least the same score as in the discrete game.

On the other hand, a strategy of the searcher in the limit game can be applied in the discrete game as follows. The searcher chooses a random ordering of the holes. Then he caches so as to have depth $f_t\big(\frac{i-1}{h-j}\big)$ in the $i$th hole, except that if a nut is found in a hole, then he digs that hole until depth $1$. He does it for all $t \in [0, 1]$, in increasing order. This way, the searcher can get at least $\big( \frac{h-j}{h} \big)^j$ times the score of the limit game.
\end{proof}

\begin{Def}
The \textbf{double limit game} is defined as the limit game with $\lambda \rightarrow \infty$, as follows. The hider chooses $k$ values $y_1, y_2, ... y_k \in [0, 1]$ where $\sum y_i \le 1$ in the original, $\sum y_i = 1$ in the extremal version. Then for some subset $Q = \{ q_1, q_2, ..., q_j \} \subset \{1, 2, ..., k\}$ with a vector of positive real numbers $x_{q_1}, x_{q_2}, ... x_{q_j} \in \R^+$, the nuts are placed at $(x_{q_i}, y_{q_i})$. The searcher observes nothing. Independently from this, the searcher defines a strategy of the limit game with $\lambda = \infty$. The score of the searcher is the $j$-dimensional measure of the vectors $x_{q_1}, x_{q_2}, ... x_{q_j}$ for which he wins, summing up for all different $Q$. This is what the searcher aims to maximize and the hider aims to minimize, in expectation.
\end{Def}

\begin{Theorem} \label{2limitthm}
Fix $k \ge j \ge 2$, and consider a sequence of pairs $(n_i, h_i)$ so that $h_i \rightarrow \infty$ and $\frac{n_i}{h_i} \rightarrow \infty$. Then the values of the two games with parameters $k, j, n_i, h_i$, multiplied by $\big(\frac{n_i}{h_i}\big)^j$, tend to the value of the corresponding double limit game with $k$ and $j$.
\end{Theorem}

\begin{proof}[Sketch of proof]
The strategy of the searcher in both limit games can be applied in the corresponding double limit game, providing the same score. This proves one direction.

The other direction is a bit more technical. The first observation is that in the discrete game, if the hider puts more nuts in the same hole, and the searcher digs $\eps h$ holes until depth 1, then this already provides him a score $\omega\Big(\big(\frac{n_i}{h_i}\big)^{-j}\Big)$. Therefore the probability of such a placement should tend to 0. Thus, the limit value does not change if we forbid such a placement.

The next observation is the probability of finding more than $j$ nuts is $o\Big(\big(\frac{n_i}{h_i}\big)^{-j}\Big)$. Therefore, the probability of finding $j$ nuts is essentially the same as the expected number of $j$-element subsets of the nuts which would be found by the searcher if the other nuts had not been cached.

We sketch the rest of the proof only for $k = j = 2$, but similar technique works for all $k \ge j \ge 2$. The optimal strategy of the searcher in the double limit game can be applied in the limit game with a large parameter $\lambda$, simply by restricting $f$ to $[0, 1] \times \lambda$. In the part which is cut, the function value was at most $\frac{1}{\lambda}$, therefore, this strategy provides the same score unless if the depth of a nut is very low. However, there is a strategy which is very efficient in these cases: $f_1(x) = 1$ if $x < \frac{1}{2}$, and $f_1(x) = \frac{1}{\lambda}$ if $x \in \big[\frac{1}{2}, \frac{\lambda + 1}{2}\big)$, and 0 otherwise. If we use the cutted strategy mixed with this strategy, then for all possible hiding strategy, this mixed searching strategy will be (at least) almost as good as the original strategy in the double limit game.
\end{proof}

%We also note without details that there is a way to make the double limit problem played in a compact strategy space by proving that the searcher is better not using too much holes. We will not use this compactness, but having it is always a good sign. - Kevert strat�gi�k mellett nem vil�gos.

Consider any optimal strategy of the hider in the extremal game. This can be identified with the probability measure $\mu$ of the depth of a random nut.

\begin{Lemma} \label{round2opt}
In the extremal double limit game with $j = 2$, if the searcher finds a nut at depth $y \in \operatorname{supp}(\mu)$, then he should change $f$ so as to maximize the size of the interval $\{x \in [0, \infty) : f_1(x) = 1 - y\}$.
\end{Lemma}

\begin{Lemma}
$f_t(x) \in \{0\} \cup \operatorname{supp}(\mu)$ for all $(t, x) \in [0, 1] \times [0, 1]$.
\end{Lemma}

Both lemmas are true because otherwise the searcher could improve his expected score.

We also know that for all $y \notin \operatorname{supp}(\mu)$, the hiding strategy $y, 1-y$ does not provide higher expected score for the searcher than the value of the game. This \emph{seems to} contradict with the fact that the optimal strategy of the searcher focuses more on $\min\{y^+ \in \operatorname{supp}(\mu)\: y^+ > y\}$ and $\max\{y^- \in \operatorname{supp}(\mu)\: y^- < y\}$ than on $y$. While we failed to conclude any contradiction, but this argument along with some further analysis strongly supported the conjecture that $\operatorname{supp}(\mu) = [0, 1]$.

\begin{Theorem} \label{limitcounter}
If $k = j = 2$, then the values of the double limit game and its extremal version have different values, assuming that $\operatorname{supp}(\mu) = [0, 1]$.
\end{Theorem}

In fact, we do not need to assume that $\operatorname{supp}(\mu) = [0, 1]$, but it would be enough that there are at least a large finite number of points in $\operatorname{supp}(\mu)$ which are not far away from $\frac{1}{4}$.

Notice that this theorem together with Theorem~\ref{2limitthm} provides infinitely many counterexamples for Question~\ref{QX}.

\begin{proof}[Sketch of proof of Theorem~\ref{limitcounter}]

% Consider the optimal strategy of the searcher in the original game. This must be an optimal strategy in the extremal game, as well.

%If the searcher finds a nut at depth $y$, then he should change $f_1$ so as to maximize the interval where $f_1(x)=1-y$. Also, we can assume that $\int f_t(x) \d x = t$.
% This interval must be in $\big[0, \frac{1}{1-y}\big]$, because $\int f_1(x) \d x = 1$.


In the extremal double limit game, a mixture of the following two pure strategies of the searcher provides him score $\sqrt{2} + 1$.
According to Lemma~\ref{round2opt}, the strategy of the searcher is represented by the first function $f$ he chooses.
\begin{itemize}
\item $f_t(x) = 1$ if $x < t$, otherwise 0.
\item $f'_t(x) = \frac{1}{2}$ if $x < 2t$, otherwise 0.
\end{itemize}

Assume by contradiction that the two values are the same, denoted by $v$.
Consider an optimal strategy of the searcher in the double limit game. This provides the expected score at least $v$ against any strategy of the hider. Therefore, it provides expected score at least $v$ against all extremal hiding strategies, therefore it is an optimal strategy of the extremal double limit game, as well. But this strategy satisfies Lemma~\ref{round2opt}. Now consider the case when the hider chooses depths $y_1 = \frac{1}{4}$ and $y_2 = \frac{1}{4} - \tilde{\eps}$, where $\tilde{\eps}$ is a uniform random value from $[0, \eps]$. We consider the limit when $\eps \rightarrow 0+$. Consider an arbitrary strategy of the searcher. The probability that he finds both nuts at the same time point is 0. Let $t^*$ denote the time point when $\big(\frac{4}{3}, \frac{1}{4}\}$ is dug, and let $s$ denote the area which is dug at depth at least $\frac{1}{4}$ by the time point $t^*$. Formally,
\begin{equation*}
t^* = \sup_{t \in [0, 1]} \bigg\{ f_t \Big(\frac{4}{3}\Big) < \frac{1}{4} \bigg\},
\end{equation*}
\begin{equation*}
s = \sup_{x \in \R} \bigg\{ \sup_{t \in [0, 1]} \Big\{ f_t (x) < \frac{1}{4} \Big\} = t^* \bigg\}.
\end{equation*}
It is easy to check that the searcher cannot win if $y_1 > s$ or $y_2 > 2 - \frac{s}{2}$ (with an error $\rightarrow 0$ where $\eps \rightarrow 0$). Therefore, the score of the searcher is at most $s(2 - \frac{s}{2}) + o(1) \le 2 < \sqrt{2} + 1$, which is a contradiction.
%Let $g_t(x) = \frac{3}{4}$ if $f_t(x) \ge \frac{1}{4}$ and $g_t(x) = f_t(x)$ otherwise. Consider the smallest $t$ for which $\int g_t(x) \d x \ge 1$. Let $s$ be the largest value with $f_t(s) = \frac{1}{4}$. If the searcher does not find a nut until $t$, then he loses, because after finding the first nut, he will definitely not find the other one. In fact, the searcher cannot win if $x_1 > s$ or $x_2 > 2 - \frac{s}{2}$. Therefore, the score of the searcher is at most $s\big(2 - \frac{s}{2}\big) \le 2 < 1 + \sqrt{2}$, which is a contradiction.
\end{proof}

%To sum up, this argument implies a surprising negative answer to Question~\ref{QX} (and disproves the Kikuta-Ruckle Conjecture for Caching Games).

We note that there are a number of further limit games, e.g. if $j_i \rightarrow \infty$ and $\frac{j_i}{k_i}$ is convergent. These limit games might also be very useful, and may look very differently from the original game.



\subsection{Solution for the double limit game}

For first, it seemed that the extremal double limit game is easier to solve than the double limit game. The reason of it is that the strategy of the hider is a probability distribution on an interval in the extremal case, and on a two-dimensional domain in the non-extremal case. And therefore, the author expected the extremal (discrete) game to be easier to solve than the original game. But the truth seems to be the opposite.

The extremal double limit game is not solved yet. If somebody tries to solve it, then the author suggests considering the searcher's function $f_{t - 1}(x) = \chi(x < t) \cdot \big(1 - \frac{1}{t}\big)$ with probability more than $\frac{1}{2}$. The searcher's other pure strategy might be started by $f_t(x) = \chi(x < t) g(x)$ for $t \in [0, \eps]$ with a function $g(0) = 1$, $g'(0) \approx -0.1$. The author believes that the value of the game is $\approx 2.8$.

On the other hand, the double limit game has a surprisingly simple solution, as follows.

\begin{Theorem} \label{limitsolution}
If $\lambda \ge k = j$, then the value of the limit game is $\frac{k!}{\lambda^k}$, and therefore, the value of the double limit game is $k!$.
\end{Theorem}

The proof of Theorem~\ref{limitsolution} consists of Propositions~\ref{hiderstrategy} and \ref{searchersrtategy}, showing optimal strategies for the hider and the searcher.

\begin{Proposition} \label{hiderstrategy}
In the limit game, for $\lambda \ge k = j$, if the hider chooses a uniform random point $(y_1, y_2, ..., y_k)$ from the simplex $y_i > 0\ (\forall i \in \{1, 2, ..., k\})$, $\sum y_i \le 1$, then the searcher wins with probability at most $\frac{k!}{\lambda^k}$.
\end{Proposition}

We note that the searcher wins with exactly this probability provided that he always searches for nuts in places where it is possible to find one (e.g. never in depth $> 1$).

\begin{proof}[Proof of Theorem~\ref{hiderstrategy}]
Consider the measure space $T$ of $k$ time points $0 \le t_1 \le t_2 \le ... \le t_k \le 1$.
For each strategy of the searcher, consider the measure space $S$ of all allocations of the nuts for which the searcher would find all nuts.
To each allocation in $S$, we can assign the vector of time points when the searcher finds the nuts. This is an injective mapping from $S$ to $T$, and the inverse of it is measure-preserving. Therefore, the measure of $S$ is at most the measure of $T$.
The allocation of the nuts is a uniform random point $(x_1, y_1, x_2, y_2, ..., x_k, y_k)$ from the set $x_i \in [0, \lambda]$, $y_i > 0$, $\sum y_i \le 1$, but this set is factored by the $k!$ permutations of the $k$ indices. Therefore, the winning probability of the searcher is at most
\begin{equation*}
\frac{\operatorname{Vol}\big((t_1, t_2, ..., t_k) \bigwhere 0 \le t_1 \le t_2 \le ... \le t_k \le 1 \big)}{\frac{1}{k!} \cdot \lambda^k \cdot \operatorname{Vol}\big((y_1, y_2, ..., y_k) \bigwhere (\forall i\: y_i \ge 0), \sum y_i \le 1\big)}
\end{equation*}
\begin{equation} \label{limitproofeq}
= \frac{k! \operatorname{Vol}\big((t_1, t_2, ..., t_k) \bigwhere t_1, t_2 - t_1, t_3 - t_2, ..., t_k - t_{k-1} \ge 0; t_k \le 1 \big)}{\lambda^k \cdot \operatorname{Vol}\big((y_1, y_2, ..., y_k) \bigwhere (\forall i\: y_i \ge 0), \sum y_i \le 1\big)}
= \frac{k!}{\lambda^k}. \qedhere
\end{equation}
\end{proof}

\begin{Proposition} \label{searchersrtategy}
In the limit game, for $\lambda \ge k = j$, the searcher can win with probability at least $\frac{k!}{\lambda^k}$ by the following strategy.

He caches parallelly in a unit interval, and if he finds a nut, then he goes to the next interval. Formally, if he found so far $q$ nuts at the points in time $t_1, t_2, ..., t_q$, then with $t_0 = 0$, he chooses the function
\begin{equation*}
  f_t(x) = \sum_{i=1}^{q} \big(\chi(i - 1 \le x < i) \cdot (t_i - t_{i-1})\big) + \chi(q \le x < q + 1) \cdot (t - t_q).
\end{equation*}
\end{Proposition}

\begin{proof}
If there is a group of nuts in each of the intervals $[0, 1)$, $[1, 2)$, ... $[k' - 1, k')$, then the searcher finds all nuts. This has a probability $\frac{k'!}{\lambda^{k'}} \ge \frac{k!}{\lambda^k}$.
\end{proof}

\begin{Theorem}\label{doublelimitk-1}
For $k - 1 = j \ge 2$, the value of the double limit game is $k!$.
\end{Theorem}

\begin{proof}
The same strategy of the searcher as for $k = j$ provides a lower bound of $k \cdot (k-1)! = k!$.
If the hider chooses $(y_1, y_2, ..., y_k)$ uniformly randomly from the simplex $y_i \ge 0$, $\sum y_i = 1$, then the joint distribution of the $k - 1$ variables, say $(y_1, y_2, ..., y_{k - 1})$ is just a uniform random vector from the simplex $y_i \ge 0$, $\sum\limits_{i = 1}^{k-1} y_i \le 1$. Therefore, this shows an upper bound of $k \cdot (k-1)! = k!$, as well.
\end{proof}



\subsection{The discrete limit game}

As we will see, the solution for the double limit game for $k = j$ is conjectured and partially proved to be work if $h$ is larger than a constant. Therefore, it will be useful to define a limit game when $n \rightarrow \infty$ and $k$, $j$ and $h$ are constant. %(We no longer deal with extremal versions.)

\begin{Def}
The \textbf{discrete limit game} is defined as follows. The hider chooses $k$ values $y_1, y_2, ... y_k \in [0, 1]$ where $\sum y_i \le 1$. Then for some subset $Q = \{ q_1, q_2, ..., q_j \} \subset \{1, 2, ..., k\}$ with a vector of different positive integers $x_{q_1}, x_{q_2}, ... x_{q_j} \in \Z^+$, the nuts are placed at $(x_{q_i}, y_{q_i})$. The searcher observes nothing. Independently from this, the searcher defines a strategy of the limit game with $\lambda = \infty$. The score of the searcher is the number of the vectors $x_{q_1}, x_{q_2}, ... x_{q_j}$ for which he wins, summing up for all different $Q$. This is what the searcher aims to maximize and the hider aims to minimize, in expectation. The value of this game is denoted by $v^*(k, j, h)$.
\end{Def}

\begin{Theorem}
\begin{equation*}
v^*(k, j, h) = \lim_{n \rightarrow \infty} \frac{v(k, j, n, h)}{{n \choose j}}.
\end{equation*}
\end{Theorem}

\begin{proof}[Sketch of proof]
The proof will be similar to the proof for the limit game (Theorem~\ref{limitthm}).

In the original game, by hiding the nuts into random holes with depths $\frac{1}{k}$, we can get that $v(k, j, n, h) = O(n^{-j})$. On the other hand, for any $j$ nuts, out of the ${n + j - 1 \choose j}$ distributions of the number of nuts in the different holes, all but only $\Theta(n^{j-1})$ distributions uses $j$ different holes. Now the searcher can choose one of the $\Theta(n^{j-1})$ distributions uniformly at random, and digging in each of the holes until he finds at least the corresponding number of nuts. Hereby the searcher can get a score $\Omega(n^{-j+1})$ against placements that use the same hole for at least two nuts. Therefore, in any optimal hiding strategy, the probability that all nuts are placed in different holes should tend to 1.

Similar argument shows that if $n \rightarrow \infty$ and $\eps \rightarrow 0$, then the probability that the hider chooses depth less than $\eps$ should also tend to 0. This implies that forbidding searcher to dig in more than $\frac{1}{\eps}$ holes has a negligible effect.

Now we can convert any hiding and searching strategy of the discrete limit game to the original game (and vice versa) with an error tending to 0.
\end{proof}

\begin{Theorem} \label{discretelimitthm}
$v(k, j, n, h) \le {n + j - 1 \choose j} \cdot v^*(k, j, h)$
\end{Theorem}

\begin{proof}[Sketch of proof]
First, we replace the winning probability with the expected number of $j$-element subsets of nuts that would have been found.

Consider a hiding strategy of DG, and choose the same hiding strategy in G in the following sense. The hider chooses a uniformly random distribution of nuts out of the $\frac{n + k - 1}{k}$ possible distributions. We put nuts in the same hole to different depths. Then we will have $k$ distances: the depth of the first nut in each non-empty hole, and the additional depths of the further nuts from the previous nuts. These depths will be a random permutation of the depths used in DG.

Now any strategy of the searcher in G can be transformed to a strategy in DG by instead of digging a hole after finding a nut, the searcher digs in a new hole. This transformed strategy wins in the same number of cases.
\end{proof}

\begin{Conjecture} \label{discreteopt2}
If $k = j = 2$ and for any $h$, if $n$ is large enough, then the bound in Theorem~\ref{discretelimitthm} is sharp, and hereby the transformed hiding strategy in G is optimal.
\end{Conjecture}

\begin{Question}
Is Conjecture~\ref{discreteopt2} true for all $k = j > 2$?
\end{Question}



\subsection{Solutions for the original problem for $k = j = 2$}

In this section, unless we say the opposite, we \textbf{always assume that} $\boldsymbol{k = j = 2}$, namely, the hider caches two nuts, and the searcher aims to find both of them.
First, we present the following version of Conjecture~\ref{discreteopt2} which will simplify further analysis.

\begin{Conjecture} \label{pairdef}
For any $n$ and $h$, there always exists an optimal hiding strategy which is a probability distribution on the following strategies, denoted by pairs $(y_1, y_2)$. The searcher chooses two holes, maybe the same hole twice, uniformly randomly out of the ${n+1 \choose 2}$ choices. If he chooses two different holes $x_1 \neq x_2$, then he caches the two nuts to $(x_1, y_1)$ and $(x_2, y_2)$, or $(x_1, y_2)$ and $(x_2, y_1)$, with the same probabilities. If he chooses the same hole $x$, then he caches the nuts to $(x, y_1)$ and $(x, 1)$, or $(x, y_2)$ and $(x, 1)$, randomly.\footnote{The strategy $(1, 0)$ can be replaced by the strategy of caching both nuts in the same random hole in depth 1.}
\end{Conjecture}

This conjecture does not seem to be very difficult to prove. It would also be interesting whether we can say anything like that for other $k$ and $j$.

In the light of this conjecture, we can use the solution of the double limit game (Theorem~\ref{limitsolution}) for the original game as follows.

\begin{Theorem} \label{discretedoublelimit}
If the hider uses the strategy $(y_1, y_2)$ for a uniform random pair satisfying $y_1 \ge 0$, $y_2 \ge 0$, $y_1 + y_2 \le 1$, then the searcher wins with probability at most $\frac{2h^2}{n(n+1)}$.
If $h \in \Z^+$ and $h \le \frac{n + 1}{2}$, then the bound is sharp, namely, the value of the game is $\frac{2h^2}{n(n+1)}$.
\end{Theorem}

The proof will be very similar to the proof of Theorem~\ref{limitsolution}. It will follow from Theorem~\ref{hiderstrategyk} and Proposition~\ref{searcherstrategy2}, about the strategies of the hider and the searcher.

\begin{Conjecture} \label{discretedoublelimitconj}
The bound $\frac{2h^2}{n(n+1)}$ in Theorem~\ref{discretedoublelimit} is sharp if $\frac{h^2}{\lfloor h \rfloor} \le \frac{n+1}{2}$ and either $h \ge 3$ or $h = 3 - \frac{1}{q}$ for any $q \in \Z^+ \setminus \{3\}$.
\end{Conjecture}

\begin{Theorem} \label{largeh}
If $\frac{n+1}{2} \le h$, then the value of the game is $\frac{\lfloor h \rfloor}{n}$. This is always an upper bound for the value of the game, because of the hiding strategy of putting both nuts at the same random hole, at depth 1.
\end{Theorem}

\begin{Conjecture} \label{largehconj}
If $\frac{n+1}{2} \le \frac{h^2}{\lfloor h \rfloor}$, then the value of the game is $\frac{\lfloor h \rfloor}{n}$.
\end{Conjecture}

To challenge Conjectures \ref{discretedoublelimitconj} and \ref{largehconj}, or to try to prove them, the author suggests considering the following question.

\begin{Question}
For $n = 6$, $h = \sqrt{10.5} \approx 3.24$, whether the searcher can win with probability $\frac{1}{2}$?
\end{Question}

If $h < 3$, then the following discrete version of the searcher's double limit game solution can provide a better upper bound.

\begin{Theorem}\label{discretelimit}
If $h < \frac{a}{b}$ for some $a, b \in \Z^+$, then with the following hiding strategy, the searcher always wins with probability at most $\frac{2(a-1)(a-2)}{b(b-1) \cdot n(n+1)}$.

The hider chooses $y_1, y_2 \in \big\{\frac{1}{b}, \frac{2}{b}, \frac{3}{b}, ..., \frac{b - 1}{b}\big\}$, $y_1 + y_2 \le 1$ uniformly at random from the ${b \choose 2}$ possible choices, and chooses the hiding straregy $(y_1, y_2)$.
\end{Theorem}

\begin{proof}
The searcher can dig at most $a - 1$ possible hiding points (depths $\frac{1}{b}, \frac{2}{b}, ..., 1$). Given the strategy of searcher, if he finds the two nuts at the $i$th and $j$th searched possible hiding points, then it determines the two positions of the nuts. There are ${a - 1 \choose 2}$ different pairs of integers $1 \le i < j \le a - 1$, and there are ${b \choose 2} \cdot {n+1 \choose 2}$ possible pairs of positions, so the searcher cannot win with higher probability than $\frac{{a - 1 \choose 2}}{{b \choose 2} {n+1 \choose 2}} = \frac{2(a-1)(a-2)}{b(b-1) \cdot n(n+1)}$.
\end{proof}

\begin{Conjecture}
If $h \in \big(\frac{5}{2}, \frac{8}{3}\big) \cup \big[\frac{19}{7}, 2\big) \setminus \big\{3 - \frac{1}{q}\: q \in \Z^+\big\}$, then the best upper bound provided by Theorem~\ref{discretelimit} is sharp.
\end{Conjecture}

Now we have a conjecture of the solution for $h \in \big[\frac{5}{2}, n\big] \setminus \big[\frac{8}{3}, \frac{19}{7}\big)$.

For $h \in \big[0, \frac{9}{5}\big) \cup \big[2, \frac{7}{3}\big)$, the values of the games are the very same as for $n = 4$, written in the form $\frac{\alpha(h)}{n(n+1)}$. The proofs are also essentially the same.

\begin{Theorem} \label{solution2minus}
For $h \in \big[2 - \frac{1}{q-1}, 2 - \frac{1}{q}\big)$, $q \in \{5, 6, 7, 8, 9\}$ and $n \le q - 1$, and for $h \in \big[\frac{9}{5}, 2\big)$ and $n \le 5$, the values of the games are $\frac{9}{2}, 5, \frac{26}{5}, \frac{28}{5}, \frac{17}{3}$, $6$, respectively, divided by $n(n+1)$.

An optimal hiding strategy in the first 5 cases are $\big(\frac{1}{q}, \frac{q-1}{q}\big)$ with probability $\frac{1}{2}, \frac{1}{2}, \frac{2}{5}, \frac{2}{5}, \frac{1}{3}$, respectively, and $\big(\frac{q-1}{2q}, \frac{q+1}{2q}\big)$ otherwise.  In the last case, it is $\big(\frac{1}{4}, \frac{3}{4}\big)$ with probability $\frac{2}{3}$ and $\big(\frac{1}{2}, \frac{1}{2}\big)$ with probability $\frac{1}{3}$, or in other words, it is a uniform random extremal strategy with depths multiples of $\frac{1}{4}$. An optimal strategy of the searcher is the mixture of the followings, until finding the first nut (the continuation is obvious, see Lemma~\ref{round2opt}). He caches a random hole until depth $h - 1$, then another one until depth $\frac{3 - h}{2}$, then continues the first hole until depth 1. Or he just caches a random hole until depth $1$.
The former strategy is used with probabilities $\frac{1}{4}, \frac{2}{4}, \frac{3}{5}, \frac{4}{5}, \frac{5}{6}, 1$, respectively.
\end{Theorem}

The proof is a simple but long case analysis which we omit from this paper.

For $h \in \big[\frac{7}{3}, \frac{5}{2}\big)$, we expect a similar but more difficult structure of the solutions as for $h \in \big[\frac{9}{5}, 2\big)$. What we know is the following.

\begin{Lemma} \label{val5/2}
If $h < \frac{5}{2}$, then the value of the game is at most $\frac{11}{n(n+1)}$. This can be achieved by the strategy $\big(\frac{1}{4}, \frac{3}{4}\big)$ with probability $\frac{1}{2}$ and $\big(\frac{1}{2}, \frac{1}{2}\big)$ with probability $\frac{1}{2}$.
\end{Lemma}

\begin{Conjecture} \label{conj5/2}
The bound in Lemma~\ref{val5/2} is optimal for $h \in \big[\frac{17}{7}, \frac{5}{2}\big)$.
\end{Conjecture}

\begin{Note} \label{note}
If one wants to solve $h \in \big[ \frac{7}{3}, \frac{17}{7} \big)$, then we suggest considering mixtures of extremal hiding strategies $\big(\frac{10 - 4h}{3}, \frac{4h - 7}{3}\big)$, $\big(\frac{h - 1}{5}, \frac{6 - h}{5}\big)$, $\big(\frac{16 - 6h}{5}, \frac{6h - 11}{5}\big)$, $\big(\frac{h - 1}{3}, \frac{4 - h}{3}\big)$.
\end{Note}

\begin{Theorem} \label{19/7}
If $h < h^* = \frac{67}{25}$ or $\frac{51}{19}$ or $\frac{19}{7}$, and $n \le 11$, then the searcher can win with probability at most $\frac{14\frac{2}{53}}{n(n+1)}$, $\frac{14\frac{2}{27}}{n(n+1)}$, $\frac{14\frac{2}{11}}{n(n+1)}$, respectively, if the hider uses the following mixture of hiding strategies.
\begin{itemize}
  \item $\big(\frac{3 - h^*}{2}, \frac{h^* - 1}{2}\big)$ with probability $\frac{12}{53}$, $\frac{20}{81}$, $\frac{4}{33}$, respectively;
  \item $\big(\frac{h^* - 1}{6}, \frac{7 - h^*}{6}\big)$ with probability $\frac{4}{53}$, $\frac{4}{81}$, $\frac{4}{33}$, respectively;
  \item $\big(\frac{h^* - 1}{4}, \frac{5 - h^*}{4}\big)$ with probability $\frac{36}{53}$, $\frac{56}{81}$, $\frac{8}{11}$, respectively;
  \item $\big(\frac{h^* - 1}{6}, \frac{h^* - 1}{6}\big)$ with probability $\frac{1}{53}$, $\frac{1}{81}$, $\frac{1}{33}$, respectively.
\end{itemize}

In particular, in the third case, the four depths are $\big(\frac{1}{7}, \frac{6}{7}\big)$, $\big(\frac{2}{7}, \frac{5}{7}\big)$, $\big(\frac{3}{7}, \frac{4}{7}\big)$ and $\big(\frac{2}{7}, \frac{2}{7}\big)$.
\end{Theorem}

The proof again is a simple but long case analysis, which we omit from this paper.

\begin{Conjecture} \label{19/7conj}
If $h \in \big[\frac{8}{3}, \frac{19}{7}\big)$, then the best bound in Theorem~\ref{19/7} is sharp.
\end{Conjecture}

The table summarizes our results and conjectures for $k = j = 2$.

\begin{figure*}[htb]
\footnotesize{
\begin{center}
\begin{tabular}[center]{|c||c|c|c|c|}
\hline
$h$ & $v(2, 2, n, h)$ & validity & status & notes \\
\hline \hline
$[0, 1)$ & $0$ & every $n$ & \multirow{17}{*}{proved} & \multirow{6}{*}{proved in earlier papers for $n = 4$,} \phantom{\Big(}\\
\cline{1-3}
$\big[1, \frac{3}{2}\big)$ & $\frac{2}{n(n+1)}$ & \multirow{2}{*}{$n \ge 2$} & \multirow{69}{*}{bound} & \multirow{5}{*}{the same proof works for $n \ge 4$} \phantom{\Big(}\\
\cline{1-2}
$\big[\frac{3}{2}, \frac{5}{3}\big)$ & $\frac{3}{n(n+1)}$ & & & \phantom{\Big(}\\
\cline{1-3}
$\big[\frac{5}{3}, \frac{7}{4}\big)$ & $\frac{4}{n(n+1)}$ & $n \ge 3$ & & \phantom{\Big(}\\
\cline{1-3}
$\big[\frac{7}{4}, \frac{9}{5}\big)$ & $\frac{4.5}{n(n+1)}$ & $n \ge 4$ & & \phantom{\Big(}\\
\cline{1-3}\cline{5-5}
$\big[\frac{9}{5}, \frac{11}{6}\big)$ & $\frac{5}{n(n+1)}$ & $n \ge 5$ & & \multirow{7}{*}{proved in Theorem~\ref{solution2minus}} \phantom{\Big(}\\
\cline{1-3}
$\big[\frac{11}{6}, \frac{13}{7}\big)$ & $\frac{5.2}{n(n+1)}$ & $n \ge 6$ & & \phantom{\Big(}\\
\cline{1-3}
$\big[\frac{13}{7}, \frac{15}{8}\big)$ & $\frac{5.6}{n(n+1)}$ & $n \ge 7$ & & \phantom{\Big(}\\
\cline{1-3}
$\big[\frac{15}{8}, \frac{17}{9}\big)$ & $\frac{5\frac{2}{3}}{n(n+1)}$ & $n \ge 8$ & & \phantom{\Big(}\\
\cline{1-3}
$\big[\frac{17}{9}, 2\big)$ & $\frac{6}{n(n+1)}$ & $n \ge 5$ & & \phantom{\Big(}\\
\cline{1-3}\cline{5-5}
$\big[2, \frac{11}{5}\big)$ & $\frac{8}{n(n+1)}$ & \multirow{2}{*}{$n \ge 4$} & & \multirow{2}{*}{proved in earlier papers for $n = 4$,} \phantom{\Big(}\\
\cline{1-2}
$\big[\frac{11}{5}, \frac{7}{3}\big)$ & $\frac{9}{n(n+1)}$ & & &  the same proof works for $n \ge 4$ \phantom{\Big(}\\
\hline
$\big[\frac{7}{3}, \frac{17}{7} \big)$ & ? & \multirow{3}{*}{$n \ge 5$} & open & see Note~\ref{note} \phantom{\Big(}\\
\cline{1-2}\cline{4-4}\cdashline{5-5}
$\big[\frac{17}{7}, \frac{5}{2}\big)$ & $\frac{11}{n(n+1)}$ & & \multirow{7}{*}{upper} & see Lemma~\ref{val5/2} and Conjecture~\ref{conj5/2} \phantom{\Big(}\\
\cline{1-3}\cline{5-5}
$\frac{5}{2}$ & $\frac{12.5}{n(n+1)}$ & \multirow{3}{*}{$n \ge 6$} & \multirow{9}{*}{bound} & see Theorem~\ref{discretedoublelimit} and Conj.~\ref{discretedoublelimitconj} \phantom{\bigg(}\\
\cline{1-2}\cline{5-5}
$\big(\frac{5}{2}, \frac{8}{3}\big)$ & $\inf\limits_{\frac{a}{b} > h}\frac{2(a-1)(a-2)}{b(b-1) \cdot n(n+1)}$ & & \multirow{11}{*}{proved} & see Theorem~\ref{discretelimit} \phantom{\bigg(}\\
\cline{1-3}\cline{5-5}
$\big[\frac{8}{3}, \frac{67}{25}\big)$ & $\frac{14\frac{2}{53}}{n(n+1)}$ & & & \multirow{5}{*}{see Theorem~\ref{19/7} and Conj.~\ref{19/7conj}} \phantom{\bigg(}\\
\cline{1-2}
$\big[\frac{67}{25}, \frac{51}{19}\big)$ & $\frac{14\frac{2}{27}}{n(n+1)}$ & $n \ge 11$ & &  \phantom{\bigg(}\\
\cline{1-2}
$\big[\frac{51}{19}, \frac{19}{7}\big)$ & $\frac{14\frac{2}{11}}{n(n+1)}$ & & & \phantom{\bigg(}\\
\cline{1-3}\cline{5-5}
$\big[\frac{19}{7}, 3\big)$ & $\inf\limits_{\frac{a}{b} > h}\frac{2(a-1)(a-2)}{b(b-1) \cdot n(n+1)}$ & $n \ge 8$ & & see Theorem~\ref{discretelimit} (and Conj.~\ref{discretedoublelimitconj}) \phantom{\bigg(}\\
\hline
$\big\{3, 4, ..., \big\lfloor \frac{n+1}{2} \big\rfloor\big\}$ & $ \frac{2h^2}{n(n+1)}$ & every $n$ & proved & proved in Theorem~\ref{discretedoublelimit} \phantom{\Big(}\\
\hline
$\big(3, \frac{n}{2} + O(1)\big]$ & $ \frac{2h^2}{n(n+1)}$ & $n \ge 6$ & \multirow{1}{*}{upper} & see Conjecture~\ref{discretedoublelimitconj} \phantom{\Big(}\\ % see "\multirow{35}{*}{bound}"
\cline{1-3}\cline{5-5}
$\frac{n+1}{2} \le \frac{h^2}{\lfloor h \rfloor}$ & \multirow{3}{*}{$\frac{\lfloor h \rfloor}{n}$} & \multirow{3}{*}{every $n$} &  \multirow{1}{*}{proved} & see Conjecture~\ref{largehconj} \phantom{\Big(}\\
\cline{1-1}\cline{4-5}
$\big[\frac{n+1}{2}, n\big]$ & & & proved & proved in Theorem~\ref{largeh} \phantom{\Big(}\\
\hline
\end{tabular}
\end{center}
}
\end{figure*}


\subsection{Extensions for $k = j > 2$}

\begin{Theorem} \label{hiderstrategyk}
For $k = j \ge 2$, the value of the game is at most $\frac{h^k}{{n + k - 1 \choose k}}$.
\end{Theorem}

\begin{proof}
We convert the proof for the double limit game (Theorem~\ref{limitsolution}) to the a proof of the original problem as follows. The hider chooses how many nuts to put to each hole, choosing one of the ${n + k - 1 \choose k}$ possibilities uniformly at random. Now we consider the distance of each nut from the closest nut above it, or if there is no nut above it, then the depth of the nut (the distance from the top). We choose these $k$ depths $y'_1, y'_2, ... y'_k$ uniformly at random from the simplex $y'_i \ge 0$ ($\forall i \in \{1, 2, ..., k'\}$), $\sum y'_i \le 1$. From here, we can continue with the proof of Proposition~\ref{hiderstrategy} with exchanging $\lambda^k$ to ${n + k - 1 \choose k}$.
\end{proof}

\begin{Conjecture}
For $k = j \ge 2$, $\frac{k + 1}{k - 1} \le h \le \frac{n}{k}$, the value of the game is $\frac{h^k}{{n + k - 1 \choose k}}$.
\end{Conjecture}

Most probably, this conjecture can be proved for integral $h$. So this weaker, seemingly easier conjecture is the following.

\begin{Conjecture}
For $k = j \ge 2$, $h \in \Z^+$ and $h \le \frac{n}{k}$, the value of the game is $\frac{h^k}{{n + k - 1 \choose k}}$.
\end{Conjecture}

The author believes that the same proof works here as for $k = j = 2$, in Proposition~\ref{searcherstrategy2}. Except that when the searcher finds a nut and chooses $h$ new holes, then he might choose again any holes which had a nut at its current bottom. We should find the right probabilities for each of these choices so as for each distribution of the number of nuts in the different holes, the searcher finds them with the same probability.

We also mention that there are many other potentially useful limit problems not yet considered, when $k \rightarrow \infty$.


\subsection{Proofs}

\begin{proof}[Proof of Theorem~\ref{largeh}]
Hiding both nuts at the same hole in depth 1 is provides hiding probability at most $\frac{\lfloor h \rfloor}{n}$.

Consider now the following strategy of the searcher. He chooses $\lfloor h \rfloor$ holes at random, and starts digging in them parallelly, until a nut is found, at hole $x$ in depth $y$. Then he continues digging $x$ until depth $1$. Then if $y \le \frac{1}{2}$, then he digs the other $\lfloor h \rfloor - 1$ chosen holes until depth $1 - y$, and the remaining $n - \lfloor h \rfloor$ holes until depth $\min(y, 1-y)$.

If the nut with the higher depth (if the depths are the same, then either nut) is in one of the $\lfloor h \rfloor$ chosen holes, then the searcher finds both nuts. This has a probability at least $\frac{\lfloor h \rfloor}{n}$.

This strategy uses a total digging amount of
\begin{equation*}
1 + \big(\lfloor h \rfloor - 1\big) \cdot \max(y, 1-y) + \big(n - \lfloor h \rfloor\big) \cdot \min(y, 1-y)
\end{equation*}
\begin{equation*}
= 1 + (n - 1) \cdot \min(y, 1-y) + \big(\lfloor h \rfloor - 1\big) \cdot \big( \max(y, 1-y) - \min(y, 1-y) \big)
\end{equation*}
\begin{equation*}
\le 1 + (2h - 2) \cdot \min(y, 1-y) + (h - 1) \cdot \big( \max(y, 1-y) - \min(y, 1-y) \big)
\end{equation*}
\begin{equation*}
= 1 + (h - 1) \cdot \big( \max(y, 1-y) + \min(y, 1-y) \big) = 1 + (h - 1) = h. \qedhere
\end{equation*}
\end{proof}

\begin{Proposition}\label{searcherstrategy2}
Consider the following strategy of the searcher. He chooses $h$ holes at random, and he is parallelly digging them until a nut is found (but until at most depth 1, when the game ends). If a nut is found at a depth $y$, then he chooses $h$ new holes, as follows. With probability $\frac{2h}{n+1}$, he chooses the hole in which the nut was found, and the remaining $h - 1$ or $h$ holes are randomly chosen from the other $n - h$ holes. Then he digs these holes in depth $1 - y$ (more).
\end{Proposition}

\begin{proof}%[Proof of Proposition~\ref{searcherstrategy2}]
Assume first that the hider caches the two nuts in two different holes. If exactly one of them are in one of the $h$ holes the searcher started with, and the other one is in the next $h$ holes, then the searcher finds both nuts. Therefore, the searcher finds both nuts in expectedly $h \cdot \big(h - \frac{2h}{n + 1}\big)$ number of cases out of the $n \choose 2$ pairs, which happens with probability
\begin{equation*}
\frac{h \cdot \big(h - \frac{2h}{n + 1}\big)}{{n \choose 2}}
 = \frac{2h \cdot \frac{(n+1)h - 2h}{n+1}}{n(n-1)} = \frac{2h \cdot \frac{(n-1)h}{n+1}}{n(n-1)} = \frac{2h^2}{n(n+1)}.
\end{equation*}

Assume now that the hider caches the two nuts in the same hole. If this nut is in the first $h$ holes chosen by the searcher, and the searcher chooses to continue digging in this hole, then he finds both nuts. This has probability
\begin{equation*}
\frac{h}{n} \cdot \frac{2h}{n+1} = \frac{2h^2}{n(n+1)}.
\end{equation*}

To sum up, this strategy of the searcher finds both nuts with probability at least $\frac{2h^2}{n(n+1)}$, against any strategy of the hider.
\end{proof}



\section*{Acknowledgements}

I am thankful to Dezs� Mikl�s for his observations and suggestions about the MMS-problem.

The research was supported by the European Research Council (grant agreements no. 306493 and 648017).

\bibliography{caching}

\end{document}

comblimit.bbl
\begin{thebibliography}{10}

\bibitem{alpern2013search}
Steve Alpern, Robbert Fokkink, G~Leszek, Roy Lindelauf, VS~Subrahmanian, et~al.
\newblock {\em Search theory: a game theoretic perspective}.
\newblock Springer Science \& Business Media, 2013.

\bibitem{alpern2012search}
Steve Alpern, Robbert Fokkink, Thomas Lidbetter, and Nicola~S Clayton.
\newblock A search game model of the scatter hoarder's problem.
\newblock {\em Journal of The Royal Society Interface}, 9(70):869--879, 2012.

\bibitem{chowdhury2014manickam}
Ameera Chowdhury, Ghassan Sarkis, and Shahriar Shahriari.
\newblock The manickam--mikl{\'o}s--singhi conjectures for sets and vector
  spaces.
\newblock {\em Journal of Combinatorial Theory, Series A}, 128:84--103, 2014.

\bibitem{csoka2016solution}
Endre Cs{\'o}ka and Thomas Lidbetter.
\newblock The solution to an open problem for a caching game.
\newblock {\em Naval Research Logistics (NRL)}, 2016.

\bibitem{erdHos1965problem}
P�l Erd{\H{o}}s.
\newblock A problem on independent r-tuples.
\newblock In {\em ARTICLE IN PRESS B. Bollob{\'a}s et al./Journal of
  Combinatorial Theory, Series A}. Citeseer, 1965.

\bibitem{huang2014minimum}
Hao Huang and Benny Sudakov.
\newblock The minimum number of nonnegative edges in hypergraphs.
\newblock {\em The Electronic Journal of Combinatorics}, 21(3):P3--7, 2014.

\bibitem{kikuta2002continuous}
Kensaku Kikuta and William~H Ruckle.
\newblock Continuous accumulation games on discrete locations.
\newblock {\em Naval Research Logistics (NRL)}, 49(1):60--77, 2002.

\bibitem{lovasz2012large}
L{\'a}szl{\'o} Lov{\'a}sz.
\newblock {\em Large networks and graph limits}, volume~60.
\newblock American Mathematical Soc., 2012.

\bibitem{lovasz2006limits}
L{\'a}szl{\'o} Lov{\'a}sz and Bal{\'a}zs Szegedy.
\newblock Limits of dense graph sequences.
\newblock {\em Journal of Combinatorial Theory, Series B}, 96(6):933--957,
  2006.

\bibitem{manickam1987number}
N~Manickam and D~Mikl{\'o}s.
\newblock On the number of non-negative partial sums of a non-negative sum.
\newblock In {\em Colloq. Math. Soc. J\'anos Bolyai}, volume~52, pages
  385--392, 1987.

\bibitem{pokrovskiy2015linear}
Alexey Pokrovskiy.
\newblock A linear bound on the manickam--mikl{\'o}s--singhi conjecture.
\newblock {\em Journal of Combinatorial Theory, Series A}, 133:280--306, 2015.

\end{thebibliography}
