SAT1000 - P911

It is given that $p_1 = 1$ and $p_i + p_{i+1} = 1\,,\;1\leq i \leq 99$ we get that every alternate $p$ is $1$ starting from $p_1$ . So we get characteristic sequence of subset $P$ of $E$ as:

$Seq(P) = 1, 0, 1, 0, 1, 0, 1,\cdots , 1, 0$

Similarly in characteristic sequence of $Q$ we have $q_1 = 1$ and $q_j + q_{j+1} + q_{j+2} = 1\,,\;1\leq j\leq 98$ . So characteristic sequence of subset $Q$ of $E$ is:

$Seq(Q) = 1, 0, 0, 1, 0, 0, 1, 0, 0, 1,\cdots , 1, 0, 0, 1$

So, in $Seq(P)$ , every $(2m-1)th$ number is $1 \;\forall\; m\in \mathbb{N}, 1 \leq m \leq 50$ Similarly, in $Seq(Q)$ every $(3n-2)th$ number is $1\;\forall\;n\in\mathbb{N}, 1 \leq n \leq 3 of 4$

Let $a_k \in P \cap Q$ . Then $a_k \in P$ and $a_k \in Q$ . So $p_k = q_k = 1$ . So there must exist $m,n$ such that

$2m - 1 = 3n - 2$

To get the cardinality of intersection $P$ and $Q$ we have to find number of all such pairs $(m,n$ . Solving the equation,

$2m = 3n - 1$

Since LHS is even, in order to RHS to be even $n$ must be odd. Now number of odd numbers in the range $1$ to $34$ is $17$ and for every odd $n$ within that range, there will exist $m$ such that $1 \leq m \leq 50$ .

So, the cardinality of $P\cap Q$ is $17$ .