Results 1 to 8 of 8

20150721, 19:32 #1
 Join Date
 Jan 2001
 Location
 La Jolla, CA
 Posts
 1,459
 Thanks
 29
 Thanked 61 Times in 57 Posts
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) 3Last edited by kweaver; 20150723 at 13:33.

20150724, 11:02 #2
 Join Date
 Jul 2013
 Location
 Murphy, NC
 Posts
 61
 Thanks
 0
 Thanked 8 Times in 8 Posts
I wasn't sure whether this fairly lengthy chain of reasoning is what you're looking for. Anyway, in trying to determine the pairings, 187, 178, and 169 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.

20150724, 12:03 #3
 Join Date
 Jan 2001
 Location
 La Jolla, CA
 Posts
 1,459
 Thanks
 29
 Thanked 61 Times in 57 Posts
PERFECT! Nice going.

20150726, 04:29 #4
 Join Date
 Aug 2010
 Location
 Pa, USA
 Posts
 2,559
 Thanks
 111
 Thanked 620 Times in 565 Posts
A teacher assigns each of her 18 students a different integer from 1 through 18
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

20150726, 11:10 #5
 Join Date
 Aug 2010
 Location
 Pa, USA
 Posts
 2,559
 Thanks
 111
 Thanked 620 Times in 565 Posts
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!

20150914, 04:08 #6
 Join Date
 Apr 2015
 Posts
 18
 Thanks
 0
 Thanked 0 Times in 0 Posts
And what's the right answer? Please write details..

20150914, 19:44 #7
 Join Date
 Jan 2001
 Location
 La Jolla, CA
 Posts
 1,459
 Thanks
 29
 Thanked 61 Times in 57 Posts
David, above, explained it correctly. It's often helpful to work "backwards" in problems like this to eliminate options.

20151116, 05:56 #8
 Join Date
 Nov 2015
 Posts
 7
 Thanks
 0
 Thanked 0 Times in 0 Posts
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)
g < graph.adjacency(p, "undirected")
V(g)$label < V(g)$name
plot(g, layout=layout.fruchterman.reingold)
tGdCr.pngLast edited by comprar; 20160527 at 04:36.