Question

Short stack. A total of n cards numbered 1 through n is divided into two stacks. What is the minimum value of n such that at least one stack will include a pair of cards whose numbers add up to an exact square?

Answer 1

I have no idea how to do this one...

Answer 2

Hmmm... maybe we can use some of these properties of square numbers:\[
\begin{align}
\text{1.}\quad x^2 &= p_1^2\cdot p_2^2\cdot...\cdot p_j^2\quad\text{where }p_i\text{ are primes}\\
\text{2.}\quad x^2 &\text{has an odd number of divisors}\\
\text{3.}\quad x^2 &=\sum_{k=1}^x2k-1\\
\end{align}
\]

Answer 3

4. Goldbach's conjecture: Every even integer greater than 2 can be expressed as the sum of two primes. And also all even integers greater than 4 can be expressed as the sum of two odd primes.

Answer 4

sorry - I mis-typed property 1 above. It should state x^2 is the product of EVEN powers of prime numbers.

Answer 5

Ok, I thought of another approach. the 1st square number that can be composed of the sum of two number is 4=1+3. so to guarantee that it cannot be formed, the 1 and 3 must be in different piles. Lets call the piles L and R for Left and Right.

So we get:
L: 1
R: 3

next square up from 4 is 9. so looking at what is in the L pile, we see that 9=1+8, so we must place 8 in the R pile. Similarly, 9=3+6 so 6 must go in the L pile, to get:
L: 1, 6
R: 3, 8

next look at what other numbers can be used to pair up to 9:
9=2+7, 4+5
each of these pairs can be put into the L and R piles in two different ways, so we get four possible combinations:
L1: 1, 6, 2, 4
R1: 3, 8, 7, 5

L2: 1, 6, 2, 5
R2: 3, 8, 7, 4

L3: 1, 6, 7, 4
R3: 3, 8, 2, 5

L4: 1, 6, 7, 5
R4: 3, 8, 2, 4

next square up from 9 is 16. so, following the same proces we can ensure pairs that add up to 16 from the numbers we already have are placed into a seperate pile to get:
L1: 1, 6, 2, 4, 13, 9, 11
R1: 3, 8, 7, 5, 15, 10, 14, 12

L2: 1, 6, 2, 5, 13, 9, 12
R2: 3, 8, 7, 4, 15, 10, 14, 11

L3: 1, 6, 7, 4, 13, 14, 11
R3: 3, 8, 2, 5, 15, 10, 9, 12

L4: 1, 6, 7, 5, 13, 14, 12
R4: 3, 8, 2, 4, 15, 10, 9, 11

and there are no other pairs of number that will total 16.

next square up from 16 is 25. but we note that we already have a pair of numbers (10+15) that add up to 25 in every list. therefore n=15 is the smallest value for n to guarantee we get a pair of numbers in one of the stacks that add to make a square number.

Answer 6

Dang that's impressive! You are correct, by the way.
Congrads asnaseer, you're definitely a "real mathematician" in my opinion, even if that's not what they pay you for.

Answer 7

Here's the answer the way it was posted on my top-secret source for these problems:

The minimum value of n is 15. First, we prove that for 15 cards, the desired pair can be found. Suppose the contrary. Then the cards numbered 1 and 15 must be in different stacks, as must cards 1 and 3. Thus cards 3 and 15 are in the same stack. Therefore, cards 6 = 9 – 3 and 10 = 25 – 15 are in the other stack, which contradicts the assumption, since 6 + 10 = 16.

Now we show that 14 cards can be distributed between the two stacks such that the sum of the numbers of any two cards of the same stack is not an exact square. Here is an example: 1, 2, 4, 6, 9, 11, 13 (the first stack) and 3, 5, 7, 8, 10, 12, 14 (the second stack). For any number of cards less than 14, the cards can be distributed between the two stacks in a similar way (with the desired condition holding true).

Pretty similar to you approach as far as the second part goes :)