Простые задачки про ферзей.

[Sirion]

Продолжать "Чёрный ящик Пандоры"мне было локально лениво, поэтому в качестве компенсации выкладываю побочные результаты своих исследований:

1) Докажите, что на шахматной доске произвольного размера невозможно расставить несколько ферзей так, чтобы каждый бил ровно пять других.
2) Докажите, что при n>3 на шахматной доске n x n можно расставить 3n-4 ферзей так, чтобы каждый бил ровно четырёх других.
3) Докажите, что на шахматной доске n x n можно расставить не более 2n ферзей так, чтобы каждый бил ровно трёх других, и при этом для n>1  2n ферзей всегда можно расставить таким образом.

здесь был хайд:
4440404
0000004
0004000
4000004
0004000
4000000
4040444

[moonlight]

1) если более трёх ферзей стоят не на одной линии то из них можно выбрать несколько таких которые образуют выпуклый многоугольник внутри или на границах которого будут все остальные ферзи. ферзи стоящие в вершинах этого многоугольника могут бить не более четырёх других ферзей. 

[moonlight]

2)

0 1 0 0 0 0 1 0
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
0 1 1 1 1 1 1 0

3(n-2)+2=3n-4

[Sirion]

Таки совершенно верно.

[BIVES]

3)
  1 0 0 0 1
  1 0 0 0 0
  1 0 0 0 0
  1 0 0 0 0
  1 1 1 1 1

Доказать, что больше чем 2n расставить нельзя,  наверное, можно по индукции предположив, что с точностью до всех симметрий существует только предложенная мной расстановка, но я могу быть неправ.
   

[moonlight]

  1 1 1 1 1
  0 0 0 0 0
  0 0 0 0 0
  0 0 0 0 0
  1 1 1 1 1

  1 0 0 1 1
  0 0 1 0 0
  1 1 0 0 0
  0 0 0 0 1
  1 1 0 0 1

Расставить 2n+1 ферзя точно нельзя.

[Sirion]

Расставить 2n+1 ферзя точно нельзя.

нуу, это как бы и требуется доказать)

[moonlight]

Расставить 2n+1 ферзя точно нельзя.

Это я про нечётные числа вообще.

[Sirion]

а как же три ферзя треугольничком? о_О

[Um_nik]

И они буду бить ровно 2 других. А надо трех.

[Sirion]

Тьфу, перепутал задачу. Ну да, количество нечётных вершин чётно.

[moonlight]

3) Докажите, что на шахматной доске n x n можно расставить не более 2n ферзей так, чтобы каждый бил ровно трёх других

Вот доска 8х8 и на ней 18 ферзей.

[Sirion]

Ня. Сейчас уберу хайд)