Solving problems with graphs

I saw this question on Quora:

A teacher assigns each of her 18 students a different integer from 1 through 18. The teacher forms pairs of study partners by using the rule that the sum of the pair of numbers is a perfect square. Assuming the 9 pairs of students follow this rule, the student assigned which number must be paired with the student assigned the number 1?

A. 16
B. 15
C. 9
D. 8
E. 3

I liked the approach that used a graph to illustrate and arrive at the answer. Below is the same approach using R.

# use the combn() function to generate all pair combinations (not permutations)
m <- t(combn(1:18, 2))

head(m)
     [,1] [,2]
[1,]    1    2
[2,]    1    3
[3,]    1    4
[4,]    1    5
[5,]    1    6
[6,]    1    7

tail(m)
       [,1] [,2]
[148,]   15   16
[149,]   15   17
[150,]   15   18
[151,]   16   17
[152,]   16   18
[153,]   17   18

We can check which pairs are perfect squares by using sqrt() and modulus.

# integers have no remainders when divided by one
34 %% 1
[1] 0

# floats will have a remainder
34.1 %% 1
[1] 0.1

# numbers that are not perfect squares will
# be a float when the square root is calculated
sqrt(25)
[1] 5

sqrt(26)
[1] 5.09902

Now to put it all together.

m <- t(combn(1:18, 2))

# store rows that sum to a perfect square
v <- vector()

# counter
k <- 0

# go through each row
for (i in 1:nrow(m)){
  # sum the pairs
  s <- m[i,1] + m[i,2]
  # check perfect square
  if (sqrt(s)%%1 == 0){
    k <- k + 1
    v[k] = i
  }
}

# subset perfect pairs into p
p <- m[v,]
p
      [,1] [,2]
 [1,]    1    3
 [2,]    1    8
 [3,]    1   15
 [4,]    2    7
 [5,]    2   14
 [6,]    3    6
 [7,]    3   13
 [8,]    4    5
 [9,]    4   12
[10,]    5   11
[11,]    6   10
[12,]    7    9
[13,]    7   18
[14,]    8   17
[15,]    9   16
[16,]   10   15
[17,]   11   14
[18,]   12   13

Finally, creating the graph.

# install if necessary
#install.packages('igraph')
library(igraph)
net <- graph.data.frame(p, directed = FALSE)
plot(net, layout = layout_components(net))

pair_graphSince 16, 17, and 18 must pair with 9, 8, and 7, respectively, 2 must pair with 14, 11 with 5, 4 with 12, 13 with 3, 6 with 10. Therefore 1 has to pair with 15.

Print Friendly, PDF & Email



Creative Commons License
This work is licensed under a Creative Commons
Attribution 4.0 International License
.
2 comments Add yours
  1. Nice, solution. But why do you use this annoying loop?
    A vectorized approach looks IMO much better: `m[sqrt(rowSums(m)) %% 1 == 0, ]` even more as R is optimized for such operations.

    1. As usual, I agree with you! Subsetting using logicals is much better. I just feel the approach I went with can be understood by a wider audience, especially those not familiar with R. But thank you for pointing out that it’s not the most efficient way. I should write a disclaimer.

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.