MathDB
Problems
Contests
National and Regional Contests
USA Contests
USA - College-Hosted Events
Harvard-MIT Mathematics Tournament
2017 Harvard-MIT Mathematics Tournament
19
19
Part of
2017 Harvard-MIT Mathematics Tournament
Problems
(1)
2017 Guts #19: Number of odd coefficients
Source:
2/21/2017
Find (in terms of
n
≥
1
n \ge 1
n
≥
1
) the number of terms with odd coefficients after expanding the product:
∏
1
≤
i
<
j
≤
n
(
x
i
+
x
j
)
\prod_{1 \le i < j \le n} (x_i + x_j)
1
≤
i
<
j
≤
n
∏
(
x
i
+
x
j
)
e.g., for
n
=
3
n = 3
n
=
3
the expanded product is given by
x
1
2
x
2
+
x
1
2
x
3
+
x
2
2
x
3
+
x
2
2
x
1
+
x
3
2
x
1
+
x
3
2
x
2
+
2
x
1
x
2
x
3
x_1^2 x_2 + x_1^2 x_3 + x_2^2 x_3 + x_2^2 x_1 + x_3^2 x_1 + x_3^2 x_2 + 2x_1 x_2 x_3
x
1
2
x
2
+
x
1
2
x
3
+
x
2
2
x
3
+
x
2
2
x
1
+
x
3
2
x
1
+
x
3
2
x
2
+
2
x
1
x
2
x
3
and so the answer would be
6
6
6
.
algebra