Problem 6. It is easy to place a set of ships for the game "Battleship" on a $10 \times 10$ board (see Fig. 4). On what smallest square board can this set be placed? (Let's recall that according to the rules, ships should not touch even at the corners.)

$[8$ points] ( $A$. D. Blinkov)
Answer. On a $7 \times 7$ board.

![](https://cdn.mathpix.com/cropped/2024_05_06_e514393ca180e6b2092dg-09.jpg?height=502&width=514&top_left_y=1258&top_left_x=227)

Fig. 4

![](https://cdn.mathpix.com/cropped/2024_05_06_e514393ca180e6b2092dg-09.jpg?height=369&width=361&top_left_y=1321&top_left_x=865)

Fig. 5

Solution. An example of placing ships on a $7 \times 7$ board is shown in Fig. 5. It remains to prove that it is impossible to place the ships on a $6 \times 6$ board.

Proof 1. We will count not the cells, but the nodes of the board occupied by the ships. A $1 \times 4$ ship occupies $2 \cdot 5=10$ nodes, a $1 \times 3$ ship occupies 8 nodes, a $1 \times 2$ ship occupies 6 nodes, and a $1 \times 1$ ship occupies 4 nodes; moreover, according to the placement rules, one node cannot belong to more than one ship. Therefore, all the ships occupy $10+2 \cdot 8+3 \cdot 6+4 \cdot 4=50$ nodes, and it is impossible to place them all on a board with fewer nodes. But the $6 \times 6$ board has only $(6+1)^{2}=49$ nodes.

![](https://cdn.mathpix.com/cropped/2024_05_06_e514393ca180e6b2092dg-10.jpg?height=247&width=247&top_left_y=385&top_left_x=1081)

| 7,8 | from March 19 to May 14 |
| 54 | $(499) ~ 245-99-72$  $(499) 245-54-25$ | Fotieva St., 18  (m. "Oktyabrskaya")  www.sch2.ru | 8 | from February to May, Fridays at $9^{15}$ |
| 57 | $(495) 691-85-72$  $(495) 691-54-58$ | Mal. Znamensky per., 7/10,  bld. 5 (m. "Borovitskaya")  www.sch57.msk.ru | 8 | from March 31, Wednesdays at $16^{00}$ |
| 179 | (495) 692-48-51 | Bol. Dmitrovka St., 5/6, bld. 7  (m. "Okhotny Ryad") www.179.ru | 8 | interview in March-April |
| 192 | $(499) 137-33-55$  $(499) 137-72-85$ | Leninsky Prospekt 34-A  (m. "Leninsky Prospekt")  www.sch192.ru | 5,$7 ;$  additional in 8 | March-May, Fridays at $16^{00}$ |
| 218 | (495) 976-19-85 | Dmitrovskoye Shosse, 5a  school218.ru | $6-8$ | registration for the interview from April 1 |
| 1543 | $(495) 433-16-44$  $(495) 434-26-44$ | St. 26 Baku Commissars,  3, bld. 5 (m. "Yugo-Zapadnaya")  www. 1543. ru | 8 | April |
| Intel-  lektual | \| 4495) 445-52-10 | Kremenchugskaya St., 13  (m. "Slavyansky Bulvar")  int-sch.ru | 5,$7 ;$  additional in 8 | registration from February, exams from late March |

Information provided by the schools to the Moscow Center for Continuous Mathematical Education. Published free of charge.

Detailed information on enrollment in these and other classes is available on the website www.mccme.ru

The VIII City Oral Mathematics Olympiad for $6-7$ grades will take place on February 28, 2010 (Sunday).

Students who have received a diploma of prizewinner or certificate in at least one of the following mathematical competitions (of the current or previous academic year) are invited to the Olympiad: