fork download
  1. /*
  2.  * \( (3) \) Let \(n\) and \( m\) be positive integers. An \( n \times  m \) rectangle is tiled
  3.  * with unit squares. Let \(r(n,m) \) denote the number of rectangles formed by the edge of these
  4.  * unit squares. Thus, for example, \(r(2, 1) = 3\). Can you find \( r(11, 12) \)?.
  5.  *
  6.  * In a row of length n,there are
  7.  *
  8.  * number rectangle dimensions
  9.  * n 1x1
  10.  * n-1 2x1
  11.  * n-2 3x1
  12.  * n-3 4x1
  13.  * n-a (a+1)x1
  14.  *
  15.  * a+1 = n at most, a = n-1
  16.  * n-(n-1) nx1
  17.  * 1 nx1
  18.  *
  19.  * Sum is from 1 to n which = n(n + 1)/2
  20.  * Because of the way I plan to do the rest of this, I'm going to exclude the 1x1 dimension rectangle. Sum is then from 0 to n-1, so:
  21.  * (n-1)((n-1) + 1)/2
  22.  * n(n-1)/2
  23.  * multiplied by m rows,
  24.  * There are,
  25.  * mn(n-1)/2 rectangles with a dimension of 1 in the whole rectangle LOOKING ONE WAYS. The rectangle can be flipped and the process repeated, so you must add:
  26.  * nm(m-1)/2
  27.  *
  28.  * Now for 2x2 rectangles.
  29.  * They can extend for (n-1) lines across, and (m-1) down. So,
  30.  * (n-1)(m-1)
  31.  *
  32.  * Since 2x2 are a square dimension, like 1x1 we only need to count it going one way.
  33.  * Sum becomes:
  34.  * mn + mn(n-1)/2 + nm(m-1)/2 + (n-1)(m-1)
  35.  *
  36.  * 2x3?
  37.  * (n-1)(m-2) and then also (m-1)(n-2)
  38.  *
  39.  * Sum is then:
  40.  * mn + mn(n-1)/2 + nm(m-1)/2 + (n-1)(m-1) + (n-1)(m-2) + (m-1)(n-2)
  41.  *
  42.  * I see a pattern, so I'm going to redo it.
  43.  *
  44.  * (m - 0)(n - 0) for 1x1 rectangles
  45.  * (m - 1)(n - 0) for 2x1 rectangles
  46.  * (m - 2)(n - 0) for 3x1 rectangles
  47.  * ...
  48.  * (m - (m-1))(n - 0) for mx1 rectangles
  49.  * (m - a)(n - b) for (a+1) by (b+1) rectangles
  50.  *
  51.  * All of this is for going one way. If the rectangle is flipped, then it is done again IF a != b.
  52.  * I'm not good with sums, so I wrote a program to calculate this.
  53.  *
  54.  */
  55.  
  56. import java.lang.Math;
  57.  
  58. public class Main {
  59. public static void main (String[] args) { //no error checking on purpose, no need really
  60. int total = 0;
  61. int m = 11;
  62. int n = 12;
  63.  
  64. for (int ai = 1; ai <= Math.min(m, n); ai++) { //loops through all the possible first dimensions
  65. for (int bi = 1; bi <= Math.max(m, n); bi++) { //loops through all possible second dimensions
  66. if (bi >= ai) { //so you don't count things twice
  67. total += numberOfaxbRectanglesInmxnRectangle(ai, bi, m, n);
  68. }//if
  69. }//for
  70. }//for
  71.  
  72. System.out.println(total);
  73. }
  74.  
  75. public static int numberOfaxbRectanglesInmxnRectangle(int a, int b, int m, int n) {
  76. int ret = 0;
  77. ret += (m - (a-1)) * (n - (b-1)); //see above explanation
  78. if (a != b && a <= n && b <= m) { //ensures you don't try and see how many 4x2s are in a 2x4
  79. ret += (n - (a-1)) * (m - (b-1)); //if it isn't a square, could have recursed but w/e
  80. }
  81. System.out.println(ret + " many " + a + " x " + b);
  82. return ret;
  83. }
  84. }
Success #stdin #stdout 0.03s 245632KB
stdin
Standard input is empty
stdout
132 many 1 x 1
241 many 1 x 2
218 many 1 x 3
195 many 1 x 4
172 many 1 x 5
149 many 1 x 6
126 many 1 x 7
103 many 1 x 8
80 many 1 x 9
57 many 1 x 10
34 many 1 x 11
11 many 1 x 12
110 many 2 x 2
199 many 2 x 3
178 many 2 x 4
157 many 2 x 5
136 many 2 x 6
115 many 2 x 7
94 many 2 x 8
73 many 2 x 9
52 many 2 x 10
31 many 2 x 11
10 many 2 x 12
90 many 3 x 3
161 many 3 x 4
142 many 3 x 5
123 many 3 x 6
104 many 3 x 7
85 many 3 x 8
66 many 3 x 9
47 many 3 x 10
28 many 3 x 11
9 many 3 x 12
72 many 4 x 4
127 many 4 x 5
110 many 4 x 6
93 many 4 x 7
76 many 4 x 8
59 many 4 x 9
42 many 4 x 10
25 many 4 x 11
8 many 4 x 12
56 many 5 x 5
97 many 5 x 6
82 many 5 x 7
67 many 5 x 8
52 many 5 x 9
37 many 5 x 10
22 many 5 x 11
7 many 5 x 12
42 many 6 x 6
71 many 6 x 7
58 many 6 x 8
45 many 6 x 9
32 many 6 x 10
19 many 6 x 11
6 many 6 x 12
30 many 7 x 7
49 many 7 x 8
38 many 7 x 9
27 many 7 x 10
16 many 7 x 11
5 many 7 x 12
20 many 8 x 8
31 many 8 x 9
22 many 8 x 10
13 many 8 x 11
4 many 8 x 12
12 many 9 x 9
17 many 9 x 10
10 many 9 x 11
3 many 9 x 12
6 many 10 x 10
7 many 10 x 11
2 many 10 x 12
2 many 11 x 11
1 many 11 x 12
5148