Maths Olympiad Prep

Track / Stage 6 / 25 of 400 #1025 of 1964

Problem 1025

National Olympiad, first round
Combinatorics Difficulty 6.0 Prove it Italian Mathematical Olympiad · Italy

On a 75×7575 \times 75 chessboard the rows and columns are numbered from 1 to 75. Chiara wants to place a checker on all and only the squares that have one coordinate even and the other a multiple of 3. How many checkers will she place in total on the chessboard?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Solution:

The answer is 1706. Indeed, the squares (x,y)(x, y) on which there is a checker can be divided into two groups:

a. xx a multiple of 2 and yy a multiple of 3;
b. xx a multiple of 3 and yy a multiple of 2.

Since there are on the chessboard [752]\left[\frac{75}{2}\right] columns with abscissa a multiple of 2 and [753]\left[\frac{75}{3}\right] rows with ordinate a multiple of 3, the number of squares of the first type is
[752][753]=3725=925 \left[\frac{75}{2}\right] \cdot \left[\frac{75}{3}\right] = 37 \cdot 25 = 925
(here [x][x] denotes the integer part of xx, that is the greatest integer less than or equal to xx).

By symmetry (since the chessboard is square, it suffices to rotate it by 9090^\circ) the number of squares of the second type is the same. In this way, however, we have counted twice the squares that belong to both groups, for example (6,6)(6,6). By the way the two groups are defined, these squares are all and only those in which the abscissa and the ordinate are both multiples of 6, whose number is
[756][756]=1212=144 \left[\frac{75}{6}\right] \cdot \left[\frac{75}{6}\right] = 12 \cdot 12 = 144
We must therefore subtract from the total the number of these squares that have been counted twice. To sum up, we have

Squares with a checker == Squares in the first group + Squares in the second group - Squares in both groups ==
=925+925144=1706 = 925 + 925 - 144 = 1706

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty, ordering) added by this project.