Maths Olympiad Prep

Library / /97 of 144

Combinatorics Difficulty 8.5 Shortlist Find the answer

Given n n countries with three representatives each, m m committees A(1),A(2),,A(m) A(1),A(2), \ldots, A(m) are called a cycle if

[i](i)[/i] each committee has n n members, one from each country;
[i](ii)[/i] no two committees have the same membership;
[i](iii)[/i] for i\equal1,2,,m i \equal{} 1, 2, \ldots,m, committee A(i) A(i) and committee A(i\plus1) A(i \plus{} 1) have no member in common, where A(m\plus1) A(m \plus{} 1) denotes A(1); A(1);
[i](iv)[/i] if 1<i\minusj<m\minus1, 1 < |i \minus{} j| < m \minus{} 1, then committees A(i) A(i) and A(j) A(j) have at least one member in common.

Is it possible to have a cycle of 1990 committees with 11 countries?

A number or a short expression. Spacing and $ signs are ignored.

Solution

To determine whether it is possible to have a cycle of 1990 committees with 11 countries, we need to carefully consider the constraints given in the problem:

1. Committee Composition: Each committee has 11 members, one from each country.
2. Unique Membership: No two committees have the same membership.
3. No Overlap Between Consecutive Committees: For any two consecutive committees A(i) A(i) and A(i+1) A(i+1) , there is no member in common, where A(m+1) A(m+1) is A(1) A(1) .
4. Overlap for Non-Consecutive Committees: For any two non-consecutive committees A(i) A(i) and A(j) A(j) such that 1<ij<m1 1 < |i - j| < m - 1 , there is at least one member in common.

### Strategy

To construct such a cycle, consider a suitable assignment of representatives to the committees that meets all the conditions. We explicitly demonstrate a feasible pattern:

1. Label Representatives: Assign 3 representatives to each of the 11 countries, giving us a total of 33 representatives.
2. Cycle Construction:
- Arrange these representatives to form committees of size 11 such that each committee draws exactly one representative from each country.

### Example Construction

Due to the symmetric and structured nature of the problem, we can consider this feasible construction approach:

- Sequential Shifts: Begin with an initial committee A(1) A(1) consisting of one representative from each country.
- Construct the subsequent committee A(i+1) A(i+1) by cyclically shifting the representative selections in a manner to ensure consecutive committees have no overlaps but all non-consecutive pairs share members, without repeating membership combinations.
- This shift pattern must ensure consistency with the rotation conditions specified, which can inherently satisfy both overlap and non-overlap criteria.

### Verification

Given 33 representatives, choose the representatives such that the condition of ij |i-j| assures some overlap but not in consecutive committees. This arrangement is possible because:

- The amount of maximum possible overlap is governed by committee design (shifts ensuring non-consecutive overlaps).
- The shift allows for 1990 unique committees, while alternating representative selections from a fixed base.

### Conclusion

By employing this structured rotational pattern, it is feasible to construct 1990 distinct committees from 33 representatives across 11 countries following the conditions provided.

Therefore, establishing the existence of such a cycle is indeed possible.

yes \boxed{\text{yes}}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.