Browse · MathNet
PrintArgentina_2017
Argentina 2017 counting and probability
Problem
Given is a table with rows and columns. Each cell in it contains a or a . The table has the following properties:
a. Every two rows are different.
b. Every row contains exactly entries equal to .
c. For every rows there is a column that intersects them at three entries equal to .
Find the greatest for which such a table exists.
a. Every two rows are different.
b. Every row contains exactly entries equal to .
c. For every rows there is a column that intersects them at three entries equal to .
Find the greatest for which such a table exists.
Solution
The answer is ; here and later on denotes a binomial coefficient.
Here is an example with . Form the (unordered) quadruples with elements from . To every such quadruple assign a row of length in which there are 's exactly at positions ; the remaining entries are 's. The obtained rows can be arranged to form a table, which satisfies conditions (a) – (c) by construction. (For condition (c) note that column contains only zeros.)
Let us show that for each table with the given properties. For each row consider the columns that intersect it at 's. We say that they form an admissible quadruple . It is uniquely determined by in view of condition (b). In addition different rows generate different admissible quadruples by condition (a). Hence there is a bijection between the rows and the admissible quadruples; in particular there are exactly admissible quadruples.
Let be an admissible quadruple. Consider all partitions of its complementary columns into quadruples and . Since columns out of can be chosen in ways, there are such partitions. Clearly the quadruples and are different for different partitions. Observe also that in each partition at least one of and is non-admissible. Indeed if and are admissible then no column intersects their respective rows at zeros, which contradicts condition (c). Hence the specified partitions generate at least non-admissible quadruples associated to the initial admissible quadruple . Because there are admissible quadruples, this argument yields a list of non-admissible quadruples. We are about to see that the repetitions in it are not too numerous.
Each non-admissible quadruple on the list occurs in it as many times as there are admissible quadruples that generate in the way explained above. Every such occupies columns among the complementary columns of , which gives at most possibilities for . Consequently every non-admissible quadruple on the list occurs at most times in it.
Given the length of the list and the maximum number of repetitions of an item, we find at least different non-admissible quadruples in . The total number of quadruples of columns is . Exactly of them are admissible and are non-admissible. Hence , which yields the desired .
Here is an example with . Form the (unordered) quadruples with elements from . To every such quadruple assign a row of length in which there are 's exactly at positions ; the remaining entries are 's. The obtained rows can be arranged to form a table, which satisfies conditions (a) – (c) by construction. (For condition (c) note that column contains only zeros.)
Let us show that for each table with the given properties. For each row consider the columns that intersect it at 's. We say that they form an admissible quadruple . It is uniquely determined by in view of condition (b). In addition different rows generate different admissible quadruples by condition (a). Hence there is a bijection between the rows and the admissible quadruples; in particular there are exactly admissible quadruples.
Let be an admissible quadruple. Consider all partitions of its complementary columns into quadruples and . Since columns out of can be chosen in ways, there are such partitions. Clearly the quadruples and are different for different partitions. Observe also that in each partition at least one of and is non-admissible. Indeed if and are admissible then no column intersects their respective rows at zeros, which contradicts condition (c). Hence the specified partitions generate at least non-admissible quadruples associated to the initial admissible quadruple . Because there are admissible quadruples, this argument yields a list of non-admissible quadruples. We are about to see that the repetitions in it are not too numerous.
Each non-admissible quadruple on the list occurs in it as many times as there are admissible quadruples that generate in the way explained above. Every such occupies columns among the complementary columns of , which gives at most possibilities for . Consequently every non-admissible quadruple on the list occurs at most times in it.
Given the length of the list and the maximum number of repetitions of an item, we find at least different non-admissible quadruples in . The total number of quadruples of columns is . Exactly of them are admissible and are non-admissible. Hence , which yields the desired .
Final answer
330
Techniques
Counting two waysColoring schemes, extremal arguments