\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Brazil 2020/5}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 74}
\maketitle
\section*{Problem}
Let $n$ and $k$ be positive integers with $k \le n$.
In a group of $n$ people,
each one or always speak the truth or always lies.
Arnaldo can ask questions for any of these people
provided these questions are of the type: ``In set $A$,
what is the parity of people who speak truthfully?'',
where $A$ is a subset of $k$ people.
(The answer is either ``even'' or ``odd'').
Arnaldo wants to figure out which people are liars.
For each pair $(n,k)$,
determine the minimum number of questions needed,
or prove that this task is impossible.
\section*{Video}
\href{https://www.youtube.com/watch?v=2ku744eaxYA&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/2ku744eaxYA}}
\newpage
\section*{Solution}
The answer is that the task is possible exactly
when $k$ is even in which case exactly $n$ questions are needed.
Treat each person as an element in $\FF_2$,
where $1$ for truth and $0$ for liar.
If you ask person $p$ about the set $A$,
their response is
\[ (p+1) + \sum_{a \in A} \pmod 2. \]
So in other words, a query amounts to
sampling a set of either $k-1$ elements ($p \in A$)
or $k+1$ elements $(p \notin A$), and taking the sum.
Now, if $k$ is odd, the task is impossible, because
replacing every $x \mapsto x+1$ changes no responses.
On the other hand, when $k$ is even, the following $n$ queries suffice:
\begin{itemize}
\ii Query $(x_1 + \dots + x_k) - x_i$ for $i=1,\dots,k$
By summing, one gets the value of $(k-1)(x_1 + \dots + x_k)$,
and hence knows $x_i $ for $1 \le i \le k$.
\ii Query $(x_1 + \dots + x_{k-2}) + x_i$ for $i = k+1, \dots, n$.
This gets $x_i$ for $i \ge n$.
\end{itemize}
Moreover, at least $n$ queries are necessary
because there are $2^n$ possible final answers for Arnaldo,
and each query has two possible responses.
\end{document}