MathDB

2

Part of 2022 Francophone Mathematical Olympiad

Problems(2)

color k cells of nxn table, n tokens

Source: P2 Francophone Math Olympiad Junior 2022

5/23/2022
We consider an n×nn \times n table, with n≥1n\ge1. Aya wishes to color kk cells of this table so that that there is a unique way to place nn tokens on colored squares without two tokens are not in the same row or column. What is the maximum value of kk for which Aya's wish is achievable?
combinatoricscombinatorial geometryColoring
exist at least 18^n passwords of length n

Source: P2 Francophone Math Olympiad Senior 2022

5/23/2022
To connect to the OFM site, Alice must choose a password. The latter must be consisting of nn characters among the following 2727 characters: A,B,C,...,Y,Z,#A, B, C, . . ., Y , Z, \# We say that a password mm is redundant if we can color in red and blue a block of consecutive letters of mm in such a way that the word formed from the red letters is identical to the word formed from blue letters. For example, the password H#ZBZJBJZH\#ZBZJBJZ is redundant, because it contains the [color=#00f]ZB[color=#f00]Z[color=#00f]J[color=#f00]BJ block, where the word ZBJZBJ appears in both blue and red. At otherwise, the ABCACBABCACB password is not redundant. Show that, for any integer n≥1n \ge 1, there exist at least 18n18^n passwords of length nn, that is to say formed of nn characters each, which are not redundant.
combinatorics