Задачи математических олимпиад: Ферзи на шахматной доске

главная страница сайта Приглашение в мир математики

Задача

Широко известна задача расположения восьми ферзей на шахматной доске так, чтобы они не угрожали друг другу. Один из вариантов её решения представлен ниже:

      Ф        
            Ф  
    Ф          
              Ф
  Ф            
        Ф      
Ф              
          Ф    

Для решения же конкурсной задачи от IBM необходимо найти, какое наибольшее количество ферзей можно разместить на доске NxN так, чтобы каждый был под боем не более чем у одного ферзя. Требуется обосновать свой результат и найти требуемые расположения для досок 8х8 и 30х30. Решения должны представлять собой пары координат (х,у).

Решение

Докажем, что верхняя граница для доски NxN равна 4N/3. Поскольку каждый ферзь угрожает не более чем одному другому ферзю, то не может быть больше двух ферзей на горизонталь/вертикаль.

Обозначим через $x_i$количество горизонталей с i ферзями, а $y_i$– количество вертикалей с i ферзями.

Понятно, $x_0+x_1+x_2 = n$и таким образом $x_1+x_2 \le n$. Так же и для y: $y_1+y_2 \le n$.

Каждый из $2x_2$ферзей в $x_2$горизонталях уже угрожает ферзю, так что как минимум в $2x_2$вертикалях стоит только по одному ферзю, т.е. $2x_2 \le y_1$. Аналогично $2y_2 \le x_1$.
Количество ферзей m равно $x_1+2x_2$а также $m = y_1+2y_2$. Решая простое неравенство получим:
$m = (x_1+2x_2 + y_1+2y_2)/2 \le (x_1+4/3x_2+1/3y_1 + y_1+4/3y_2+1/3x_1)/2 = 2(x_1+x_2 +y_1+y_2)/3 = 4/3 n$

Задайте вопрос на блоге о математике