Understanding a Proof in COMBINATORICA 3 ( 3 - 4 ) (1983) 325--329 Preliminary words on notation:


*

*$[n]$ denotes the set $\{1, 2, \ldots, n\}$.

*For two vectors $x, y \in [k]^n$ we write $a(x, y) = h$ to denote that they agree on $h$ positions.

*For some fixed $v \in [n]^k$ we denote by $g(v)$ the least amount of questions necessary to determine v if all questions are of the form "What is $a(v, q)$ for some question vector q?" and all questions are asked simultaneously.


In his proof on an upper bound on $g(v)$, Chvátal proposes the following sufficient condition on the amount of questions needed to determine $v$:

Proof. By a difference pattern, we shall mean a nonempty set $I$ of subscripts along with two distinct colors $x_i$, $y_i$ for each $i \in I$; we shall say that this difference pattern
  is split by a question $q$ if the number of subscripts $i \in I$ with $q_i \neq x_i$ differs from the number of subscripts $i \in I$ with $q_i \neq y_i$. Note that every two distinct candidates $x, y$ for the mystery vector $v$ define a unique difference pattern by $i \in I$ iff $x_i \neq y_i$, and
  that this difference pattern is split by a question q if and only if $a(q, x ) \neq a ( q , y)$. Thus we only need establish the existence of a set $Q$ of questions such that every difference pattern is split by some question in $Q$ ...

My two questions about this proof concern the two emphasized parts of the cited text:


*

*Is the first assertion (i.e. ... if and only if $a(q, x ) \neq a ( q , y)$ ...) true? Consider for example $x = [0 \, 1]$, $y = [1 \, 0]$, $I = \{2\}$ and $q = [1 \, 1]$. Certainly, by definition, we see that the subvectors induced by $I$ are split by $q$ as $x_2 = q_2 \neq y_2$. On the other hand we have $a(q, x) = 1 = a(q, y)$. This seems to contradict the author's claim, what did I miss?

*I flat out fail to grasp the second assertion: Why does splitting every difference pattern imply that the set of questions $Q$ suffices to recover $v$?

 A: 
  
*
  
*Is the first assertion (i.e. ... if and only if $a(q, x ) \neq a ( q , y)$ ...) true? Consider for example $x = [0 \, 1]$, $y = [1 \,
> 0]$, $I = \{2\}$
  

No.

$x, y$ ... define a unique difference pattern by $i \in I$ iff $x_i \neq y_i$

If $x = [0 \, 1]$, $y = [1 \, 0]$ then $I = \{1, 2\}$.
The contributions to $a(q, x)$ and $a(q, y)$ of the indices not in $I$ are equal by definition of $I$.



  
*I flat out fail to grasp the second assertion: Why does splitting every difference pattern imply that the set of questions $Q$ suffices
  to recover $v$?
  

Suppose you cannot recover $v$. Without loss of generality we can select two distinct candidates $u$ and $w$ which are compatible with the answers given to $Q$. But by definition of $Q$ it contains a question $q$ which splits the difference pattern of $u$ and $w$, so they cannot both be compatible with the answers given to $Q$. Therefore by contradiction there are not two distinct candidates for $v$.

As an aside, the thing which I see as an error is (my emphasis)

Note that every two distinct candidates $x, y$ for the mystery vector $v$ define a unique difference pattern by $i \in I$ iff $x_i \neq y_i$

This is trivially wrong, but it doesn't seem that the proof actually relies on it at all.
