The Actuary Puzzle 508 – Square numbers
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
The Actuary Puzzle 508 – Square numbers
Author: Matt Malin
From the puzzle pages of The Actuary June 2012, I attempt to solve the following, making use of R:
This square contains exactly 21 smaller squares. Each of these smaller
squares has sides of integer length, with no two smaller squares having
sides of the same length. Can you find a solution for the size of the 21 smaller
squares? (Note, the 21st square, n, is between squares f, g, m and o).
The approach I decided to take was to calculate a few relationships and work from there to attempt to find working solutions, instead of working out all necessary equations and completely solving. Although there can be probably be an exhaustive set of calculations leading to some form of order of size (and solution), any assumptions on size are based on size differences guaranteed by adjacent squares and following lines directly, not from comparing printed sizes, so this approach may be missing out on easily excluding some more impossible values this way.
Initial rules
Looking at the square and coming up with a few rules hoping to be exhaustive enough, where letter \(x\) here is the value of the length of side on square \(x\):
- Values are integers.
- Values are unique.
- \(o > n\)
- \(m = n + o\)
- \(q = m + o\)
- \(l = m + q\)
- \(s = 0.25 * q \Rightarrow 4 | q\), as all values are integers.
- Derivation: \(t + s = l + q \Rightarrow (u + s) + s = l + q \Rightarrow u + 2s = l + q\)
- \(\Rightarrow (k + s) + 2s = l + q \Rightarrow k + 3s = l + q\)
- \(\Rightarrow (l + s) + 3s = l + q \Rightarrow l + 4s = l + q\)
- \(\Rightarrow 4s = q\)
- Derivation: \(t + s = l + q \Rightarrow (u + s) + s = l + q \Rightarrow u + 2s = l + q\)
- \(4 | q = m + o = (n + o) + o = n + 2o\), so have that \(4 | n + 2o\).
- \(2 | 4\) and \(2 | 2o \Rightarrow 2 | n\), so \(n\) is even.
- \(k = l + s\)
- \(u = k + s\)
- \(t = u + s\)
- \(l – n > p > o\)
- \(r = l + t – n -p\)
- \(j = r – p\)
- \(i = j – p\)
- \(g = q + p – i – n – m\)
- \(f = g – n\)
- \(h = g – i\)
- \(e = i + j – h\)
- \(d = e – h\)
- \(c = d + e\)
- \(b = c + d\)
- \(a = b + f\)
The set of numbers are also contrained by the fact that the total length of each side of the large square is consistent (will check this in three ways):
- \(a + b + c = u + t + r\)
- \(b + c = k + u\)
- \(b + t = k + e + j\)
Also, the total area of the small squares should sum the total area of the large square:
- \((a + b + c)^2 = a^2 + b^2 + c^2 + … + s^2 + t^2 + u^2\)
Calculations
Under these assumptions there are very few lengths which aren’t defined by the lengths of values already determined, so setting up nested loops for searching for working solutions shouldn’t be too computationally intensive.
First decide on maximum values to take across our loops.
max_nn <- 10 max_oo <- 50
Now set up the set of possible values for our first guess (in this case, square \(n\), which is even)
possible_nn <- 2 * 1:(max_nn/2)
Instead of stopping the loop at the first solution, will save all of the combinations in a list outside the loop, to see if there are multiple solutions.
possible_solutions <- list() i <- 1
Now create and check possible values under the rules above, looping across possible values for those not defined strictly by linear sums and moving onto the next possibility when it produces an incorrect combination of values:
for (nn in possible_nn) { possible_oo <- (nn + 1):max_oo # includes that o > n for (oo in possible_oo) { mm <- nn + oo qq <- mm + oo if ((qq%%4) != 0) next ll <- mm + qq if (any(duplicated(c(nn, oo, mm, qq, ll)))) next ss <- qq/4 kk <- ll + ss uu <- kk + ss tt <- uu + ss if (any(duplicated(c(nn, oo, mm, qq, ll, ss, kk, uu, tt)))) next possible_p <- (oo + 1):(ll - nn - 1) possible_p <- possible_p[!{ possible_p %in% c(nn, oo, mm, qq, ll, ss, kk, uu, tt) }] # filter out values already used, as numbers must be unique if (length(possible_p) == 0) next for (pp in possible_p) { rr <- ll + tt - nn - pp jj <- rr - pp ii <- jj - pp gg <- qq + pp - ii - nn - mm ff <- gg - nn hh <- gg - ii ee <- ii + jj - hh dd <- ee - hh cc <- dd + ee bb <- cc + dd aa <- bb + ff all_values <- c(a = aa, b = bb, c = cc, d = dd, e = ee, f = ff, g = gg, h = hh, i = ii, j = jj, k = kk, l = ll, m = mm, n = nn, o = oo, p = pp, q = qq, r = rr, s = ss, t = tt, u = uu) if (any(duplicated(all_values))) next if (aa + bb + cc != uu + tt + rr) next if (bb + cc != kk + uu) next if (bb + tt != kk + ee + jj) next if ((aa + bb + cc)^2 != sum(all_values^2)) next # if execution reaches here, numbers fit criteria: possible_solutions[[i]] <- all_values i <- i + 1 } } }
This produces the following (potential) solutions to the puzzle:
## [[1]] ## a b c d e f g h i j k l m n o p q r s t u ## 50 35 27 8 19 15 17 11 6 24 29 25 9 2 7 18 16 42 4 37 33 ## ## [[2]] ## a b c d e f g h i j k l m n o p q r ## 100 70 54 16 38 30 34 22 12 48 58 50 18 4 14 36 32 84 ## s t u ## 8 74 66 ## ## [[3]] ## a b c d e f g h i j k l m n o p q r ## 150 105 81 24 57 45 51 33 18 72 87 75 27 6 21 54 48 126 ## s t u ## 12 111 99 ## ## [[4]] ## a b c d e f g h i j k l m n o p q r ## 200 140 108 32 76 60 68 44 24 96 116 100 36 8 28 72 64 168 ## s t u ## 16 148 132 ## ## [[5]] ## a b c d e f g h i j k l m n o p q r ## 250 175 135 40 95 75 85 55 30 120 145 125 45 10 35 90 80 210 ## s t u ## 20 185 165 ##
As you can see, they are seem to be multiples of the first solution (when \(a = 50\), \(b = 35\), etc) suggesting a unique solution up to scalar multiples, but these still need to be confirmed. To do this will now attempt to plot the square with layout from the original puzzle, values from the first produced solution.
library(ggplot2) values <- as.list(possible_solutions[[1]]) # use first solution
To set up the plot, need to manually create table of values of corner locations for each square. I used the image of the puzzle to create these points based on lengths of all squares in a given solution.
squares <- list() squares <- with(values, { sq <- list() sq$u <- c(x1 = 0, y1 = 0, x2 = u, y2 = u) sq$u <- c(x1 = 0, y1 = 0, x2 = u, y2 = u) sq$t <- c(x1 = u, y1 = 0, x2 = u + t, y2 = t) sq$r <- c(x1 = u + t, y1 = 0, x2 = u + t + r, y2 = r) sq$k <- c(x1 = 0, y1 = u, x2 = k, y2 = u + k) sq$s <- c(x1 = k, y1 = u, x2 = k + s, y2 = u + s) sq$l <- c(x1 = k, y1 = u + s, x2 = k + l, y2 = u + s + l) sq$q <- c(x1 = k + l, y1 = t, x2 = k + l + q, y2 = t + q) sq$m <- c(x1 = k + l, y1 = t + q, x2 = k + l + m, y2 = t + q + m) sq$o <- c(x1 = k + l + m, y1 = t + q, x2 = k + l + m + o, y2 = t + q + o) sq$n <- c(x1 = k + l + m, y1 = t + q + o, x2 = k + l + m + n, y2 = t + q + o + n) sq$p <- c(x1 = k + l + q, y1 = r, x2 = k + l + q + p, y2 = r + p) sq$j <- c(x1 = k + l + q + p, y1 = r, x2 = k + l + q + p + j, y2 = r + j) sq$i <- c(x1 = a + f + g, y1 = r + p, x2 = a + f + g + i, y2 = r + i) sq$a <- c(x1 = 0, y1 = k + u, x2 = a, y2 = k + u + a) sq$b <- c(x1 = a, y1 = t + q + m + f, x2 = a + b, y2 = t + q + m + f + b) sq$c <- c(x1 = a + b, y1 = r + j + e, x2 = a + b + c, y2 = r + j + e + c) sq$d <- c(x1 = a + b, y1 = r + j + h, x2 = a + b + d, y2 = r + j + h + d) sq$e <- c(x1 = a + b + d, y1 = r + j, x2 = a + b + d + e, y2 = r + j + e) sq$f <- c(x1 = a, y1 = t + l, x2 = a + f, y2 = t + l + f) sq$g <- c(x1 = a + f, y1 = t + q + o, x2 = a + f + g, y2 = t + q + o + g) sq$h <- c(x1 = a + f + g, y1 = r + j, x2 = a + f + g + h, y2 = r + j + h) sq$i <- c(x1 = a + f + g, y1 = r + p, x2 = a + f + g + i, y2 = r + p + i) return(sq) }) squares_df <- data.frame(do.call("rbind", squares), square = names(squares)) squares_df ## x1 y1 x2 y2 square ## u 0 0 33 33 u ## t 33 0 70 37 t ## r 70 0 112 42 r ## k 0 33 29 62 k ## s 29 33 33 37 s ## l 29 37 54 62 l ## q 54 37 70 53 q ## m 54 53 63 62 m ## o 63 53 70 60 o ## n 63 60 65 62 n ## p 70 42 88 60 p ## j 88 42 112 66 j ## i 82 60 88 66 i ## a 0 62 50 112 a ## b 50 77 85 112 b ## c 85 85 112 112 c ## d 85 77 93 85 d ## e 93 66 112 85 e ## f 50 62 65 77 f ## g 65 60 82 77 g ## h 82 66 93 77 h
Now plot this to see if it matches the puzzle, using ggplot2 and the geom “geom_rect” for plotting the rectangles. To achieve random colouring, first rearranged the levels of the factor “square”:
set.seed(1) ggplot(squares_df) + scale_x_continuous(name="x") + scale_y_continuous(name="y") + geom_rect(aes( xmin = x1, xmax = x2, ymin = y1, ymax = y2, fill = factor(square, levels = sample(levels(square)))), colour = "black") + geom_text(aes( x = x1 + (x2 - x1) / 2, y = y1 + (y2 - y1) / 2, label = square)) + opts(legend.position = "none", title = "21 squares")
Final solution!
As you can see, it has produced a correct solution:
unlist(values) ## a b c d e f g h i j k l m n o p q r s t u ## 50 35 27 8 19 15 17 11 6 24 29 25 9 2 7 18 16 42 4 37 33
I’m certain that further algebra playing, coming up with more equations perhaps from the picture, this result can be derived without these loops but it was definitely a fun exercise producing a solution this way.
R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.