What is the largest possible number of cards I could have had in the box in the beginning, in the following problem?There are several cards in my box. A positive integer is written on each of the...
What is the largest possible number of cards I could have had in the box in the beginning, in the following problem?
There are several cards in my box. A positive integer is written on each of the cards so that the numbers on different cards are different. I take two cards from the box and replace them with a new card on which I write the product of the difference of the numbers on these two cards and their sum. For example, if the numbers on the two cards were 7 and 4, then the number on the new card would be (7 - 4) (7 + 4) = 33. After I repeate tthis procedure a few times, there is only one card left in the box with the number 2764 written on it. What is the largest possible number of cards I could have had in the box in the beginning?
What cards could produce 2764? We have (a+b)(a-b)=2764. Now the factors of 2764 are 1,2,4,691,1382,2764. Since 2764 is even, at least one of a+b or a-b is even; adding and subtracting b results in the same parity for a+b and a-b,(Assume a is even; if b is even then both a+b and a-b are even, if b is odd then both a+b and a-b are odd. Likewise, if a is odd then if b is odd both a+b and a-b are even and if b is even then a+b and a-b are odd), so both a+b and a-b are even. This occurs if a,b are both even or both odd. a+b is a factor of 2764 and a-b is a factor of 2764.
Try 1,2764. This results in a+b=2764,a-b=1. Solving this system yields 2a=2765 so a is not an integer.
Try 2,1382. Then a+b=1382,a-b=2==>2a=1384==>a=692,b=690. This works:(692-690)(692+690)=2764.
Try 4,691: Then a+b=691,a-b=4==>2a=695 and a is not an integer.
(1) The only possible cards to get to 2764 are 690,692.
Repeat this process for 690 and 692. In working the process you will note that the sum of the factors must be even. So 690 has no cards: the factors are 1,2,3,5,23,30,138,230,345,690. Now a+b=690,a-b=1 ==> 2a=691,a+b=345 a-b=2 ==>2a=347,a+b=230 a-b=3 ==>2a=233 etc... all resulting in noninteger a.
For 692 the factors are 1,2,4,173,346,692. The only pair of factors whose sum is even are 2 and 346. This means a+b=346 a-b=2==>2a=348==>a=174,b=172.
(2) The only possible cards for 692 are 174 and 172.
Repeating the process we find:
(3) No cards are possible for 174. The only cards for 172 are 42 and 44.
(4) There are no possible cards for 42. The cards for 44 are 10 and 12.
(5) There are no cards for 10. The cards for 12 are 2 and 4.
(6) There are no cards for 2. The cards for 4 are 2 and 0, but zero is not a positive integer.
The cards must be 2,4,10,42,174,690 -- there are 6 cards in the hat.
Check: Cards 2 and 4 yield: (4+2)(4-2)=12
The cards 10 and 12 yield: (12+10)(12-10)=44
The cards 42 and 44 yield: (44-42)(44+42)=172
The cards 172,174 yield: (174-172)(174+172)=692
The cards 690 and 692 yield: (692-690)(692+690)=2764
If you draw two cards, you replace them with one card whose value is the product of the sum and difference of the two cards. As the example in the problem shows, if you draw a 7 and a 4, you replace the two cards with one card labelled with (7+4)(7-4)=33.
Now if I find a card labelled 33, then I know it came from two cards a and b such that (a+b)(a-b)=33, or the card marked 33 was in the box originally. Thus when there is a card labelled 2764 either 2764 was the only card ever in the box, or it replaced two cards a and b such that (a+b)(a-b)=2764.
The question asked for the largest number of cards, so if the procedure can replace a card by two cards then you would do that.
Good answer mr.embizze!!
embizze, how do you know that a+b and a-b have to be factors of 2764 in the first place?
Another question from the Gauss Student Problems (Australian Mathematics Trust) set in Victoria Australia 2012 for students to work ALONE on.
Stop cheating, nickgy!