11
$\begingroup$

Every evening, Peter meets with some of his many friends in the pub. One day he observes that over the last $n$ days:

  • every evening he has met with exactly three of his friends;
  • on no two of these evenings he has met with exactly the same three friends;
  • for any two of these evenings, there is exactly one friend that was present at both evenings;
  • none of his friends was present at all $n$ evenings.

Question: What's the largest value that $n$ can possibly take?

$\endgroup$
  • $\begingroup$ I assume the fourth point means "none of the friends (that he met in the pub over the last n days)." Otherwise it's a useless point (there could just be an additional friend who he has, but who avoids pubs) $\endgroup$ – Richard Rast Mar 10 '16 at 2:14
10
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.)

$\endgroup$
3
$\begingroup$

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$

$\endgroup$

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.