13
$\begingroup$

In a small town, there exist a number of organizations of people. Each year, they send out a list of their members to everyone and this is the official way in which people know they are part of an organization. This usually goes well, however, this year things didn't go well.

The town's postal service is notoriously bad, so the letters get a bit mixed up. In particular, each person receives the membership lists of every organization of which they are not a part (and none of the lists of the organizations they are a part of). Worse, since membership in an organization changes year to year, no one is sure which organizations they belong to (or even if they belong to any) nor how many organizations there are. Everyone receives the erroneous mailing the same morning (and this is common knowledge) and quickly discover the nature of the error (i.e. that everyone received the mailing from all the organizations they were not a parto f).

The good news is that all the organizations hold a daily meeting at noon in the town center, visible to everyone. Moreover, everyone knows that there is at least one organization in the town. If anyone can deduce that they are definitely part of at least one organization, they will go to the town center at noon, and continue to do so daily. Anyone who is not sure will stay home to avoid embarrassment. If an entire organization's worth of people go to the town center, they will recognize this fact (by magic), and have a proper meeting. No one who stayed home can tell if a proper meeting has occurred, since meetings look just like a bunch of people standing around awkwardly.

Given that all the actors will deduce anything logically possible, will there eventually be a proper meeting? Will everyone who goes to the town center eventually be part of a proper meeting?

For mathematical formulation, see below

There is a set $S$ of sets of people. Each person knows about every $s\in S$ of which they are not a member. It is common knowledge that $S$ is not empty. Each day, they all simultaneously either declare that they can prove that they are in some $s\in S$ or that they cannot prove this. An organization holds a proper meeting when every member can prove they are a member of some set.

$\endgroup$
  • $\begingroup$ Are there people who do not belong to any organisation? $\endgroup$ – ghosts_in_the_code Oct 17 '15 at 3:37
  • $\begingroup$ @ghosts_in_the_code That is possible. The solution doesn't particularly depend on whether they exist, though - they're pretty much inert, since they're never going to prove that they're part of an organization (since they're not). What's important is that no one a priori knows that they do belong to an organization. $\endgroup$ – Milo Brandt Oct 17 '15 at 3:40
  • $\begingroup$ If an actor gets mail from X, they know they don't belong to X. If they don't get mail from Y, they may not even know Y exists. In the worst case, all actors are members of the same set of organizations, so even if they share with each other the knowledge of what mail they've collectively / individually received, they still have no information on any organization they are part of. In practice, they could look around to see what organizations exist, but the question suggests this information is not available (paragraph 2). How does an actor know that an organization they belong to exists? $\endgroup$ – Lawrence Oct 17 '15 at 8:44
  • 1
    $\begingroup$ @Lawrence The fact that everyone knows that there is at least one organization is critical: If you receive no mail, then you may immediately deduce that there is an organization containing you. The organizations can't be identified by members, but it is possible for people to determine that they are part of some organization without this knowledge. $\endgroup$ – Milo Brandt Oct 17 '15 at 15:01
  • $\begingroup$ if you stay home, do you even know who went to town or stayed home? Do you learn anything each day that goes by? $\endgroup$ – Kate Gregory Oct 17 '15 at 22:39
2
+50
$\begingroup$

I claim the answers to both questions are yes.

The main lemma needed is this: suppose $X$ is any collection of people such that every organization contains at least one person from $X$. Then there is some $n\ge 1$ such that at least $n$ people from $X$ go to the town center at noon on day $n$ (note that this $n$ must be less than or equal to the size of $X$).

Call a set $X$ of people sufficient if every organization contains at least one person from $X$.

To prove the lemma, induct on the size $k$ of the sufficient set $X$. Suppose that all the townspeople know that the lemma is true for sufficient sets of size strictly less than $k$, that $X$ is a sufficient set of $k$ people, and that for every $1 \le n < k$ there have been strictly less than $n$ people from the set $X$ who showed up at the town center on day $n$. Then on the morning of day $k$, by the known cases of the lemma everyone in town will know that every proper subset of $X$ is insufficient. Suppose Alice is in the set $X$. Since $X$ is sufficient, every organization not containing Alice contains someone else from the set $X$, so Alice knows that if she were not a member of any organization then the collection of people in $X$ other than Alice would be sufficient - which she knows is impossible by the morning of day $k$! Thus Alice can prove that she is a member of some organization by day $k$. Since all of the other members of $X$ can reason similarly, on day $k$ all $k$ members of $X$ will show up in the town center (remember, this argument only applies if there was no $1 \le n < k$ such that at least $n$ people from $X$ showed up on day $n$).

To answer the first question: let $X$ be the set of people who never show up to the town center. By the lemma, $X$ must be insufficient - so there is some organization which has no members in $X$, and that organization must therefore eventually have a proper meeting.

For the second question, we will need a secondary lemma: if Alice shows up for the first time on day $k$, then Alice is contained in some sufficient set $X$ of $k$ people such that for every $1 \le n < k$, strictly less than $n$ people showed up in the town center on day $n$.

Call a set $Y$ of people apparently sufficient (to Alice) if every organization which does not contain Alice contains at least one person from $Y$.

We will prove the secondary lemma by induction on the day $k$ when Alice first shows up in the town center. If $k = 1$, then it is obvious: the only way that Alice can show up at the town center on the first day is if Alice all by herself is sufficient. Now assume that $k$ is at least $2$, that Alice can prove the secondary lemma for strictly smaller values of $k$, and that Alice shows up for the first time on day $k$. Alice knows that if she were not a member of any organizations, then apparently sufficient sets and sufficient sets would be the same - and so she can use smaller cases of the secondary lemma to predict exactly what would happen on days $1$ to $k-1$ under the assumption that she is not a member of any organization. The only way she can possibly prove that she is a member of some organization on day $k$ is if some other person - say Bob - deviates from this prediction before day $k$. If Bob deviated before day $k-1$, then Alice would have gone to the town center before day $k$, so in fact Bob must have deviated from the prediction on day $k-1$. Since every sufficient set appears to be sufficient to Alice, the only way Bob can deviate from her prediction is if he fails to go to the town center when Alice expects him to. Thus there must be some apparently sufficient set $Y$ containing Bob of size $k-1$, such that for every $1 \le n < k-1$, strictly less than $n$ people from $Y$ show up at the town center on day $n$. Letting $X$ be the set obtained by adding Alice to $Y$, we see that since $X$ has size $k$, that $X$ is sufficient, and that on day $k-1$ at most $k-2$ people from $X$ showed up at the town center (since neither Alice nor Bob showed up on day $k-1$). Thus, for every $1 \le n < k$, strictly less than $n$ people from $X$ showed up at the town center on day $n$.

To answer the second question: Suppose that Alice goes to the town center for the first time on day $k$, let $X$ be a sufficient set containing Alice of size $k$ such that for every $1 \le n < k$ strictly less than $n$ people showed up in the town center on day $n$. Let $Y$ be the set obtained by deleting Alice from $X$ (so $Y$ appears sufficient to Alice), and let $Z$ be the set of people who never show up at the town center. Then we can apply the main lemma to see that $Y \cup Z$ must be insufficient, so some organization must have no member in common with $Y\cup Z$. Since $Y$ is apparently sufficient, that organization must have Alice as a member, and by the definition of $Z$ that organization must eventually have a proper meeting.

Whew, that was long.

$\endgroup$
4
$\begingroup$

There will eventually be a proper meeting, but not necessarily of every organization.

Start with imagining Person A, who does not get any letters. This tells Person A "there is no organization of which I am not a member." Person A goes to the town square on Day 1 and from then on. If there is only one organization, or every person is in every organization, this happens for everyone and the process ends on Day 1.

Now imagine Person B gets 1 letter. These means there are n+1 organizations, where n is 0 or more, and Person B is in n of them. Person B can't be sure that n isn't 0, so stays home.

The next day, Person B can compare the names in their letter to the people who went to town. If there are people named in the letter who didn't go to town, Person B knows that those people must have received letters. This means there are at least two organizations, and therefore B is in one. B will now start going to town.

If all the people in B's letter went to town, then B will have to see if anyone not in the letter went to town. This too will indicate the existence of another letter, and therefore another organization, and send B to town from now on.

However if the set of people who went to town exactly matches B's letter, there will be nothing to indicate that there is a second organization and B will stay home on day 2.

From then on, if anyone else suddenly starts going to town, B will realize there is another organization and start going to town.

Now consider Person C who got two letters. This person only exists if there are two or more organizations. This person believes there are n+2 organizations and C is in n of them, but n might be 0. Person C monitors the people who go to town and compares them to the people on the two letters. Anyone named in a letter who didn't go to town on Day 1 must have got at least one letter. If they then go to town on Day 2, it's because their letter names someone who didn't go to town yet. It might be C, but C can't be sure unless everyone else has gone to town. However as with A, if anyone goes to town who isn't in B's letters, there is a third organization that person is in, and C must be in it too. This will send C to town from then on.

As well, if someone is in both of C's letters, but didn't go to town on Day 1, they must have received a third letter. This will send C to town on Day 2.

So a person will go to town when they know there is an organization they didn't get a letter for. This happens:

  • right away if you didn't get a letter
  • whenever someone goes to town who is not named in any of your letters
  • whenever someone named in all of your letters doesn't go to town

This is not guaranteed to bring everyone. For example consider Org 1 with ABCD and Org 2 with ABCDE. A, B, C, and D don't get a letter and go right away. E gets only the letter for Org 1, looks it over and says "yup, that makes sense" and doesn't go to town. However a proper meeting does get hold for Org 1.

Applying this to the example from a comment by the OP: consider organizations AC, AD, AE, ACDE, BC, BD, BE, BCDE.

  • A gets letters naming BC, BD, BE, BCDE
  • B gets letters naming AC, AD, AE, ACDE
  • C gets letters naming AD, AE, BD, BE
  • D gets letters naming AC, AE, BC, BE
  • E gets letters naming AC, AD, BC, BD

On Day 1 nobody goes to town.

On Day 2, A sees that B is named in all the A letters, but didn't go to town. Therefore B must have another letter naming A. From now on, A goes to town. B draws the same conclusions about A. C, D, and E can't be sure yet because nobody is named in all their letters. It's possible they aren't in any organizations.

On Day 3, C sees that A and B went to town. But D and E didn't. This must mean that D and E have at least one letter each. Yet D and E are in each of the letters C holds. Therefore, there's another organization, and C must be in it. C goes to town from then on. By the same logic so do D and E.

So for this example, all the organizations end up having proper meetings.

For the next example, A B C AB AC BC:

  • A gets letters naming B, C, and BC
  • B gets letters naming A, C, and AC
  • C gets letters naming A, B, and AB

On Day 1 nobody goes to town because they got letters.

On Day 2, A thinks "B should have gone to town because B is in an organization. So B must have got a letter. Perhaps it was this same C letter that I got." So A expects that B was expecting C to go to town on Day 1. Since C didn't go, A expects B to decide to go on Day 2, but A stays home since there's no reason to conclude A is in a group. The others follow the equivalent reasoning for their letters and stay home.

On Day 3, A thinks "B should totally have gone to town yesterday if the only letter B got was this C letter I have here. So in addition to this letter naming C that I have, B must have some other letter as well, naming me (or possibly me and C). I had better go to town." And A goes to town. The same holds for the others, who go to town on Day 3 as well.

So the OP is right that this adds another circumstance under which you go town.

  • Whenever someone who is not named in all your letters (they've been dealt with in an earlier step) doesn't go to town on a day when they should have, based on the letters you have seen in which the person isn't named.
$\endgroup$
  • $\begingroup$ It is intended that no one knows whether "the process has ended" (i.e. whether any proper meetings have taken place). I edited the question to clarify this point. The content of the lists is important to the intended answer (but they are, of course, not allowed to share this knowledge) - knowing the number of letters does not suffice. $\endgroup$ – Milo Brandt Oct 17 '15 at 18:46
  • $\begingroup$ Actually, this is wrong even with the presumption that they can tell whether the process has ended; if there were 4 people named A, B, C, and D and the organizations were AC, AD, AE, ACDE, BC, BD, BE, BCDE, then everyone receives $4$ letters. However, A and B may deduce on day two that they are in an organization, which is much faster than the $5$ days that this answer predicts. (And, C, D, and E will discover that they're in an organization on day $3$, which is again faster). $\endgroup$ – Milo Brandt Oct 17 '15 at 19:11
  • $\begingroup$ I know it can be faster if there is overlap, in fact I said so. I just know it won't take more than n days. Still working on how to use the names to figure out if the process has ended. $\endgroup$ – Kate Gregory Oct 17 '15 at 19:13
  • $\begingroup$ I think you're going down the right path, but consider a case like the organizations being A B C AB AC BC (with three people). It doesn't seem like anything you've written addresses this. The sentence "whenever someone named in all of your letters doesn't go to town" is a good first step. (The sentence "whenever someone goes to town who is not named in any of your letters" is a red herring - it turns out that this provably never happens) $\endgroup$ – Milo Brandt Oct 20 '15 at 2:29
  • $\begingroup$ added a fourth sending rule @MiloBrandt $\endgroup$ – Kate Gregory Oct 23 '15 at 20:25
2
$\begingroup$

A person will go to the town center if they can determine that they must be a member of some organization. If they can determine that there is at least one letter they did not receive, then they must be a member of some organization.

If they are not a member of any organization, then they received the membership of every organization. This allows them to do a simple proof by contradiction. They start off by assuming that they are not a member of any organization (and therefore have perfect knowledge of the situation), and then wait until something unexpected happens.

The simplest case is that a person receives no letters. Assuming that they are not a member of any organization implies there are no organizations, which they know to be false. Therefore, they must be a member of at least one organization.


Consider how this plays out with organizations consisting only of single members: A, B, and C

A gets letters about B and C, B gets letters about A and C, and C gets letters about A and B.

On day 1, as everyone received letters, nobody goes to the town center.

On day 2, A assumes that there are only two organizations — B and C. B received a letter about C, and C received a letter about B. Thus, neither of them should have gone to the town center. As neither of them did, A has no reason to believe that there are any other organizations. B and C follow similar reasonings.

On day 3, A assumes that there are only two organizations — B and C. On day 2, B would have reasoned as follows: "Suppose there is only one organization, with C as its only member. Then C should have gone to the town center on day 1. However, C did not, so I must be a member of some group. So I will go to the town center today." However, B did not go to the town center on day 2, so there must be an organization that A does not know about that A is a member of. So A will go to the town center. By symmetric reasoning, B and C will also go to the town center.


We know that it is not the case that everyone will always be able to determine that they are a member of some organization. Consider the case of organizations A, AB, ABC, and ABCD.

On day 1, A, having received no letters, goes to the town center.

Every day after that, A goes to the town center while B, C, and D all stay home. B thinks there's only one organization A, and only A going to the town center confirms that. C knows there's also an organization AB, but expects B to stay at home because B doesn't know about that one. D knows there's also an organization ABC, but knows that C and B are unaware of its existence. There will never be an event that disrupts anyone's expectations, so this is a stable situation.


There are two questions we still need to answer — will there always be at least one proper meeting, and will everyone who goes eventually be in a proper meeting?

First, let's establish a base condition - there will always be at least one person who goes to the town center. I'll use a group of A, B, C, and D to help explain my proof.

If anyone does not receive a letter, then they will go the first day. This is the only way in which someone will go on the first day.

Now assume that everyone received at least one letter (and so nobody went on the first day). Then on the second day A, assuming that she is not a part of any group and therefore knows the membership of every group, will consider every other person. If any of B, C, and D is a member of all the groups, then that person should not have received any letters and gone on the first day. But nobody went the first day, so A must not have perfect information, and therefore must be a member of some group.

If nobody goes on the second day, then A will go one level deeper in her reasoning. She first considers B — he knows about all the groups for which he is not a member. If C or D is a member of all of those groups, then B would have expected them to go on the first day. When he observed that they did not, he should have gone on the second day. Because he did not go on the second day, A knows that there must be some group that she does not know about and therefore is a member of. She follows the same reasoning for C and D.

If nobody goes on the third day, A will reach the deepest level of reasoning necessary for four people. She will again consider B's reasoning. Assuming that she knows about all the groups that exist, B knows only about groups that consist of C and/or D. So he, on the third day, would have considered C's reasoning for the second day. He would have assumed that he knew about all the groups that exist, and since he only knows about groups the have only C and D in them, C must have only known about a group of which D is the only member. So C, on the second day, would have thought that only D was a member of a group, and having not witnessed D go on the first day, should have gone on the second day. Thus, B, having not witnessed C go on the second day, should have gone on the third day. Thus A, if she does not see B go on the third day, will go on the fourth day.

In more formal terms, on day $k+1$ person $p_0\in P$ will determine if $\exists p_{i1}\in (P-\{p_0\}) \exists p_{i2}\in (P-\{p_0,p_{i1}\})...\exists p_{ik}\in (P-\{p_0,...,p_{i(k-1)}\})\forall g\in G: \{p_{i1},...,p_{ik}\}\cap g \ne \emptyset$

where $G$ is the set of all groups that $p_0$ knows about. If this condition is met, then there are no groups that do not contain at least one of the people considered. This means that on day $k+1$, $p_0$ expected each person in the chain $p_{ij}$ to expect the next person in the chain to have left on the previous day (with the last person expected to leave on the first day). Because the expectation was not met, $p_0$ will go to the town center on day $k+1$.


Everyone who goes will eventually be a part of a proper meeting:

Let $p_0$ be a person who will go to the town center. If $p_0$ is the sole member of an organization, then a proper meeting can be held immediately. Otherwise, $\exists g_0,p_1\mid p_0,p_1\in g_0$. Because $p_0$ and $p_1$ are both members of that organization, neither received a letter about it. Suppose there are no organizations of which $p_0$ is a member but $p_1$ is not. Then, when $p_0$ goes to the town center, $p_1$ will know there is at least one organization that they did not receive a letter for, and must therefore be a member of.

Otherwise $\exists g_1\mid p_0\in g_1\land p_1\notin g_1$. By our above reasoning, we know that anyone who only belongs to organizations $p_0$ does will go to the town center one day after $p_0$ at the latest.

For each person $p_i\in g_1$ who is a member of $g_i\mid p_0\notin g_i$, $p_1$ can follow the same chain of logic we used to prove that someone will eventually go. I'm having trouble writing out the formal logic for it, but here's the basic idea — $p_1$ will expect $p_i$ to expect etc. In the end it boils down to two cases - either an entire organization goes, or $p_1$ will go, and because $p_1$ was an arbitrary member of $g_0$ that means everyone in $g_0$ will go.

$\endgroup$
1
$\begingroup$

Thanks Milo Brandt's for a nice puzzle. The answer to his questions are "yes" and "yes".

Even more, I state that:
S1. At least one person will go to town, on day N or earlier.
S2. Everyone who goes to the town will be part of a proper meeting eventually, on day (N+1) or earlier.

Here and later, N is number of organisations with at least 1 member. org - shortcut organisation.

Proof:

I suppose all organisations are not empty and all people are male :), and each man is in some organisation. Obviously, this doesn't change result.

First of all, let's note, that the condition for a person who got L letters to stay home is that he can assume that there is exactly L orgs and find no contradictions with it.

Let's use math. induction to prove that S1 and S2 is true for any N.

a) Base. If there is only 1 org, then all people got 0 letters and go to town on the first day, and have a proper meeting immediately.

b) Let's suppose that S1 and S2 are true for any town with k-1 orgs and prove this for k orgs.

So, there is k orgs. We consider a random guy X. He got at most k-1 letters and assumes that there is no other ogrs. Thereby, he sees the town as a town with k-1 orgs and expects at least someone to show up on the (k-1)-th day at least. S1 is true if everything goes as he expected. If this is not the case, then X understands that he don't have a full picture and goes to the town on k-th day. That proves that S1 is always true for k orgs.

Now, let's consider a random guy Y, who is already in town and still doesn't have a proper meeting.
First of all, all guys, who belong to all orgs of Y, will go to town on the next day. Indeed, Y is not in their letters, but they see him in town...
If at least one Y's org has no members left, Y will get his proper meeting (next day, which is (k+1)-th day) (making S2 true).
If this is not the case, let's consider a guy Z - a member of an arbitrary Y's org, who stays at home.
Z sees the town as a town with k-1 orgs, and Y is a member of some of them. So Z expects Y to get proper meeting on day k at least. And either Y got it on day k, or Z goes to town on day k+1 and Y has proper meeting(-s) then (because Z was chosen arbitrary and all other co-members of Y and Z will do the same). That means S2 is true for all cases with k orgs in town, what had to be proven.

Thereby, according to math induction principle the initial statements are true.

$\endgroup$
  • $\begingroup$ Why do you assume each man is in some organization? How does it "obviously" not change the result? $\endgroup$ – Rob Watts Oct 23 '15 at 20:22
  • $\begingroup$ Also, the last part of your proof doesn't work. "Z expects Y to get proper meeting on day k at least" - in the question it says "No one who stayed home can tell if a proper meeting has occurred". $\endgroup$ – Rob Watts Oct 23 '15 at 20:23
  • $\begingroup$ @RobWatts, OP has already answered to this question: klm123 One may as well assume so; it doesn't really change the problem at all as that case is trivial anyways - if there's an empty organization, no one ever goes to town, but there's a proper meeting anyways since the whole empty organization is at town. – Milo Brandt Oct 20 at 2:22. I may add to this that even if such a meeting (with 0 ppl) we don't call a proper meeting we can ignore 0 member orgs, since all people knows about them and know that there is 0 members, and those 0 members can't really do anything and give ppl information:) $\endgroup$ – klm123 Oct 23 '15 at 23:00
  • $\begingroup$ @RobWatts, I think you interpret this statement of OP incorrectly. No one will see "a poster" like PROPER MEETING IS NOW, but each person sees who came to the town centre and if he doesn't belong to the organisation he has a full list of org members, so he can compare, think and easily conclude whether the org has proper meeting or not. $\endgroup$ – klm123 Oct 23 '15 at 23:03
1
$\begingroup$

This is how I see it. The main goal for everyone is to determine whether the lists they receive are from all organisations there are.

The trivial case is the case when one does not receive a list. This means that that person is in an organisation so he will go to town.

Now everyone does this: For every person on your lists imagine what lists that person would have if the lists you have are from all organisations.

Now there are 2 cases:

  1. There is a person that has no lists
  2. Every person has at least one list

Case 1

You expect that person to appear.
If that person appears it means you have the lists of all organizations and you are in none.
If that person doesn't appear it means he has a list you don't have and you are in it so you go to town the next day.

Case 2

You wait a day and now for each person in your list imagine you were that person and apply the first strategy again. Keep doing this every day until you get a Case 1. This is guaranteed to happen because the number of lists for each person shrinks every time.

This means the answer to both questions is yes.

You could wonder: what would happen if a person goes to town while you didn't predict it? If it were to happen it means you are in a organisation. But I strongly believe that this is impossible to happen.

So let's work out a case: Say person A gets BCD BC CD BD B C D

If A had all lists he would expect that everyone had the following lists:
B: CD C D
C: BD B D
D: BC B C

We now have a case 2
So first we pretend we are B so we have CD C D. He then expects for the remaining persons to have this:
C: E
D: C
Now for C:
B: E
D: B
Now for D:
B: C
C: B

Again a Case 2. If we now apply it again we are in a state where everyone has no lists so we have a Case 1. so A expects that B, C and D all go to town. If they are there then A is not in an organisation, if they are not then A is in a organisaion.

I believe this strategy is foolproof for any situation

$\endgroup$
  • $\begingroup$ "You expect that person to appear. If that person appears it means you have the lists of all organizations and you are in none." Why? This person can be in all organisations even though you don't get their letters. $\endgroup$ – klm123 Oct 26 '15 at 21:38
  • $\begingroup$ " Keep doing this every day until you get a Case 1. This is guaranteed to happen because the number of lists for each person shrinks every time." - again - why? $\endgroup$ – klm123 Oct 26 '15 at 21:41
  • $\begingroup$ @klm123 As for your first question, I think this is mostly intuition from my part, I don't have an exact proof I think. But I loved to be proven wrong. If you would give me a list of organisations for which this doesn't hold please provide it. As for your second question, this is logical due to the nature of my algorithm. You always split one longer list in multiple smaller lists because you split it among people on that list that obviously don't have the lists that you had where they were on so it will always be smaller. $\endgroup$ – Ivo Beckers Oct 26 '15 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.