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 ${\mathbb F}_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: 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$. Query $(x_1 + \dots + x_{k-2}) + x_i$ for $i = k+1, \dots, n$. This gets $x_i$ for $i \ge n$. Moreover, at least $n$ queries are necessary because there are $2^n$ possible final answers for Arnaldo, and each query has two possible responses.

The answer is that it is not possible when $k$ is odd, and it takes $n$ turns when $k$ is even. When $k$ is odd, he cannot distinguish between everyone telling the truth and everyone lying (since in both cases, all queries will result in the answer being "odd"). There are $2^n$ possible configurations, so if he asks at most $n-1$ questions, by Pidgeonhole there exists some string of answers that corresponds to more than one possible configuration, hence he cannot determine the configuration, which shows the lower bound. When $k$ is even, we claim that he can simply query the same set $A$ each time and ask each person once. First, he asks each person in $A$ about $A$ and record the number of "even" responses and "odd" responses. These are the numbers of truth-tellers and liars in $A$ in some order. However, since $|A|$ is even, these two numbers are either both odd or both even. If they are both odd, then the people that said odd are truth-tellers and the people that said even are liars, and vice versa for the both even case. In both cases, he can determine the type of each person in $A$. Furthermore, he knows the true answer to his question at this point, so he can simply ask the same question to the remaining $n-k$ people to determine their type, hence done.

Hmm...this problem hurts my head For odd $k,$ the process is impossible. For even $k,$ the process requires $n$ queries. For odd $k,$ observe that a string of all $T$'s and all $F$'s cannot be distinguished, since every query results with the answer ``odd." For even $k,$ we first observe that $n$ operations are necessary: At each step, we at most determine if a set of $k$ people has an odd number of $T$'s or $F$'s, which halves our possibilities. Thus, to get from $2^n$ possibilities to $1$ unique string, we require at least $n$ queries. For upper bound, since $k$ is even, in any arbitrary set of $k$ people, the parity of the truthtellers and liars must be the same. Querying everyone in the set of $k$ people, we count number of ``evens" and ``odds" we obtain as answers. If the parity of the number of people who said ``odd" lines up with the number of ``odds" we counted, then these people are the truthtellers (similarly for even), and we know the rest are liars. Arnaldo can continue this process until there are $q<k$ people remaining, from which $q$ queries is sufficient to determine who are liars and truthtellers--by taking a set of $k$ people and querying the $q$ people of which we don't know who are truthtellers or liars.

For odd $k$, Arnaldo cannot distinguish between all truth-tellers or all liars, as he will receive an answer of ``odd" every time. For even $k$, I claim that at least $n$ queries are required. $n$ queries are sufficient because Arnaldo may fix a group of $k$ people and ask all $n$ people the same question for those $k$ people. Among the $k$ people themselves, suppose $a$ people reply ``odd" and $b$ people reply ``even". Then $a$ and $b$ must be the same parity, and whichever response matches that common parity comes from truth-tellers. Correspondingly Arnaldo may determine the truthfulness of all $n$ people. To see that $n-1$ questions cannot work, notice that upon asking $n$ questions, one to every member of the group, we receive $2^n$ possible combinations of responses. By the above discussion, every response corresponds to a unique distribution of truth-tellers and liars, and every distribution of truth-tellers and liars yields a unique set of responses. Hence, upon only asking $n-1$ questions, there will be at least $2$ possibilities for the distribution of liars.

Solved with mathematical717. Very interesting problem. We faced some unnecessary difficulty with the bound, but we were just clowning around. Let a positive integer $k$ be called $n$-detectable if it possible to determine which people speak the truth and which people always lie. Further, the type of a person is whether he speaks the truth or lies. (a) We claim that the answer is all even integers $k$ (and all $n\ge k$ for each $k$). First of all note that if $k$ is odd and all the $n$ people are of the same type, Arnaldo has no way of knowing which type it is since irrespective of which set of $k$ people and which person Arnaldo selects to question, the reply will always be 'even'. So he gains no new information, and will never know the liars and truth-tellers exactly. (b) We now show that all even integers $k$ are $n$-detectable for all $n\ge k$ with $n$ being the minimum number of moves required to determine which people speak the truth and which people lie. Our algorithm for detecting the liars and the truth-tellers exactly within $n$ moves is as follows. Consider a random set of $k$ people among the available $n$. Now, ask each and every person of this group the question concerning this group of $k$ people. Then, each person will answer 'even' or 'odd'. Arnaldo then separates them into two groups based on there response. It is easy to see that all the people in each group are of the same type, and two people from the two separate groups must be of different types. Now, after separating into groups, both the groups are of even size, or both groups are of odd size (since $k$ is even). Thus, Arnaldo knows the parity of the size of the set of truth-tellers among this set of $k$ people. Hence, he can exactly distinguish (based on which answer they provided) which group among the separated two consists of only truth-tellers. Now, if this group has atleast one truth-teller Arnaldo picks one of them as his buddy. If all of them are liars he picks one of them as his anti-buddy and negates what ever answer he provides to a question Arnaldo asks and considered him as his buddy. Using a buddy, Arnaldo can determine the type of all the other people as follows. Arnaldo selects the $k-1$ non-buddy people in his initial set of people. Then, he considers the set of people formed by adding each new person among the available $n$ in turn. Then, he asks from his buddy how many people speak the truth. Since Arnaldo knows the type of all but one person in this group, Arnaldo can then determine the type of the additional temporary member of the group. He repeats this process with each of the $n-k$ left over people, and finishes his task in exactly $n$ steps. To see why Arnaldo needs $n$ steps, note that if Arnaldo can finish in at most $n-1$ steps, Arnaldo has to uniquely distinguish a set of $2^n$ possible states (each person has two possible types) using $2^{n-1}$ answer sequences. Since $2^n > 2^{n-1}$ there exists atleast two possible states for some answer sequence for $n-1$ queries, making it impossible for Arnaldo to distinguish between the two. Thus, he will always need atleast $n$ queries to determine which people speak the truth and which people always lie, and we are done.