Author |
Topic: n cards (Read 553 times) |
|
BNC
Uberpuzzler
Gender: 
Posts: 1732
|
I wrote the first n integers (1..n) on n cards (1 number per card). Now, if I split these n cards into two piles, no matter how, I can find in at least one pile two numbers whose sum is a square.
What is the minimal number of cards I have?
|
|
 IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Speaker
Uberpuzzler
Gender:
Posts: 1118
|
 |
Re: n cards
« Reply #1 on: Apr 14th, 2003, 5:26pm » |
 Quote  Modify
|
I don't have the math skills to answer these usually. But, never pass up a chance to join in the fracus.
First, if you divide the cards in to two piles in any way, you could make one pile consisting of one card. In which case there are no two cards that sum to a square.
Second, if you divide the cards... Sorry no second, I told you. 
Maybe there isn't even a first.
How about 5
|
|
IP Logged |
They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety. <Ben Franklin>
|
|
|
cho
Guest
|
I misread this puzzle several times and wasted time solving different puzzles before I realized what I was supposed to be doing. I would answer:15: the numbers 1,3,6,10, and 15 won't fit in 2 piles without a square sum.
As for the puzzles I worked on first:
Divide the cards evenly into 2 piles so that both piles must have at least one combination of 2 or more cards adding up to a square.
Then I realized that only 2 card combinations counted, so I worked on that one awhile (but hadn't solved it yet), before I realized that a square sum in either pile would count (not both).
Your puzzle was a lot easier than the ones I wasted all that time on.
|
|
IP Logged |
|
|
|
Boody
Newbie
Gender:
Posts: 42
|
|
Re: n cards
« Reply #3 on: Apr 16th, 2003, 5:36am » |
Quote Modify
|
on Apr 14th, 2003, 5:26pm, Speaker wrote:I don't have the math skills to answer these usually. But, never pass up a chance to join in the fracus.
First, if you divide the cards in to two piles in any way, you could make one pile consisting of one card. In which case there are no two cards that sum to a square.
How about 5 |
|
Do we have to, really, assume that there is always at least two cards in deck ?
I think that a single card deck is not contracditory with the riddle.
n=5 doesn't work
I split like this:
deck one:
1, 2, 4
deck two:
3, 5
|
|
IP Logged |
|
|
|
Boody
Newbie
Gender:
Posts: 42
|
|
Re: n cards
« Reply #4 on: Apr 16th, 2003, 9:14am » |
Quote Modify
|
I tried this:
Assume we find 3 integers x, y, z for witch both of them had a sum equal to a square.
0<x<y<z.
x+y = R^2
x+z = S^2
y+z = T^2
There was always at least two of them in the same deck.
then we got a solution with n = z cards (perhaps not optimal).
Brut force for find this 3 numbers:
[ hide ]
square = 4 9 16 25 36 49 64 81 ...
Try x=2 : y, z should be within 7 14 23 34 47 62 79 ...
Is there a least one couple of it, which sum makes square ?
34 + 47 = 81 ok
So 2, 34, 47 make the deal.
[ /hide ]
This not an evidence of being the optimal solution but
we know that with n=47 cards it works.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: n cards
« Reply #5 on: Apr 16th, 2003, 10:40am » |
Quote Modify
|
The best I can find that way (with three numbers) is 6, 19, 30 (simple brute force)
But using all numbers, cho's answer is optimal..
|
| « Last Edit: Apr 16th, 2003, 11:39am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Boody
Newbie
Gender:
Posts: 42
|
|
Re: n cards
« Reply #6 on: Apr 16th, 2003, 5:43pm » |
Quote Modify
|
on Apr 16th, 2003, 10:40am, towr wrote:The best I can find that way (with three numbers) is hidden text (simple brute force)
But using all numbers, cho's answer is optimal.. |
|
my solution is poor solution.
I didn't saw the hidden text of cho, before you make me noticed it.
But what is the explanation to find his solution ?
|
| « Last Edit: Apr 16th, 2003, 5:44pm by Boody » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: n cards
« Reply #7 on: Apr 16th, 2003, 11:44pm » |
Quote Modify
|
Well, you can find it simply by tring to divide n numbers into 2 piles in every way and check if either pile has two numbers that sum to a square. A computer program can do that quite fast.
Validating that his is the correct answer is very simple by just trying all 32 way's the numbers can be divided over two piles (actually 16 is enough, since the two piles are symmetrical, everything in one pile isn't in the other and vice versa)
Also, if you look at the numbers themselves, they have a certain property taken together, which may lead you to find them even without brute force computer techniques..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
cho
Guest
|
I just started with 1 and grouped numbers that couldn't go together. 1 couldn't go with 3, which couldn't go with 13 or 6, which couldn't go with 10. 2,7,9 is a group. 4,5,11,12, which can't go with 13 so this group merges with group one. Within each group you keep the numbers in 2 piles. At 15, it couldn't go in either pile.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove