What is the minimal number of binary gates needed to compute AND and OR of $n$ input bits simultaneously? The trivial upper bound is $2n-2$. I believe that this is optimal, but how to prove this? The standard gate elimination technique does not work here as by assigning a constant to any of the input variables one trivializes one of the outputs.
The problem is also given as an exercise 5.12 in the book "Complexity of Boolean Functions" by Ingo Wegener in a slightly different form: "Let $f_n(x) = x_1\dots x_n \lor \bar{x}_1 \dots \bar{x}_n$. By the elimination method one can prove only a lower bound of size $n+\Omega(1)$. Try to prove larger lower bounds."