GATE 2026 DA Q.19: solution and answer

GATE 2026 · DAQ.19 · 1 mark · MCQ

Let $M$ be a randomly chosen non-empty subset of $S = {1, 2, 3, \dots, 2026}$ . Which of the following is the probability that the product of all the elements of $M$ is even?

(A)
$2^{1013} (2^{1013} - 1) / 2^{2026}$
(B)
$2^{1013} / 2^{2026}$
(C)
$2^{1013} (2^{1013} - 1) / (2^{2026} - 1)$
(D)
$1/ (2^{2026} - 1)$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The probability that the product is even is $\frac{2 ^{1013} ( 2 ^{1013} - 1 )}{2 ^{2026} - 1}$ , which is option (C).

Official answer: CSource: Official answer key, GATE 2026 DA (IIT Guwahati)

$M$ is chosen uniformly from the non-empty subsets of $S = {1, 2, \dots, 2026}$ . $S$ has $2^{2026}$ subsets and one of them is empty, so the sample space has $2^{2026} - 1$ equally likely outcomes.
A product of integers is even exactly when at least one factor is even. So the product is odd exactly when every element of $M$ is odd. Count the favourable outcomes through this complement.
Among $1, 2, \dots, 2026$ there are $1013$ odd numbers and $1013$ even numbers.
The non-empty subsets of $S$ made only of odd numbers are the non-empty subsets of a $1013$ -element set. There are $2^{1013} - 1$ of them.
The non-empty subsets with an even product number $(2^{2026} - 1) - (2^{1013} - 1) = 2^{2026} - 2^{1013} = 2^{1013} (2^{1013} - 1) .$
Divide by the size of the sample space: $P (product is even) = \frac{2 ^{1013} ( 2 ^{1013} - 1 )}{2 ^{2026} - 1} .$
This is option (C). As a check, $2^{1013} \cdot 2^{1013} = 2^{2026}$ , so the ratio is slightly less than $1$ , as it should be. Option (A) wrongly divides by $2^{2026}$ , which includes the empty set.

KEY IDEA

Use the complement. A product is odd only if every element is odd. Count non-empty subsets of the $1013$ odd numbers, and divide by the number of non-empty subsets of $S$ .

WATCH OUT FOR

Dividing by $2^{2026}$ (counting the empty set as an outcome) gives option (A). The question says $M$ is non-empty, so the denominator is $2^{2026} - 1$ . A second slip is to forget to remove the empty set from the all-odd count, which should be $2^{1013} - 1$ .

From the GATE 2026 DA paper. Every question of this paper · Download the full paper · All 5 Counting & axioms questions, with notes

GATE 2026 DA Q.19: solution and answer

Answer and solution

More Counting & axioms questions