What is the maximum number of cells that can be marked on a chessboard so that from each of them, it is possible to move to any other marked cell in exactly two moves of a chess knight?

#
Let the knight be on a square of a certain color, then after two moves it will be on a square of the same color. Therefore, the marked squares should be of the same color (let's say black).

We will divide all the black squares of the board into eight four-square figures of two types (striped and gray), as shown in the image.

![](https://cdn.mathpix.com/cropped/2024_05_06_3da1f4345ad15e82abd2g-33.jpg?height=643&width=621&top_left_y=1342&top_left_x=707)

The distance between any two squares of each such figure is at least four knight moves. Therefore, each of these figures can contain no more than one marked square. Consequently, no more than eight squares can be marked. An example for eight marked squares is shown in the image.

![](https://cdn.mathpix.com/cropped/2024_05_06_3da1f4345ad15e82abd2g-33.jpg?height=572&width=575&top_left_y=2175&top_left_x=747)

## Answer

## [ Ordinary fractions $]$ Problem 116612 Topics: [ Case enumeration $\quad]$ [Mathematical logic (other) $]$

Author: Shapovalov A.V.

Vasya wrote a true statement:

"In this phrase, $1 / 3$ of all digits are the digit 3, and $1 / 2$ of all digits are the digit $1$."

And Kolya wrote the phrase:

"In this phrase, 1/... of all digits are the digit *, the fractions of digits * and * are the same and equal to 1/..., and the fraction of all other digits is $1 / \ldots$."

Insert three different digits in place of the asterisks, and three different numbers in place of the ellipses so that the statement is true.

## Solution

If any of the numbers replaced by ellipses is at least three digits, then there are at least 100 digits in this phrase, which is impossible (then one of the numbers consists of at least 30 characters, but then there are at least $10^{30}$ digits in total, and so on, it is clear that this cannot be). Therefore, all numbers are either single-digit or double-digit, and there are between 9 and 12 digits in total.

The digit "1" is not less than 4, and its fraction is not less than $4 / 12 = 1 / 3$, so the denominator of the first fraction is a single-digit number, meaning there are fewer than 12 digits.

All denominators are divisors of the number of digits, greater than one. Therefore, there cannot be 11 digits (the number 11 has no single-digit divisors other than one), nor 9 digits (four terms of the form $1 / 3$ and $1 / 9$ do not sum to 1). Therefore, there are 10 digits in total, and the fraction of the digit "1" is $1 / 2$. The other fractions can be $1 / 5$ and $1 / 10$. The sum of the fractions must be equal to 1: $1 / 2 + 1 / 5 + 1 / 5 + 1 / 10$.

In the denominators, the digits 0, 2, and 5 appear once each. Any two can be mentioned explicitly, then their fraction will be $1 / 5$, and the fraction of the only remaining digit will be $1 / 10$.

## Answer

"In this phrase, 1/2 of all digits are the digit 1, the fractions of digits 2 and 5 are the same and equal to 1/5, and the fraction of all other digits is $1 / 10$"

(or "...the fractions of digits 0 and 2 are the same..." or "...the fractions of digits 0 and 5 are the same...").