Results 1 to 8 of 8
  1. #1
    Bronze Lounger
    Join Date
    Jan 2001
    Location
    La Jolla, CA
    Posts
    1,468
    Thanks
    30
    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) 3
    Last edited by kweaver; 2015-07-23 at 14:33.

  2. #2
    Star Lounger
    Join Date
    Jul 2013
    Location
    Murphy, NC
    Posts
    64
    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, 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. #3
    Bronze Lounger
    Join Date
    Jan 2001
    Location
    La Jolla, CA
    Posts
    1,468
    Thanks
    30
    Thanked 61 Times in 57 Posts
    PERFECT! Nice going.

  4. #4
    Gold Lounger Maudibe's Avatar
    Join Date
    Aug 2010
    Location
    Pa, USA
    Posts
    2,629
    Thanks
    114
    Thanked 644 Times in 588 Posts
    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. #5
    Gold Lounger Maudibe's Avatar
    Join Date
    Aug 2010
    Location
    Pa, USA
    Posts
    2,629
    Thanks
    114
    Thanked 644 Times in 588 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!

  6. #6
    New Lounger
    Join Date
    Apr 2015
    Posts
    18
    Thanks
    0
    Thanked 0 Times in 0 Posts
    And what's the right answer? Please write details..

  7. #7
    Bronze Lounger
    Join Date
    Jan 2001
    Location
    La Jolla, CA
    Posts
    1,468
    Thanks
    30
    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.

  8. #8
    New Lounger
    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.png
    Last edited by comprar; 2016-05-27 at 05:36.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •