MathDB

4

Part of ICMC 2

Problems(2)

ICMC 2018/19 Round 1, Problem 4

Source: Imperial College Mathematics Competition 2018/19 - Round 1

8/7/2020
For u,v∈R4u,v \in\mathbb{R}^4, let <u,v><u,v> denote the usual dot product. Define a vector field to be a map ω:R→R\omega:\mathbb{R}\to\mathbb{R} such that <ω(z),z>=0, ∀z∈R4.<\omega(z),z>=0,\ \forall z\in\mathbb{R}^4.
Find a maximal collection of vector fields {ω1,...,ωk}\left\{\omega_1,...,\omega_k\right\} such that the map Ω\Omega sending zz to λ1ω1(z)+⋯+λkωk(z)\lambda_1\omega_1(z)+\cdots+\lambda_k \omega_k(z), with λ1,…,λk∈R\lambda_1,\ldots,\lambda_k\in\mathbb{R}, is nonzero on R4\{0}\mathbb{R}^4\backslash\{0\} unless λ1=⋯=λk=0\lambda_1=\cdots=\lambda_k=0
college contests
ICMC 2018/19 Round 2, Problem 4

Source: Imperial College Mathematics Competition 2018/19 - Round 2

8/7/2020
Let f:{0,1}n→{0,1}⊆Rf:\{0, 1\}^n \to \{0, 1\} \subseteq \mathbb{R} be a function. Call such a function a Boolean function. Let ∧\wedge denote the component-wise multiplication in {0,1}n\{0,1\}^n. For example, for n=4n = 4, (0,0,1,1)∧(0,1,0,1)=(0,0,0,1).(0,0,1,1) \wedge (0,1,0,1) = (0,0,0,1).
Let S={i1,i2,…,ik}⊆{1,2,…,n}S = \left\{i_1,i_2,\ldots ,i_k\right\} \subseteq \left\{1,2,\ldots ,n\right\}. ff is called the oligarchy function over SS if f(x)=xi1,xi2,…,xik  (with the usual multiplication),f (x) = x_{i_1},x_{i_2},\ldots,x_{i_k}\ \text{ (with the usual multiplication),}
where xix_i denotes the ii-th component of xx. By convention, ff is called the oligarchy function over ∅\emptyset if ff is constantly 1.
(i) Suppose ff is not constantly zero. Show that ff is an oligarchy function if and only if ff satisfies f(x∧y)=f(x)f(y), ∀x,y∈{0,1}n.f(x\wedge y)=f(x)f(y),\ \forall x,y\in\left\{0,1\right\}^n. Let YY be a uniformly distributed random variable over {0,1}n\left\{0, 1\right\}^n. Let TT be an operator that maps Boolean functions to functions {0,1}n→R\left\{0, 1\right\}^n\to\mathbb{R}, such that
(Tf)(x)=EY(f(x∧Y)), ∀x∈{0,1}n(Tf)(x)=E_Y(f(x\wedge Y)),\ \forall x\in\left\{0,1\right\}^n
where EY()E_Y() denotes the expectation over YY. ff is called an eigenfunction of TT if ∃λ∈R\{0}\exists\lambda\in\mathbb{R}\backslash\left\{0\right\} such that (Tf)(x)=λf(x), ∀x∈{0,1}n(Tf)(x)=\lambda f(x),\ \forall x\in\left\{0,1\right\}^n
(ii) Prove that ff is an eigenfunction of TT if and only if ff is an oligarchy function.
college contestsfunction