Problem statement

My son, being a first grader, recently struggled with this piece of math:

Consider this system of equations:

\[ a + b + c = 20\\ d + e + f = 14\\ g + h + i = 11\\ a + d + g = 15\\ b + e + h = 10\\ c + f + i = 20\\ a + e + i = 20\\ g + e + c = 10\]

In R:

Let \(A\) be the LHS of the equation system:

A <- tibble::tribble(
  ~a, ~b, ~c, ~d, ~e, ~f, ~g, ~h, ~i,
  1L, 1L, 1L, 0L, 0L, 0L, 0L, 0L, 0L,
  0L, 0L, 0L, 1L, 1L, 1L, 0L, 0L, 0L,
  0L, 0L, 0L, 0L, 0L, 0L, 1L, 1L, 1L,
  1L, 0L, 0L, 1L, 0L, 0L, 1L, 0L, 0L,
  0L, 1L, 0L, 0L, 1L, 0L, 0L, 1L, 0L,
  0L, 0L, 1L, 0L, 0L, 1L, 0L, 0L, 1L,
  0L, 0L, 1L, 0L, 1L, 0L, 1L, 0L, 0L,
  1L, 0L, 0L, 0L, 1L, 0L, 0L, 0L, 1L
  )

A
#> # A tibble: 8 x 9
#>       a     b     c     d     e     f     g     h     i
#>   <int> <int> <int> <int> <int> <int> <int> <int> <int>
#> 1     1     1     1     0     0     0     0     0     0
#> 2     0     0     0     1     1     1     0     0     0
#> 3     0     0     0     0     0     0     1     1     1
#> 4     1     0     0     1     0     0     1     0     0
#> 5     0     1     0     0     1     0     0     1     0
#> 6     0     0     1     0     0     1     0     0     1
#> 7     0     0     1     0     1     0     1     0     0
#> 8     1     0     0     0     1     0     0     0     1

As matrix:

Am <- as.matrix(A)
Am
#>      a b c d e f g h i
#> [1,] 1 1 1 0 0 0 0 0 0
#> [2,] 0 0 0 1 1 1 0 0 0
#> [3,] 0 0 0 0 0 0 1 1 1
#> [4,] 1 0 0 1 0 0 1 0 0
#> [5,] 0 1 0 0 1 0 0 1 0
#> [6,] 0 0 1 0 0 1 0 0 1
#> [7,] 0 0 1 0 1 0 1 0 0
#> [8,] 1 0 0 0 1 0 0 0 1

dim(Am)
#> [1] 8 9

So we have a system of 8 rows and 9 coefficients, that’s a underdetermined system, hence there are more than 1 solution.

Let \(X\) be the vector of coefficients.

Let \(Y\) be the RHS of the system:

Y <- c(20, 14, 11, 15, 10, 20, 10, 20)

Ym <- matrix(Y, ncol = 1)

Ym
#>      [,1]
#> [1,]   20
#> [2,]   14
#> [3,]   11
#> [4,]   15
#> [5,]   10
#> [6,]   20
#> [7,]   10
#> [8,]   20

Solve it

Drawing from this source, we can solve underdetermined systems of equations like this:

X <- qr.coef(qr(Am), Ym)
X[is.na(X)] <- 0

X
#>   [,1]
#> a   17
#> b    7
#> c   -4
#> d  -13
#> e    3
#> f   24
#> g   11
#> h    0
#> i    0

Not a solution

I forgot to implement that only positive integers are allowed. Sigh.

Here come the solution

My colleague Norman Markgraf, a true math guy, provided this beautiful solution.

Thank you, Norman!