Orthogonal Sign Vectors

Problem

Let An={(x1,,xn)xi{1,1}}A_n=\{(x_1,\dots,x_n)\mid x_i\in\{-1,1\}\}. For x,yAn\vec x,\vec y\in A_n define xy=x1y1++xnyn\vec x\cdot\vec y=x_1y_1+\cdots+x_ny_n; if xy=0\vec x\cdot\vec y=0, call x\vec x and y\vec y orthogonal.

1. For x=(1,1,1,1)\vec x=(1,1,1,1), list all elements of A4A_4 orthogonal to x\vec x. 2. Let B={xyx,yAn}B=\{\vec x\cdot\vec y\mid\vec x,\vec y\in A_n\}. If mBm\in B, prove that m+nm+n is even. 3. If AAnA\subseteq A_n with every two elements of AA orthogonal, find the maximum size of AA for n=8n=8 and for n=14n=14.

Answer

Solution

Difficulty9/10
Topicscombinatorics, Modular Arithmetic, Linear Algebra, Casework, vectors

Whiteboard

Your sketch is saved only in this browser. To share it, export your drawing as an image (whiteboard menu → Export as → PNG), then upload that image in the comments below.

Discussion

Ask questions, share alternate solutions, and use LaTeX freely.

0 comments
Log in to join the discussion.

No comments yet.