Формула для числа прямоугольников (олимпиада Приморского кр)

[Sonkina]

Выразите через натуральное число n количество прямоугольников на координатной плоскости со сторонами, параллельными осям и целочисленными вершинами (a, b) $0\le a, b\le n$

[ИСН]

Большинство людей, когда надо узнать число дней с 26-го, например, по 31-е число месяца, считает путём загибания пальцев. Это из той же оперы?

[svv]

ИСН писал(а):

Это из той же оперы?

Нет, это из олимпиады Приморского края.

[Sonkina]

ИСН в сообщении #426873 писал(а):

Большинство людей, когда надо узнать число дней с 26-го, например, по 31-е число месяца, считает путём загибания пальцев. Это из той же оперы?

Ну а если $n=100$ тоже на пальцах будете? Пальцев не хватит

[ИСН]

Вот поэтому-то математики вывели формулу, сколько целых чисел умещается от сих до сих, и ею пользуются.

[Sonkina]

ИСН в сообщении #426878 писал(а):

Вот поэтому-то математики вывели формулу, сколько целых чисел умещается от сих до сих, и ею пользуются.

Вы точно эту задачу решаете, а не какую другую?

[svv]

Sonkina, мне тоже совершенно непонятно, в чем фишка. Вы можете ещё как-то по другому объяснить условие?
А то у меня получается совершенно недоброе представление об олимпиаде Приморского края.

[Null]

$\left(\frac{n(n+1)}{2}\right)^2$?

[Sonkina]

svv в сообщении #426885 писал(а):

Sonkina, мне тоже совершенно непонятно, в чем фишка. Вы можете ещё как-то по другому объяснить условие?

Попробую. На декартовой плоскости дано множество всех целочисленных точек, каждая из координат которых не меньше нуля и не больше n. Сколькими способыми можно выбрать прямоугольник, чтобы его вершины лежали в этом множестве, а стороны были параллельны осям координат? Так понятней? А Вы о чем подумали сначала?

[svv]

Я всё понял. Надо найти количество всевозможных подпрямоугольников, помещающихся в большой прямоугольник. Их там туча. Отличающиеся только сдвигом считаются всё равно разными. Так?

Подумал примерно то же, что и Null.

[Sonkina]

Null в сообщении #426888 писал(а):

$\left(\frac{n(n+1)}{2}\right)^2$?

А вопросительный знак - это что? Я знаю что восклицательный это факториал, а вопросительный?

-- Ср мар 23, 2011 23:42:34 --

svv в сообщении #426894 писал(а):

Я всё понял. Надо найти количество всевозможных подпрямоугольников, помещающихся в большой прямоугольник. Их там туча. Отличающиеся только сдвигом считаются всё равно разными. Так?

Подумал примерно то же, что и Null.

Только не просто большой прямоугольник, а именно большой квадрат.

[age]

Null в сообщении #426888 писал(а):

$\left(\frac{n(n+1)}{2}\right)^2$?

Немножко не так. Для каждой пары $(a_0,b_0)$ - координат первой точки подойдут любые пары $(a_1,b_1)$ координат для второй точки. Кроме $(a_0,b_0)$, т.к. в данном случае прямоугольник будет вырожденный. Также будут вырождаться в отрезок все прямоугольники у которых будет совпадать хоть одна координата. Поэтому их всех надо исключить. Комбинаторная задача. Надо посчитать.

[kocuHyc]

age в сообщении #426903 писал(а):

Null в сообщении #426888 писал(а):

$\left(\frac{n(n+1)}{2}\right)^2$?

Немножко не так. Для каждой пары $(a_0,b_0)$ - координат первой точки подойдут любые пары $(a_1,b_1)$ координат для второй точки. Кроме $(a_0,b_0)$, т.к. в данном случае прямоугольник будет вырожденный. Также будут вырождаться в отрезок все прямоугольники у которых будет совпадать хоть одна координата. Поэтому их всех надо исключить. Комбинаторная задача. Надо посчитать.

http://e-science.ru/forum/index.php?showtopic=29108

[Xenia1996]

Null в сообщении #426888 писал(а):

$\left(\frac{n(n+1)}{2}\right)^2$?

Выведенная Вами формула является частным случаем более общей закономерности, согласно которой число прямоугольников (с целочисленными вершинами и соронами, параллельными осям координат) внутри (не обязательно строго внутри) большого прямоугольника n на m равна произведению энного и эмного треугольных чисел.
$\frac{n(n+1)}2 \cdot \frac{m(m+1)}2$

Частный случай $n=2; m=3$ подробно рассмотрен в этом детском саду, а задачу, я полагаю, ТС взяла отсюда (год 1990, задача 1).