Let $p, q \in \mathbb R$ be positive reals for which $p + q = 1$. How to prove that for any two natural numbers $n, m$ the following inequality is true?
$(1 - p^n)^m + (1 - q^m)^n \ge 1$
I don't have a big knowledge about solving inequalities, so I tried to use cauchy-schwarz inequality, binomial theorem and some other baisc techniques, but it lead me nowhere. I've been thinking about it for a long time and now I'm completly stuck.
Consider $m \times n$ grid (matrix if you like) with $m$ rows and $n$ columns, with either $0$ or $1$ numbers in its cells. Now let $p$ be probability that a cell contains $1$ and $q$ be probability that a cell contains $0$, so we have $p+q=1$.
Now what is the probability of (event $A$) each row having at least one $0$ in it? That is exactly the $P(A)=(1-p^n)^m$ ($p^n$ for a row made of $1s$, $1-p^n$ for row with at least one $0$, $(1-p^n)^m$ then for $m$ rows with this property). Similarly, probability of (event $B$) having in each column at least one $1$, is $(1-q^m)^n$. Thus we have
$$ (1-p^n)^m+(1-q^m)^n = P(A) + P(B) $$
Now notice that $P(A \cup B) = 1$. This is because we will always have all rows containing a $0$ or all columns containing a $1$. If there would be for example no row containing a $0$, it would mean there is a row full of $1$s, which means all columns contain a $1$ (at least the one from the row which is filled with them). You can argue similarly for the case when there would be no column containing a $1$...
Another way to see this is to notice
$$P(A \cup B) = 1- P(\overline{A \cup B}) = 1- P(\overline{A} \cap \overline{B}) = 1$$
since $\overline{A}$ (having a row consisting only of $1s$) and $\overline{B}$ (having a row consisting only of $0$s) are clearly mutually exclusive, you can't have both at the same time, therefore $P(\overline{A} \cap \overline{B}) = 0$.
Putting all these together gives $$(1-p^n)^m+(1-q^m)^n = P(A) + P(B) = P(A \cup B) + P(A \cap B) \geq P(A \cup B) = 1 $$
The problem 19 found here states and proves more general inequality using double induction:
$$(1-x_1 \dots x_n)^m + (1-y_1^m) \dots (1-y_n^m) \geq 1,\ x_i, y_i \in [0,1],\ x_i + y_i = 1.$$
You can just plug in the $x_i = p$, $y_i=q$ and reproduce the proof.
Let there are two coins each with probability of head $p$. Let coin 1 has been tossed $n$ times independently and this whole scheme is repeated independently for $m$ times.
Similarly coin 2 is tossed $m$ times independently and this whole scheme is repeated independently for $n$ times and independently of coin 1.
$A$= at least one tail occurs in the string of 1st $n$-tosses, 2nd $n$ tosses, $\cdots$, $m^{th}$ $n$-tosses for coin 1
$B$= at least one head occurs in the string of 1st $m$-tosses, 2nd $m$ tosses, $\cdots$, $n^{th}$ $m$-tosses for coin 1
Notice the desired form is $P(A\cup B)\leq1$
