Задача 10. Лестница
Дана клетчатая фигура в виде лестницы, содержащей n ступенек (на рисунке приведён пример для n=11).
Сколько значений n, удовлетворяющих неравенству 300
Уголок из трёх клеток — клетчатая фигура, состоящая из трёх клеток, одна из которых имеет общие границы с двумя другими, причём эти общие границы являются соседними сторонами этой клетки:
Дана клетчатая фигура в виде лестницы, содержащей n ступенек (на рисунке приведён пример для n=11).
Сколько значений n, удовлетворяющих неравенству 300
Уголок из трёх клеток — клетчатая фигура, состоящая из трёх клеток, одна из которых имеет общие границы с двумя другими, причём эти общие границы являются соседними сторонами этой клетки:
Answers & Comments
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;
{
[email protected]
##
}
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.