158 lines
4.9 KiB
Plaintext
158 lines
4.9 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "f6ad1b47",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Counting Rectangles](https://projecteuler.net/problem=85)\n",
|
|
"\n",
|
|
"Let $R(m, n)$ give the number of rectangles contained in an $m \\times n$ grid. We will derive a simple formula for $R$. First, observe that an $m \\times 1$ grid contains $\\frac{m(m+1)}{2}$ rectangles, i.e.\n",
|
|
"$$R(m, 1) = \\frac{m(m+1)}{2}$$\n",
|
|
"(You could prove this [inductively](https://en.wikipedia.org/wiki/Mathematical_induction) if you really wanted to).\n",
|
|
"\n",
|
|
"Then, we can derive the following recursive formula for $R$.\n",
|
|
"$$R(m, n) = R(m, n - 1) + n R(m, 1)$$\n",
|
|
"To make sense of this formula, consider that the number of rectangles in an $m \\times n$ grid must be the sum of the number of rectangles in an $m \\times (n-1)$ grid (i.e. $R(m, n-1)$) and the number of rectangles in an $m \\times n$ grid *that are at least partially in the bottom row* - these are [disjoint sets](https://en.wikipedia.org/wiki/Disjoint_sets), so there's no double counting with this approach. We already know the number of rectangles that lie *entirely* in the bottom row - it's just $R(m, 1)$. We can then make any of those rectangles any height we want between 1 and $n$, giving the formula $n R(m, 1)$.\n",
|
|
"\n",
|
|
"At this point, we could easily translate this into a recursive function to compute $R$, but we can also simplify this into a closed formula. Substituting the formula for $R(m,1)$ from above, we get\n",
|
|
"$$R(m, n) = R(m, n - 1) + \\frac{mn(m+1)}{2}$$\n",
|
|
"Then, by repeatedly substituting $R(m, n-1)$ with our recursive formula, we get\n",
|
|
"$$R(m, n) = \\frac{mn(m+1)}{2} + \\frac{m(n-1)(m+1)}{2} + \\frac{m(n-2)(m+1)}{2} + \\cdots + \\frac{m(m+1)}{2} = \\sum_{k=1}^n \\frac{mk(m+1)}{2}$$\n",
|
|
"Applying some [summation identities](https://en.wikipedia.org/wiki/Summation) (also see [problem 1](https://projecteuler.net/problem=1)), this simplifies to\n",
|
|
"$$R(m, n) = \\frac{mn(m+1)(n+1)}{4}$$\n",
|
|
"Interestingly, this formula is really just the product of $m$th and $n$th [triangular numbers](https://en.wikipedia.org/wiki/Triangular_number)."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "2c2038a4",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"def R(m, n):\n",
|
|
" return m * n * (m + 1) * (n + 1) // 4"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "f29eaf82",
|
|
"metadata": {},
|
|
"source": [
|
|
"Figuring out the formula's the hard part - now we can just iterate over grid sizes to calculate how many rectangles they have."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "3409e88c",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"totals = dict()\n",
|
|
"\n",
|
|
"for x in range(1, 2001):\n",
|
|
" for y in range(1, 2001):\n",
|
|
" r = R(x, y)\n",
|
|
" totals[(x,y)] = r\n",
|
|
" if r > 2000000:\n",
|
|
" break"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "d9ce5480",
|
|
"metadata": {},
|
|
"source": [
|
|
"We'll figure out which grid is the closest to containing 2000000 rectangles."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"id": "dbc72aaa",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"(36, 77)"
|
|
]
|
|
},
|
|
"execution_count": 3,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"m, n = min(totals, key=lambda x: abs(totals[x] - 2000000))\n",
|
|
"m, n"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "e69c5c48",
|
|
"metadata": {},
|
|
"source": [
|
|
"The area of that grid is our answer."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 4,
|
|
"id": "f230a0d0",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"2772"
|
|
]
|
|
},
|
|
"execution_count": 4,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"m * n"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "d30d6d4f",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Relevant sequences\n",
|
|
"* Number of rectangles in an $m \\times n$ grid: [A098358](https://oeis.org/A098358)\n",
|
|
"\n",
|
|
"#### Copyright (C) 2025 filifa\n",
|
|
"\n",
|
|
"This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"kernelspec": {
|
|
"display_name": "SageMath 9.5",
|
|
"language": "sage",
|
|
"name": "sagemath"
|
|
},
|
|
"language_info": {
|
|
"codemirror_mode": {
|
|
"name": "ipython",
|
|
"version": 3
|
|
},
|
|
"file_extension": ".py",
|
|
"mimetype": "text/x-python",
|
|
"name": "python",
|
|
"nbconvert_exporter": "python",
|
|
"pygments_lexer": "ipython3",
|
|
"version": "3.11.2"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|