Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
Every evening, Peter meets with some of his many friends in the pub. One day he observes that over the last $n$ days:
Question: What's the largest value that $n$ can possibly take?
The answer is
7
With one possible combination being
ABC ADE BDF AFG BEG CDG CEF
Proof
Each friend cannot appear on more than 3 days. There needs to be a day without this friend, but still share another friend from each day. Since there only 3 friends each day, 3 is the maximum. Each new day we have to include a friend from each of the previous days. Since we can only reuse a person which has occurred less than 3 times, each of the persons on the 7th day can match up with 2 of the previous days. we cannot do this for day 8.
Kruga's answer with an alternate proof.
7 is indeed the maximum
I use a constructive proof. Let the friends be represented by letters as in Kruga's answer. The letters do not imply any sort of order. Therefore, we have:
Day 1: ABC.
Consider the second day.
One friend from the first day must be present. The letters are arbitrary, so we pick A. Also, since all of the conditions are reflexive and commutative, the numbering of the days is arbitrary. By condition 3 (we note that condition 2 is a special case of condition 3) no other friend from the first day can be present; therefore, we have two new friends D and E.
Day 2: ADE
By the 4th condition, there must exist a day when A is not present. I will call this Day 3, but, again, the number is arbitrary. This day must have exactly 1 friend from Day 1. We can pick B since the names are arbitrary. There must also be 1 friend from Day 2, but not A. We can pick D. There cannot be a second friend from either day so the third friend must be one never seen before. Call this friend F. We have:
Day 3: BDF
Now we note that it is only possible to construct one more day with either A or B. Consider A. A cannot be paired with B or C due to Day 1 or with D or E due to Day 2 yet there must be one common friend with Day 3. The only possibility is F. In other words any new day containing A must contain F. By the third condition, there can be only one such day or A and F would be both be present on two occasions. The same logic applies to B.
By condition 3, any day outside of the three we have listed must share exactly one friend with Day 1. We can generate a maximum of one more day containing A, a maximum of one more day containing B. If we want to generate more than two more days, the only remaining possibility is to use C. Call this new day Day 4. Day 4 must Contain C. It must have a friend in common with Day 2, but not A or Day 4 and Day 1 would have both C and A in common. Whichever you pick, the set of Day 1, Day 2 and Day 4 is isometric with Day 1, Day 2 and Day 3. Therefore, by the same reasoning only one more day can be generated including C after Day 4. Thus there is a maximum of 4 + 1 + 1 +1 = 7 combinations. Kruga has given one such combination. QED.
Here's a “seating arrangement”
7 friends A,B,C,G,P,R,Y meet on $n\!$ = 7 evenings
Vertices ($\bullet$) = evenings.
Large labeled triangles = friends.
Small labeled triangles = outward-pointing corners of large triangles,
where they meet other triangles.
(Center vertex = first evening, where/when
the orange triangles A,B,C are the first three friends to meet.)
•
3 friends/triangles meet on/at each evening/vertex.
•
Each pair of evenings/vertices are connected by exactly one
friend / triangle-side.
Reasoning:
Left: No friend F can be present on 4 or more evenings because that would require at least 4 other friends to be present on some other single evening. (Some evening E is required where F is not present; E is required to share a friend with each of F's 4 evenings, but all other friends on F's 4 evenings would be different from each other or else they'd be with F on two evenings.)
Center: At most $n\!$ = 7 evenings remain in play. (Each of the first 3 friends can be present on at most 2 other evenings.) The light blue triangles show possible other friends, as long as their extra corners can be connected back to the 6 perimeter vertices.
Right: The solution unfolded with multiple images of each friend/triangle so that all evenings/vertices can be seen. (The nights/vertices are equivalent to a 7-colored torus.)
No-go:
If at least 4 groups with the same friend can be found, there'll be no legit group without him, so there can be 3 such groups at most rather than 4.
Solution:
Let the friends in the first group be $a, b$ and $c$. One of them (not always the same) must be found in all groups, but there must be only one of them in every group other than the first. If 3 of them have each of the three, $b$ and $c$ will be counted twice each, hence we can reach 9-2=7.
Example:
$a-b-c / a-d-e / a-f-g / b-d-f / b-e-g / c-d-g / c-e-f$
