% LaTeX Article Template - customizing page format
%
% LaTeX document uses 10-point fonts by default.  To use
% 11-point or 12-point fonts, use \documentclass[11pt]{article}
% or \documentclass[12pt]{article}.


\documentclass[12pt]{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{enumerate}

% Set left margin - The default is 1 inch, so the following 
% command sets a 1.25-inch left margin.
\setlength{\oddsidemargin}{0.25in}

% Set width of the text - What is left will be the right margin.
% In this case, right margin is 8.5in - 1.25in - 6in = 1.25in.
\setlength{\textwidth}{6in}

% Set top margin - The default is 1 inch, so the following 
% command sets a 0.75-inch top margin.
\setlength{\topmargin}{-0.25in}

% Set height of the text - What is left will be the bottom margin.
% In this case, bottom margin is 11in - 0.75in - 9.5in = 0.75in
\setlength{\textheight}{8in}

% Set the beginning of a LaTeX document
\begin{document}

\title{Make \$ 1000 from simple combinatorics}   % Enter your title between curly braces
\author{}        % Enter your name between curly braces
\date{}          % Enter your date or \today between curly braces
\maketitle

 

This is Research Problem 12.5.6 of    the ``Upper and Lower Bounds '' book. You have to have a look at the book to get the connection between this problem and stochastic processes,  but the problem can be understood without knowing anything about this book. 

 Consider a number $\delta \leq 1/2$, an integer $N$ and the product measure $P$ on $\{0,1\}^N$, when on each factor one gives mass $\delta$ to $1$ and $1-\delta$ to $0$. Given an integer $q$ and a set $D \subset \{0,1\}^N$ we define 
\begin{eqnarray*} D^{(q)}= \{ (x_1, \cdots, x_N) \in \{0,1\}^N ; &&\forall (x_1^1, \cdots, x_N^1), \cdots ,(x_1^q, \cdots, x_N^q) \in D, \\
&&\exists i \leq N,  x_i =1, x_i^1, \cdots, x_i^q =0 \}. 
\end{eqnarray*}  % Enter section title between curly braces

If one identifies points in $\{0,1\}^N$ with subsets of $\{1,\cdots, N\}$, then $D^{(q)}$ is simply the collection of subsets of $\{1,\cdots,N\}$ that cannot be covered by $q$ elements of $D$. Also, $P$ is the law of a random set $J$ obtained as follows: for each  $i\in \{1, \cdots, N\}$ the probability that $i \in J$ is $\delta$, and these probabilities are independent over $i$. 

 Given a subset $I$ of $\{0,1\}^N$, we denote 
$$B(I) = \{(x_1, \cdots, x_N) \in \{0,1\}^N
; \forall i \in I, x_i=1\}. $$

 This is simply the collection of subsets of $\{1, \cdots, N\}$
that contain $I$.
\vskip5mm

\noindent{\bf Problem.} Can one find a number $q$, independent of $N$ and $\delta$, such that for each set $D$ with $P(D) \geq 1-1/q$ we can find a family $\cal G$ of subsets of $\{1, \cdots, N\}$ such that
$$ D^{(q)}\subset \bigcup_{I \in \cal G} B(I)$$
and 
$$ \sum_{I \in \cal G}\delta^{{\rm card}I}\leq 1/2?$$
If, rather that the above condition you obtain the weaker condition that 
$$ \sum_{I \in \cal G}\delta'^{{\rm card}I}\leq 1/2,$$
 where $\delta'$ depends on $\delta$ only, you get the money. (The case $\delta= 1/2$ won't get you anything, $q=2$ works.)

This problem is discussed in great detail in my paper  ``Are many small sets explicitly small?'', STOC'10 Proceedings of the 2010 ACM International Symposium on Theory of Computing, 13–35, ACM, New York, 2010. Problems related to this one (but in some sense less basic) are explained in  my paper ``Are all sets of positive measure essentially convex?'' Operator theory:  Advances and applications.  Vol. 77, Birkh\"auser,
1995, p. 295-310. 
\end{document}
