Separating disjoint polyhedra with LP duality This is question 4.35 from Introduction to Linear Optimization by Bertsimas and Tsitsiklis. 
The problem

Consider two non-empty polyhedra $P=\{\mathbf{x}\in\mathbb{R}^n\ |\ \mathbf{Ax}\leq\mathbf{b}\}$ and $Q=\{\mathbf{x}\in\mathbb{R}^n\ |\ \mathbf{Dx}\leq\mathbf{d}\}$.
(a) Devise a linear programming problem such that: if $P\cap Q\neq\varnothing$, it returns a point in $P\cap Q$; if $P\cap Q=\varnothing$, the linear programming problem is infeasible.
(b) Suppose that $P\cap Q$ is empty. Use the dual of the problem you have constructed in part (a) to show that there exists a vector $\mathbf{c}$ such that $\mathbf{c}^\text{T}\mathbf{x}<\mathbf{c}^\text{T}\mathbf{y}$ for all $\mathbf{x}\in P$ and $\mathbf{y}\in Q$.

Attempted solution
I think I have an answer for part (a):
$$ \begin{array}{rl} \text{max}\quad&\mathbf{0}^\text{T}\mathbf{x} \\ \text{s.t.}\quad&\mathbf{Ax}\leq\mathbf{b} \\ & \mathbf{Dx}\leq\mathbf{d} \end{array} $$
This seems to accomplish the requirements of part (a). I am stuck on part (b). The dual of the above linear program is
$$ \begin{array}{rl}\text{min}\quad&\mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d}\\\text{s.t.}\quad&\mathbf{p}_1^\text{T}\mathbf{A}+\mathbf{p}_2^\text{T}\mathbf{D}=\mathbf{0}^\text{T}\\ & \mathbf{p}_1,\mathbf{p}_2\geq\mathbf{0} \end{array} $$
If we assume the primal is infeasible (i.e. $P\cap Q=\varnothing$), then the dual is either infeasible or unbounded. Since $\mathbf{p}_1=\mathbf{0}$, $\mathbf{p}_2=\mathbf{0}$ is feasible for the dual, it must be unbounded. I think this might be a useful fact, but I can't see exactly how.
Geometrically, this question is very straightforward. But I'm struggling to come up with the algebra to show the existence of this $\mathbf{c}$.
Similar question
The question found here is similar, but I'm not interested in computing the separating hyperplane, just proving its existence.
 A: (a) The linear program
\begin{array}{rl}
\max &\mathbf{0}^\text{T}\mathbf{x} \\
\text{s.t.}&\mathbf{Ax}\leq\mathbf{b} \tag{P}\label{P}\\
& \mathbf{Dx}\leq\mathbf{d}
\end{array}
suggested by the OP responds to the problem.
(b) Since $P \cap Q = \varnothing$, each of these two points satisfies exactly one of the two constraints in \eqref{P} (from the definition of $P$ and $Q$).
The OP's deduction is correct:

The dual for \eqref{P} is
  \begin{array}{rl}
\min & \mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} \\
\text{s.t.} & \mathbf{p}_1^\text{T}\mathbf{A}+\mathbf{p}_2^\text{T}\mathbf{D}=\mathbf{0}^\text{T} \tag{D} \label{D} \\
& \mathbf{p}_1,\mathbf{p}_2\geq\mathbf{0}
\end{array}
  The infeasibility of \eqref{P} and the feasibility of \eqref{D} (with $\mathbf{p}_1 = {\bf 0}, \mathbf{p}_2 = {\bf 0}$) implies that \eqref{D} is unbounded.

From the unboundedness of \eqref{D}, we deduce that for each $z \in \Bbb R$, there exists $\mathbf{p}_1,\mathbf{p}_2\geq\mathbf{0}$ such that $\mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} \le z$.  In particular, we fix $\epsilon > 0$ and take $z = -\epsilon$, so that $$\mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} < 0 \tag{*} \label{*}.$$
For all ${\bf x} \in P$ and ${\bf y} \in Q$, we have (from the definition of $P$ and $Q$)
\begin{align}
\mathbf{Ax} &\leq \mathbf{b} \tag{1}\label{1} \\
\mathbf{Dy} &\leq \mathbf{d} \tag{2}\label{2}
\end{align}
Multiply $\mathbf{p}_1^\text{T}$ and $\mathbf{p}_2^\text{T}$ on both sides of \eqref{1} and \eqref{2} respectively.  (We can do so since $\mathbf{p}_1 \ge {\bf 0}, \mathbf{p}_2 \ge {\bf 0}$.)
\begin{align}
\mathbf{p}_1^\text{T}\mathbf{Ax} &\leq \mathbf{p}_1^\text{T}\mathbf{b} \tag{3}\label{3} \\
\mathbf{p}_2^\text{T}\mathbf{Dy} &\leq \mathbf{p}_2^\text{T}\mathbf{d} \tag{4}\label{4}
\end{align}
Substitute the constraint in \eqref{D} into \eqref{4}.
$$(-\mathbf{p}_1^\text{T}\mathbf{A}){\bf y} \leq \mathbf{p}_2^\text{T}\mathbf{d} \tag{4'}\label{4'}$$
Add \eqref{3} and \eqref{4'}.
$$\mathbf{p}_1^\text{T}\mathbf{A} ({\bf x} - {\bf y}) \le \mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} \stackrel{\eqref{*}}< 0 \tag{$\star$} \label{fin}$$
It's evident from \eqref{fin} that ${\bf c} = (\mathbf{p}_1^\text{T}\mathbf{A})^\text{T} = \mathbf{A}^\text{T} \mathbf{p}_1$ satisfies
$$\mathbf{c}^\text{T}\mathbf{x}<\mathbf{c}^\text{T}\mathbf{y} \quad \forall \mathbf{x} \in P, \forall \mathbf{y} \in Q.$$
