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))

*Since 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*.

This work is licensed under a Creative Commons

Attribution 4.0 International License.

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.

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.