Задача 10. Лестница
Дана клетчатая фигура в виде лестницы, содержащей n ступенек (на рисунке приведён пример для n=11).

Сколько значений n, удовлетворяющих неравенству 300

Уголок из трёх клеток — клетчатая фигура, состоящая из трёх клеток, одна из которых имеет общие границы с двумя другими, причём эти общие границы являются соседними сторонами этой клетки:

Решение состоит из двух программ.

1) Методом перебора определяем,

что на уголки можно разрезать треугольники со стороной 2, 6, 8, 9, и

11. Треугольники со сторонами 3 и 5 разрезать не получится.
2)

Замечаем, что из двух уголков можно составить прямоугольник 2*3 (назовем

его «универсальный кирпичик»), а из 12 уголков — квадрат 6*6.
3)

Теперь мы можем разрезать большую фигуру на квадраты 6*6 и треугольники

со стороной 6. В остатке будут «полоски» шириной n и высотой 1, 2, 3, 4,

5.
4) Замечаем, что из универсальных кирпичиков — прямоугольников

2*3 можно составить такие фигуры, как 6*11 (6+3+2), 6*9 (6+3), 6*2 (2

кирпичика, лежащих горизонтально).
5) Итак, чтобы разрезать большую

фигуру на уголки, мы разрезаем ее сверху вниз на квадраты и треугольники

со стороной 6, пока не порежем всю фигуру, либо получим в остатке

полоску высотой 2, 9, или 11 и шириной n.
6) Из шага (1) нам

известно, что треугольники размером a = 2, 9 и 11 можно порезать на

уголки. После этого останется полоска размером (n — a)*a, но (n — a)

делится на 6, поэтому мы можем порезать ее на прямоугольники 2*3, как

следует из шага 4.
7) Конечно, фигуру можно разрезать на уголки только тогда, когда число ее клеток кратно 3.

Решение методом полного перебора для первых n:

uses crt, math;

var matrix: array[1..700] of array[1..700] of smallint;
{ маркер для красоты }
var m: integer;
var total, n: integer;
var iteration: extended;

{ x, y }
type TCoords = array[1..2] of smallint;

procedure clear_matrix();
var x, y: integer;
begin
        for y:= 1 to 700 do begin
                for x := 1 to y do begin
                        { свободно }
                        matrix[x][y] := 0;
                end;
                for x := y + 1 to 700 do begin
                        { граница }
                        matrix[x][y] := 2;
                end;
        end;
end;

procedure print_matrix();
var v, x, y: integer;
begin
        for y:= 1 to 20 do begin
                for x := 1 to 20 do begin
                        v := matrix[x][y];
                        if v = 2 then write(' ') else write(v);
                end;
                writeln();
        end;
end;

{ координата первой свободной клетки или (0,0) если все клетки заняты }
function first_empty(): TCoords;
var x, y: integer;
var coords: TCoords;
label done;
begin
        coords[1] := 0;
        coords[2] := 0;

        for y := 1 to n do begin
                for x := 1 to n do begin
                        if matrix[x][y] = 0 then begin
                                coords[1] := x;
                                coords[2] := y;

                                goto done;
                        end;
                end;
        end;
done:
        first_empty := coords;
end;

function solve_matrix(): integer;
var coords: TCoords;
var r, i, x, y: integer;
label solved;
begin
        iteration := iteration + 1;

        coords := first_empty();
        x := coords[1];
        y := coords[2];

        m := m + 1;
        if m > 9 then m := 3;

        if x <> 0 then begin
            if matrix[x][y] <> 0 then write('!');
            if (x < n) and (y < n) then begin
                { общее }
                matrix[x][y] := m;

                {
                         @-
                         ##
                }
                if (x + 1) <> y then begin
                        if (matrix[x][y + 1] = 0) and (matrix[x + 1][y + 1] = 0) then begin
                                matrix[x][y + 1] := m;
                                matrix[x + 1][y + 1] := m;

                                r := solve_matrix();
                                if r <> 0 then begin
                                        goto solved;
                                end;

                                { восстанавливаем }
                                matrix[x][y + 1] := 0;
                                matrix[x + 1][y + 1] := 0;
                        end
                end;

                {

                        ##
                }
                if (x > 1) and (y > 1) then begin
                        if (matrix[x — 1][y + 1] = 0) and (matrix[x][y + 1] = 0) then begin
                                matrix[x — 1][y + 1] := m;
                                matrix[x][y + 1] := m;

                                r := solve_matrix();
                                if r <> 0 then begin
                                        goto solved;
                                end;

                                { восстанавливаем }
                                matrix[x — 1][y + 1] := 0;
                                matrix[x][y + 1] := 0;
                        end
                end;

                {
                        @#
                        -#
                }
                if y > 1 then begin
                        if (matrix[x + 1][y] = 0) and (matrix[x + 1][y + 1] = 0) then begin
                                matrix[x + 1][y] := m;
                                matrix[x + 1][y + 1] := m;

                                r := solve_matrix();
                                if r <> 0 then begin
                                        goto solved;
                                end;

                                { восстанавливаем }
                                matrix[x + 1][y] := 0;
                                matrix[x + 1][y + 1] := 0;
                        end
                end;

                {
                        @#
                        #
                }
                if (y > 1) then begin
                        if (matrix[x + 1][y] = 0) and (matrix[x][y + 1] = 0) then begin
                                matrix[x + 1][y] := m;
                                matrix[x][y + 1] := m;

                                r := solve_matrix();
                                if r <> 0 then begin
                                        goto solved;
                                end;

                                { восстанавливаем }
                                matrix[x + 1][y] := 0;
                                matrix[x][y + 1] := 0;
                        end
                end;

                { общее }
                matrix[x][y] := 0;
            end;

            { фигура не может быть разрезана }
            solve_matrix := 0;
        end
        else begin
                { все клетки заполнены — фигура разрезана }
                writeln('solved: n=', n:3, ', iterations: ', iteration:15:0);
                {print_matrix();}
                total := total + 1;
            solved:
                solve_matrix := 1;
        end;
end;

begin
        total := 0;
        m := 3;
        { главный цикл }
        for n := 1 to 120 do begin
                { если число клеток не кратно трем, то разрезать не получится }
                if n*(n + 1) mod 6 = 0 then begin
                        iteration := 0;
                        clear_matrix();
                        if solve_matrix() = 0 then writeln('not solved: n=', n:3);
                end;
        end;
        writeln('total: ', total);
end.

Решение для произвольных n:

uses math;

var i: integer;
var s: integer;
var y: integer;
var n: integer;

begin
        y := 0;
        n := 0;

        for i := 301 to 699 do begin
                { число клеток (сумма арифметической прогрессии) кратно 3 }
                if i * (i + 1) mod 6 = 0 then begin
                        s := i;
                        while s > 0 do begin
                                if (s = 0) or (s = 2) or (s = 9) or (s = 11) then begin
                                        y := y + 1;
                                        break
                                end else begin
                                        { никогда не выполняется }
                                        if s < 6 then begin
                                                n := n + 1;
                                        end;
                                end;
                                s := s — 6;
                        end;
                end;
        end;

        writeln();
        writeln('yes: ', y);
        writeln('no: ', n);
end.

Ответ: 200.