{"id":1451,"date":"2021-03-01T15:04:00","date_gmt":"2021-03-01T19:04:00","guid":{"rendered":"http:\/\/mathfun4kids.com\/mlog\/?p=1451"},"modified":"2024-10-25T03:06:57","modified_gmt":"2024-10-25T07:06:57","slug":"mathcounts-exercise-convolution-of-non-zero-squares","status":"publish","type":"post","link":"https:\/\/mathfun4kids.com\/mlog\/?p=1451","title":{"rendered":"MATHCOUNTS Exercise – Convolution of Non-zero Squares"},"content":{"rendered":"\n

A four by four grid of unit squares contains squares of various sizes (1 by 1 through 4 by 4), each of which are formed entirely from squares in the grid. In each of the 16 unit squares, write the number of squares that contain it. For instance, the middle numbers in the top row are 6s because they are each contained in one $1\\times 1$ square, two $2\\times 2$, two $3\\times 3$, and one $4\\times 4$.
(a) <\/strong>What is the sum of all sixteen numbers written in this grid?
(b)<\/strong> What about the same problem with a $10\\times 10$ grid?<\/p>\n\n\n\nClick here<\/a> for the solution.\n

\n\n\n\n

Solution (a)<\/strong> By filling numbers in to the grid, we have the following $4\\times 4$ grid: $$ \\begin{array}{|c|c|c|c|} \\hline 4 & 6 & 6 & 4 \\\\ \\hline 6 & 10 & 10 & 6 \\\\ \\hline 6 & 10 & 10 & 6 \\\\ \\hline 4 & 6 & 6 & 4 \\\\ \\hline \\end{array} $$ Therefore the answer to the questions is $\\boxed{104}$. <\/p>\n\n\n\n

Solution (b)<\/strong> Assume the sum is $S$. There are $10^2$ squares of $1\\times 1$, producing a partial sum of $1^2\\times 10^2$; and $9^2$ squares of $2\\times 2$, producing a partial sum of $2^2 \\times 9^2$; and so on; and finally, there is $1^2$ square of $10\\times 10$, producing a partial sum of $10^2 \\times 1^2$. Therefore, $$S=\\sum_{i=1}^{10}i^2\\cdot(10-i+1)^2=2\\cdot(1^2\\cdot 10^2 + 2^2\\cdot 9^2 + 3^2\\cdot 8^2+ 4^2\\cdot 7^2 + 5^2\\cdot 6^2)$$ $$=2\\cdot(100+324+576+784+900)=2\\cdot 2684=\\boxed{5368}$$<\/p>\n\n\n\n

Note: <\/strong>For a $n\\times n$ grid, the sum is $$S(n)=\\sum_{i=1}^{n}i^2\\cdot(n-i+1)^2$$ The above is the convolution of non-zero squares, producing OEIS<\/a> sequence A033455<\/a>, with the following closed form: $$\\boxed{S(n)=\\dfrac{(n+1)((n+1)^4-1)}{30}=\\dfrac{n(n+1)(n+2)(n^2+2n+2)}{30}}$$<\/p>\n\n\n\n

Challenge: <\/strong>In stead of a grid of squares, what is the answer for a grid consisting of equilateral triangles, such as the following: <\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n<\/div>\n","protected":false},"excerpt":{"rendered":"

A four by four grid of unit squares contains squares of various sizes (1 by 1 through 4 by 4), each of which are formed entirely from squares in the grid. In each of the 16 unit squares, write the … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false},"categories":[13,10],"tags":[],"_links":{"self":[{"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/posts\/1451"}],"collection":[{"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1451"}],"version-history":[{"count":36,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/posts\/1451\/revisions"}],"predecessor-version":[{"id":4574,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/posts\/1451\/revisions\/4574"}],"wp:attachment":[{"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1451"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1451"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1451"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}