# Thread: Pairing up to form perfect squares

1. ## Pairing up to form perfect squares

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 must follow this rule, the student assigned which number must be paired with the student assigned the number 1? (of course, and why?)

EDIT: the original question was presented as a multiple choice.
The possible answers might help in determining the correct answer, but "why" is still needed.

(A) 16, (B) 15, (C) 9, (D) 8, (E) 3

2. I wasn't sure whether this fairly lengthy chain of reasoning is what you're looking for. Anyway, in trying to determine the pairings, 18-7, 17-8, and 16-9 are forced (being that 18+17 falls short of 36). (I soon realized that 15 through 10 could be paired with 1 through 6, respectively, but that doesn't prove that there are no other solutions, hence the following.) This forces 2 to be paired with 14 (because 7 is taken), which in turn forces 11 to be paired with 5 (because 14 is taken), which in turn forces 4 to be paired with 12 (because 5 is taken), which in turn forces 13 to be paired with 3 (because 12 is taken), which in turn forces 6 to be paired with 10 (because 3 is taken), which leaves 1 and 15.

3. PERFECT! Nice going.

4. A teacher assigns each of her 18 students a different integer from 1 through 18
Coming up with a different logic and answer.

4 is a perfect square. Combinations of 4 are: 0+4, 1+3, 2+2. Since 0 is not a possible assigned number and there is only one 2, the only possible combination for 4 is 1+3

Maud

5. Perhaps I read too much into the question. From David's post, I am now assuming that not all the perfect squares need to have a combination rather that all of the combined numbers must equal any perfect square.

got it!

7. David, above, explained it correctly. It's often helpful to work "backwards" in problems like this to eliminate options.

8. You can use outer to compute the allowable pairs. The resulting matrix is the adjacency matrix of a graph, and you just want a Hamiltonian path on it.

# Allowable pairs form a graph
p <- outer(
1:17, 1:17,
function(u,v) round(sqrt(u + v),6) == floor(sqrt(u+v)) )
)
rownames(p) <- colnames(p) <- 1:17
image(p, col=c(0,1))

# Read the solution on the plot
library(igraph)