Flipping-Cups Vector Sequences

Problem

For an nn-dimensional vector A=(a1,,an)A=(a_1,\dots,a_n) with each ai{0,1}a_i\in\{0,1\}, call AA an nn-dimensional T-vector. For two such vectors A,BA,B, define d(A,B)=i=1naibid(A,B)=\sum_{i=1}^n|a_i-b_i|.

1. For A=(1,0,1,0,1)A=(1,0,1,0,1) and B=(0,1,1,1,0)B=(0,1,1,1,0), find d(A,B)d(A,B). 2. Consider a sequence of 55-dimensional T-vectors A1,A2,A_1,A_2,\dots with A1=(1,1,1,1,1)A_1=(1,1,1,1,1) and d(Ai,Ai+1)=2d(A_i,A_{i+1})=2 for all ii. Prove that the zero vector (0,0,0,0,0)(0,0,0,0,0) never appears in the sequence. 3. Consider a sequence of 1212-dimensional T-vectors A1,A2,A_1,A_2,\dots with A1=(1,1,,1)A_1=(1,1,\dots,1) and, for some jNj\in\mathbb N^{*}, Aj=(0,0,,0)A_j=(0,0,\dots,0); suppose there is a positive integer mm with d(Ai,Ai+1)=md(A_i,A_{i+1})=m for all ii. Find all possible values of mm.

Answer

Solution

Difficulty9/10
Topicscombinatorics, Modular Arithmetic, 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.