Minimum number of vertices to intersect each subcube I came across the following puzzle today that I'm curious about:
Given $d<n$, what's the least number of vertices one needs to remove from the Boolean cube $\{0,1\}^n$ so that there is no $d$-dimensional subcube remaining?
I'm hoping for a nice combinatorial proof.
Edit: to clarify what I mean by a subcube, it's the combinatorial entity rather than the linear-algebraic one (which would be an affine subspace of $\mathbb{F}_2^n$). So a subcube is a subset of the Boolean cube of the form 
$$ C = \{(b_1,\ldots,b_n) : b_i = s_i \text{ if }i\in S\}$$
for some set of indices $S$ and some fixed values $s_i$ for $i\in S$, and the dimension of the subcube is $n-|S|$.
 A: This is a partial answer, but maybe I'll be able to extend it later. 
Given integers $0\le d\le n$ by $f(n,d)$ we denote the minimum number of vertices of $n$-dimensional Boolean cube $D^n\equiv\{0,1\}^n$, intersecting each its (canonical) $d$-dimensional subcube. 
As a first non-trivial upper bound we show that $f(n,d)\le 2^n/(d+1)$. Indeed, for each vertex $x\in D^n$ by $\Sigma(x)\in\Bbb Z_{d+1}$ we denote the sum of its coordinates modulo $d+1$ and for each integer $0\le r<d$ put $ D^n_r=\{x\in D^n:\Sigma(x)=r\}$. Since for each $d$-dimensional subcube $C$ of $D^n$ we have $\Sigma(C)=\Bbb Z_{d+1}$, the intersection $C\cap D^n_r$ is non-empty for each $r$. Since $D^n$ is a union of its mutually disjoint  $d+1$ subsets $D^n_r$, one of these sets has size at most $2^n/(d+1)$.
Now we consider the case $d=2$. We already have bounds $2^n/4\le f(n,2)\le 2^n/3$. We improve the lower bound and this once more refute the conjecture $f(n,d)=2^{n-d}$. :-) 
To show that $f(3,2)=2$ we can choose a set consisiting of two opposite vertices of the $3$-dimensional cube.
Next we claim that $f(4,2)=5$. The upper bound follows from the inequality $f(4,2)\le 2^4/3$. Now assume that we have  a set $F\subset D^4$ such that each 2-dimensional subcube of $D^4$ intersects $F$. A $2$-dimensional subcube of $D^4$ is defined by two coordinates where the coordinates of vertices of the subcube are fixed. There are ${4 \choose 2}$ choices for these two coordinates and $2^2$ choices for these values. So the total number of $2$-dimensional subcubes of $D^4$ is ${4 \choose 2}\cdot 2^2$. From the other hand, each point $x\in F$ belongs to exactly ${4 \choose 2}$ $2$-dimensional subcubes. Thus $|F|\ge {4 \choose 2}\cdot 2^2/{4 \choose 2}=4$ and the equality holds only when there are no two points from $F$ belonging to one $2$-dimensional subcube. We claim that the latter case is impossible, thus $|F|>4$ and $4<f(4,2)=5$. Indeed, for each vertex $x\in F$ let $B_1(x)$ be the set of all points $y$ from $D^n$ such that Hamming distance $d(x,y)$ between $x$ and $y$ (that is the number of coordinates $i$ such that $x_i\ne y_i$) is at most $1$. Then $|B_1(x)|=5$. Since $|F|\cdot 5=20>16=2^4$ there exist different points $x,y\in F$ such that the intersection $B_1(x)$ and $B_1(y)$ is non-empty. Then Hamming distance $d(x,y)$ between $x$ and $y$ is at most $2$, which directly implies that there is a $2$-dimensional subcube containing both $x$ and $y$. 
Given $f(4,2)=5$, since for $n\ge 4$ we can partition $D^n$ into $2^{n-4}$ disjoint $4$ dimensional subcubes, we have $f(n,d)\ge 5\cdot 2^{n-4}>2^{n-2}$ (for $n\ge 4$). 
Now we apply our bounds for small $n$. For $n=5$ we have $5\cdot 2\le f(5,2)\le 2^5/3$, so $f(5,2)=10$. For $n=6$ we have $5\cdot 4\le f(6,2)\le 2^5/3$, so $20\le f(6,2)\le 21$, and I guess that the exact value will be written in the first comment. :-)
