Maths Olympiad Prep

Library / /69 of 97

Combinatorics Difficulty 8.2 Shortlist Find the answer

Find the largest positive integer mm which makes it possible to color several cells of a 70×7070\times 70 table red such that
- There are no two red cells satisfying: the two rows in which they are have the same number of red cells, while the two columns in which they are also have the same number of red cells;
- There are two rows with exactly mm red cells each.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To find the largest positive integer m m that allows coloring several cells of a 70×70 70 \times 70 table red such that:
1. There are no two red cells satisfying: the two rows in which they are have the same number of red cells, while the two columns in which they are also have the same number of red cells.
2. There are two rows with exactly m m red cells each.

We need to construct a configuration that meets these criteria.

The largest possible m m is 32 32 . This can be achieved by arranging the red cells in the topmost two rows, ensuring that the tail consists of segments with lengths 1,2,4,8,16,2 1, 2, 4, 8, 16, 2 .

Thus, the largest positive integer m m is:
32 \boxed{32}

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.