Problem C. 1660. (March 2021)

C. 1660. The positive integers \(\displaystyle 1\) to \(\displaystyle 61^2\) are written in the fields of a \(\displaystyle 61\times61\) chessboard, starting from the top left corner and proceeding along each row in succession. Then some changes are made as follows. In the first move, the sign of each number is changed to negative. In the second move, the signs of all even numbers are changed. In the third move, the sign of every multiple of 3 is changed, and so on, while the moves are meaningful. When all this is completed, how many \(\displaystyle 1\times2\) rectangles will there be on the chessboard in which the sum of the numbers is negative?

(5 pont)

Deadline expired on April 12, 2021.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Először határozzuk meg a számok (végső) előjelét. Minden szám előjele annyiszor változik, ahány pozitív osztója van. Mivel pontosan a négyzetszámoknak van páratlan sok osztója, ezért a négyzetszámok előjele negatív lesz, a többi számé pedig pozitív.

Egy \(\displaystyle 1\times 2\)-es téglalapban pontosan akkor negatív az összeg, ha a nagyobb abszolút értékű szám negatív, vagyis abszolút értéke négyzetszám. (Akár az is előfordulhat, hogy a kisebb abszolút értékű is negatív, de ez nem befolyásolja a továbbiakat.)

Az egyszerűség kedvéért a mezőkre hivatkozzunk azzal a (pozitív) számmal, ami eredetileg oda lett írva.

Először vizsgáljuk meg, hány olyan \(\displaystyle 1\times 2\)-es téglalap van, aminél a két négyzet egy sorban van, továbbá jobb oldali négyzete (ami a nagyobb értéket fedi) négyzetszám. Ehhez azt kell meghatároznunk, hogy az \(\displaystyle 1^2,2^2,\dots,61^2\) számok közül hány nem az első oszlopban van. Pontosan azok vannak az első oszlopban, melyek 61-es maradéka 1. A \(\displaystyle k^2\) szám 61-es maradéka pedig pontosan akkor 1, ha \(\displaystyle k^2-1=(k+1)(k-1)\) osztható 61-gyel. Mivel a 61 prímszám, ezért ez csak akkor lehet, ha \(\displaystyle 61\mid k+1\) vagy \(\displaystyle 61\mid k-1\). Ez a két eset – mivel most \(\displaystyle k\leq 61\) – \(\displaystyle k=60\), illetve \(\displaystyle k=1\) esetén áll fenn, tehát \(\displaystyle 1^2\) és \(\displaystyle 60^2\) az első oszlopban vannak, a többi 59 négyzetszám nem, így ebből 59 megfelelő téglalapot kapunk.

Most vizsgáljuk meg, hány olyan \(\displaystyle 1\times 2\)-es téglalap van, aminél a két négyzet egy oszlopban van, továbbá a lejjebb lévő négyzete (ami a nagyobb értéket fedi) négyzetszám. Ehhez azt kell meghatároznunk, hogy az \(\displaystyle 1^2,2^2,\dots,61^2\) számok közül hány nem az első sorban van. Az első sorban lévő négyzetszámok \(\displaystyle 1,4,9,16,25,36,49\) (hiszen a 64 már a második sorba kerül), a többi 54 négyzetszám (\(\displaystyle 8^2,9^2,\dots,61^2\)) nem az első sorban van, így ebből 54 megfelelő téglalapot kapunk.

Tehát az olyan \(\displaystyle 1\times 2\)-es téglalapok száma, ahol a számok összege negatív: \(\displaystyle 59+54=113\).

Statistics:

122 students sent a solution.
5 points:	64 students.
4 points:	29 students.
3 points:	12 students.
2 points:	9 students.
1 point:	4 students.
0 point:	4 students.

Problems in Mathematics of KöMaL, March 2021