Parity and sets

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Parity and sets

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Brazil National Olympiad 2020 5 Level 3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

144 posts

#1 h Mar 18, 2021, 9:17 PM

Y by

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 lie. 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 to
true? ”, where $A$ is a subset of size $k$ of the set of $n$ people. The answer can only
be “ $even$ ” or “ $odd$ ”.
a) For which values of $n$ and $k$ is it possible to determine which people speak the truth and
which people always lie?
b) What is the minimum number of questions required to determine which people
speak the truth and which people always lie, when that number is finite?

This post has been edited 14 times. Last edited by betongblander, Jun 7, 2021, 8:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6882 posts

#3 h Jun 12, 2021, 2:31 AM • 3 Y

Y by HamstPan38825, Yuuhhuuuuuuu, PHSH

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4191 posts

#5 h Nov 30, 2023, 5:49 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1032 posts

#6 h Dec 31, 2023, 7:42 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8881 posts

#7 h Jan 6, 2024, 4:08 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

662 posts

cursed_tangent1434

#8 h Oct 20, 2024, 3:18 PM • 1 Y

Y by mathematical717

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

128 posts

#9 h Feb 23, 2025, 9:01 AM

Y by

I claim that the task is only possible when $k$ is even and in that case, the minimum number of questions is $n$ .

When $k$ is odd, to see that the desired task is impssible, notice that we cant differentiate between all people being truth tellers and all people being liars.

Now when $k$ is even, I give a strategy with $n$ questions which is clearly the minimum as there are $2^n$ possible asignements of truth tellers/liars to the $n$ people.

Firstly take $k$ players and use $k$ queries on each of them about the set of those $k$ players. Some work mod 2 can give that this reveals the identity of all $k$ of the players. Now for the rest of the $n-k$ players, to figure them out within $n-k$ queries, we find out the players one by one by asking them about the $k$ players whose status we already know which tells us the identity of that player.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

247 posts

#10 h Apr 22, 2025, 6:31 AM

Y by

Nice? Oh god pls make me better at combo. Let $f(n,k)$ denote our required (with $\infty$ meaning it ain't possible). Then $\boxed{f(n,k) = \begin{cases} \infty \text{ if $k$ is odd} \\ n \text{ if $k$ is even} \end{cases}}$ To see why $k$ is odd fails, see that atmost we can just make $2$ groups and we know one group are liars and one group are truth tellers (just ask everyone the same question on some set of $k$ people). But since $k$ is odd, the parity of wise truth seekers and devilish liars are always different so we can never know for sure, which is which.

For $k$ even, we atleast need $n$ questions as there are $2^n$ possiblities and each question just ``halves" the ones into possible sequences and not at all possible sequences atmost hence we need $\log_2(2^n)=n$ questions atleast.

To see why it is all we need, just fix some group of $k$ people and ask everyone the same question. Now the parity of wise truth seekers and devilish liars in the $k$ set of people is same, and based on what answers the $k$ people gave we know what that parity is and hence whichever people are saying that parity are the truth seekers and others are naughty liars and so done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a