Morteza Has $100$ sets. at each step Mahdi can choose two distinct sets of them and Morteza tells him the intersection and union of those two sets. Find the least steps that Mahdi can find all of the sets. Proposed by Morteza Saghafian
Problem
Source: Iranian TST Problem 1
Tags: combinatorics
02.04.2022 13:57
@2below Yes, you are right sorry for that.
02.04.2022 18:20
I will show that the answer is $100$. Let our sets be $S_1,S_2,...,S_{100}$. For construction ask the questions to $\{S_{3k+1},S_{3k+2}\},\{S_{3k+2},S_{3k+3}\},\{S_{3k+3},S_{3k+1}\}$ for $k=0,1,...,32$ and at last ask the question to $\{S_{99},S_{100}\}$. Now, I will show that we need at least $n$ questions for $n$ sets. Induct on $n$. $n=3$ is obvious.Let it be true until $n=k-1$. Assume Mahdi can find all sets with $k-1$ questions for $n=k$. So there is set $S_{i}$ that asked question just once and let only set it was asked is $\{S_i,S_{j}\}$. Since at the end Mahdi can find all sets, he should know set $S_{j}$ to find $S_{i}$. But obviously the question asked to $\{S_{i},S_{j}\}$ helps only finding set $S_i$. So he can find all sets, except $S_i$ using remaining questions. So he can find remaining $k-1$ sets using $k-2$ questions, but it's contradiction due to induction hypotise. So we are done.
02.04.2022 21:46
hakN wrote: Note that both the sets $S_1,S_2, \dots , S_{100}$ and $S_1',S_2', \dots, S_{100}'$ give the same answers to the questions. So $99$ moves is not enough to find the sets. Mahdi does the next step after seeing the results of the previous steps, so constructing two possible family of sets under a fixed graph does not suffice.
03.04.2022 00:57
NTstrucker wrote: hakN wrote: Note that both the sets $S_1,S_2, \dots , S_{100}$ and $S_1',S_2', \dots, S_{100}'$ give the same answers to the questions. So $99$ moves is not enough to find the sets. ...so constructing two possible family of sets under a fixed graph does not suffice. I did not read the original solution in #2, but I do think that it indeed suffices to show that any graph on $100$ vertices with at most $99$ edges can always be assigned $0,1,2$ (indeed only $0,1$) on the edges in a way that leaves us with at least two possibilities how to label the vertices with $0,1$ such that each edge has label the sum of its adjacent vertices. Here is why the graph claim is true: One component has fewer edges than vertices, hence is a tree and for a tree the claim is obvious. Here is why the graph claim suffices: Just let Morteza take sets such that each of the $2^{100}-1$ possible spaces in the Venn diagram of the $100$ sets is non-empty, e.g. all of them contain exactly one element. Now suppose that Mahdi has a strategy to find these given sets in $99$ steps and consider the corresponding graph. By the graph claim, we get an edge assignment which corresponds to more than one vertex assignment. But what this means is simply that Mahdi cannot distinguish between the two elements corresponding to these two vertex assignments, which is a contradiction! (The punchline of my argument is that since all the possible assignments can occur on the same occasion, it does not really help Mahdi to be able to choose his graph after seeing the results.)
17.08.2022 21:28
Firstly , we'll show that Mahdi needs at least $100$ questions. We assign these sets $A_1 , ... , A_{100}$ to vertexes of a graph $G$ , such that for each pair of the asked sets , there is an edge between their corresponding vertexes. Suppose that the graphs $G_1 , ... , G_k$ are connected components of $G$ with $v_1 , ... , v_k$ vertexes. so it's enough to show that each component $G_i$ , has at least $v_i$ edges , Which is equivalent with that none of these components be tree. Suppose that $G_i$ be a tree and let $v$ be one of it's vertexes. We construct two different group of sets whit each of it's adjacent corresponding vertexes like $X , Y$ , has same $X \cup Y$ and $X \cap Y$. And for that , it's enough that in one group , we add a random member $a$ to each set which it's corresponding vertex has an odd distance from $v$ and the same for the other group , obviously a contradiction. so $|E(G)| \ge 100$ and for an example for equality case , one can easily suppose that each component is a triangle , and one with another vertex and edge. So the answer is $100$.
26.08.2022 23:32
We will implicitly assume that all the sets are finite. We claim Mahdi can win in $100$ steps. To show this, we have the following lemma. Lemma: If we know all pairwise intersections and unions among three sets $A_1,A_2,A_3$, then we can find $A_1,A_2,A_3$. Proof: Fix an element $x$. Let $a_i=0$ if $x\not\in A_i$, and $a_i=1$ otherwise. For each pair $(i,j)$ with $i\ne j$, we learn that either $\{a_i,a_j\}=\{0\}$ (if both the union and intersection don't have $x$), or $\{a_i,a_j\}=\{1\}$ (if both the union and intersection do have $x$), or $\{a_i,a_j\}=\{0,1\}$ (if the union has $x$ but the intersection doesn't). Clearly, we will not learn that $\{a_i,a_j\}=\{0,1\}$ for all $(i,j)$, since that would mean all the $a_i$s are distinct, which can't happen. Therefore, WLOG suppose we learn $\{a_1,a_2\}=\{0\}$. Then, based on what we learn from $(1,3)$, we can determine $a_3$, so we now know all of $a_1,a_2,a_3$. Repeating this procedure for all $x\in A_1\cup A_2\cup A_3$ recovers $A_1,A_2,A_3$, as desired. $\blacksquare$ Let the sets be $A_1,\ldots,A_{100}$. Mahdi should ask for the pairs $(k,k+1)$, $(k+1,k+2)$, $(k,k+2)$ for all $k\equiv 1\pmod {3}$, and should further ask for $(1,100)$ (this is exactly $100$ pairs). By the lemma, Mahdi will learn the values of $A_i$ for all $1\le i\le 99$. Now, since Mahdi knows $A_1,A_1\cap A_{100},A_1\cup A_{100}$, he can learn $A_{100}=(A_1\cup A_{100})\setminus(A_1\setminus(A_1\cap A_{100}))$. This shows that Mahdi can learn all the sets in $100$ steps. Now, suppose that Mahdi only uses $99$ steps. We will provide a strategy for Morteza to give answers as the questions come in, as long as there are at least $2$ valid configurations at the end satisfying all of Morteza's responses. View the questions asked as a graph on the vertex set $V=[100]$. Suppose a new question comes in the form of an edge $e=(i,j)$. Let $C$ be the connected component containing $e$. If $C$ is a tree, then Morteza should reply that $A_i\cap A_j=\{\}$ and $A_i\cup A_j=\{0\}$. If $C$ contains a cycle (potentially created by adding $e$), then Morteza should just reveal the exact values of all the sets in $C$ according to some valid configuration (which exists since by induction our previous responses had at least $1$ valid configuration), and answer $e$ truthfully. There is always at least one valid configuration after placing $e$, since we can just two-color the trees with $\{\}$ and $\{0\}$. At the end of this process, we see that the number of valid configurations is at least $2^n$, where $n$ is the number of connected components that are trees. This is because all connected components that are not trees have their sets fully revealed, and for connected components that are trees, both two-colorings with $\{\}$ and $\{0\}$ are valid configurations. Thus, it suffices to show that every graph on $100$ vertices with $99$ edges has a connected component that is a tree. If this were not the case, then a connected component with $v$ vertices would necessarily have at least $v$ edges, so the total number of edges would be at least $100$, which is a contradiction. This completes the proof.
17.12.2022 22:15
The answer is 100. Draw a graph with 100 vertices such that each vertice represents a set. And draw an edge between two vertices if Mahdi chose them at the same time. First, we will show that Mahdi needs at least 100 steps to identify all sets.Take $1,2,p_1,p_2...p_{100}$ different numbers and suppose that set $A_i$ either ${(1,p_i)}$ or $(2,p_i)$(But which one is not clear until Morteza decides). Each set is in superstate at the beginning, being either $(1,p_i)$ or $(2,p_i)$(or both at the same time )(If a set is in superstate even morteza doesn't know what the set is) At first there is 100 connected components of the graph. $ Lemma:$ If a connected component has cycle every set in the component is known exactly by morteza (not in superstate) and otherwise every set in the component is in superstate. $a)$ If Mahdi chooses two sets in superstate without creating cycle, such as $A_i$ and $A_j$, Morteza says the intersection of those 2 sets is empty and the union is $(1,2,p_i,p_j)$. Lemma still holds. $b)$ If Mahdi asks a question that creates a cycle in a connected component that doesn't already contain cycle, before Morteza says anything to Mahdi, she brokes the superstate of each vertice in the component part of the graph which contains cycle and decides what those sets are by coloring them(without the last edge its a tree, thus bipartite) in red and blue such that no neighbors are the same color and decides that each red vertice contains ${1}$ and each blue vertice contains ${2}$. (When a set is not in superstate, it cannot be changed later by Morteza and she knows what the set is). Then Morteza says the intersection and union of the two sets truthfully to Mahdi. (Lemma still holds) $c)$ If Mahdi asks two sets such that one is in superstate and other one is not this means Mahdi chose and edge that connects two connected parts(one contains cycle and other one does not). First Morteza colors the component that doesn't have cycle(it is a tree, hence bipartite) in red and blue such that no neighbors are in the same color. Morteza then breaks the superstate of the colored vertices and decides each red set is $(1,p_i)$ and each blue set is $(2,p_i)$. Morteza then answers Mahdi since she knows what those two sets are(they are no longer in superstate) And note that the lemma still holds. $d)$ If Mahdi asks for two sets both not in superstate, Morteza already decided what those sets are, so she answers their intersection and union. When Mahdi decides he knows all the sets, let's look if any of the sets are in superstate. If there is such vertice this means the connected component that contains that vertice doesn't not contain a cycle and all the vertices in that component is in superstate. Morteza colors the component(a tree,bipartite) in red and blue again. And there is two possible different identification of the sets that Mahdi cannot identify the difference. All reds are $(1,p_i)$ and blues are $(2,p_i)$ or vice versa. So there is no vertice in superstate when mahdi says he identified all sets. But this means every connected component has a cycle, thus its edges are not less then its vertices. Mahdi asked at least 100 questions. To achieve 100 questions, Mahdi asks $(A,B)$,$(A,C)$,$(B,C)$ and identifies what $A,B,C$ are. Then he asks $(A,S_i)$ and identifies $S_i$. He asked total of $3+97 = 100$ questions.
15.09.2024 21:32
Mahdi needs at least $100$ inquiries to determine all the sets. We first provide a strategy for Mahdi. Consider three sets $A$, $B$, and $C$. Mahdi should ask Morteza about the pairs $(A,B)$, $(B,C)$, and $(C,A)$. Then, $$(A\cup B+A\cap B)+(A\cup C+A\cap C)-(B\cup C+B\cap C)=$$$$(A+B)+(A+C)-(B+C)=2A$$so we can determine the set $A$ (here we are working with multisets). Similarly we can determine the sets $B$ and $C$. Now we claim that if Mahdi has previously found a set $X$ then from asking about the pair $(X,Y)$ he can determine $Y$. As above, $$(X\cup Y+X\cap Y)-X=(X+Y)-X=Y$$Thus after the first three inquiries, we can determine the other $97$ sets, each with one inquiry. Thus Mahdi can determine all the sets in at most $100$ inquiries. We now show that Mahdi needs at least $100$ inquiries. Consider a graph $G(V,E)$ with vertices $v_1,v_2,\dots,v_{100}$ representing the sets and an edge between $v_i$ and $v_j$ if Mahdi ever inquired about the two sets. Let $G_1,G_2,\dots,G_n$ be connected sub graphs of $G$. We claim that each connected sub-graph $G_i$ needs at least $|G_i|$ edges, which is sufficient to finish the problem. Assume that $G_i$ only has $|G_i|-1$ edges. Then it is well known that $G_i$ must be a tree. Assume that regardless of the inquiry Morteza responded that the intersection was $\{\emptyset\}$ and their union was $\{x,y\}$. Consider a coloring of the vertices of the tree black and white such that the vertices at each end of an edge are of different colors. Then it is possible that each set colored black was $\{x\}$ and each set colored white was $\{y\}$ or vice versa. Since Mahdi can not distinguish between these scenarios, he must require an additional inquiry. Remark: The necessary and sufficient condition for $G$ to work is that ever connected component of $G$ must contain an odd cycle.