MathDB
CSMO 2017 Grade 10 Problem 1

Source: China Southeast Mathematical Olympiad

July 31, 2017
functionalgebra

Problem Statement

Let xi∈{0,1}(i=1,2,⋯ ,n)x_i \in \{0, 1\} (i = 1, 2, \cdots, n). If the function f=f(x1,x2,⋯ ,xn)f = f(x_1, x_2, \cdots, x_n) only equals 00 or 11, then define ff as an "nn-variable Boolean function" and denote Dn(f)={(x1,x2,⋯ ,xn)∣f(x1,x2,⋯ ,xn)=0}D_n (f) = \{ (x_1, x_2, \cdots, x_n) | f(x_1, x_2, \cdots, x_n) = 0 \}. (1)(1) Determine the number of nn-variable Boolean functions; (2)(2) Let gg be a 1010-variable Boolean function satisfying g(x1,x2,⋯ ,x10)≡1+x1+x1x2+x1x2x3+⋯+x1x2⋯x10(mod2)g(x_1, x_2, \cdots, x_{10}) \equiv 1 + x_1 + x_1 x_2 + x_1 x_2 x_3 + \cdots + x_1 x_2\cdots x_{10} \pmod{2} Evaluate the size of the set D10(g)D_{10} (g) and ∑(x1,x2,⋯ ,x10)∈D10(g)(x1+x2+x3+⋯+x10)\sum\limits_{(x_1, x_2, \cdots, x_{10}) \in D_{10} (g)} (x_1 + x_2 + x_3 + \cdots + x_{10}).
Back to ProblemsView on AoPS