Couple Candy Shopping

[BMAD]

1. Three couples bought candy at a candy store. Each person paid as many cents per candy as pieces of candy he or she bought, and everyone bought a different number of pieces (no one was empty handed.) When they compared their bills, they found that the difference between the amounts paid by each husband and wife was the same. What is the smallest number of candies purchased? Show the amounts for the difference and for each person/couple.
2. What if there were two couples?
3. Four couples?
4. Five couples?
5. Can a method be extended for M couples?
6. If the difference between each husband's and wife's amount is less than 500 cents, what was the largest number of couples possible in the store?

[Rainman]

Let x be the number of candies purchased by a wife, and y the number of candies purchased by a husband. Assume WLOG that the wife always purchased more. The difference is x

²-y² = (x+y)(x-y) cents. Thus each couple yields a factorization of the difference.

Lemma: No two couples can yield the same factorization.

Proof: Suppose two couples did yield the same factorization, i.e. {(x₁+y₁),(x₁-y₁)} = {(x₂+y₂),(x₂-y₂)}. We have two cases:

1. x₁+y₁ = x₂+y₂ and x₁-y₁ = x₂-y₂. Add the equations to get 2x₁ = 2x₂, which implies x₁ = x₂ contradicting the requirement of each number being different.
2. x₁+y₁ = x₂-y₂ and x₁-y₁ = x₂+y₂. Subtract the equations to get 2y₂ = -2y₂, which implies y₂ = 0 contradicting the requirement of no one being empty handed.

So there must be a unique factorization for each couple. Furthermore, the factors (x+y) and (x-y) must have the same parity, as the difference is 2y and y is an integer. So for example, 3*8 would not be a valid factorization of 24. Square factorizations are also invalid, as they would imply y=0.

Note that we are trying to minimize the number of candies bought (x+y), not the difference in cost (x+y)(x-y). If we were trying to minimize the difference, we could have a difference of 45 which can be expressed as 1*45, 3*15, or 5*9. The number of candies bought would be 45+15+9 = 69. A better solution is a difference of 48, which can be expressed as 2*24, 4*12, or 6*8. The number of candies bought is 24+12+8 = 44.

Expressely, we have one couple buying 13+11 candies, another couple buying 8+4 candies, and another buying 7+1 candies.

For two couples, if we were trying to minimize the difference, we could have a difference of 15 which can be expressed as 1*15 or 3*5. The number of candies bought would be 15+5 = 20. A better solution is a difference of 24, which can be expressed as 2*12 or 4*6. The number of candies bought would be 12+6 = 18.

Expressely, we have one couple buying 7+5 candies and the other buying 5+1 candies.

For four or more couples, minimizing number of candies bought coincides with minimizing the difference. We should have a difference of 2^M+1*3, where M is the number of couples. The total number of candies bought is sum(i from 1 to M)(max(2ⁱ, 2^M+1-i*3)).

For six couples, the minimum difference is 384. For seven couples, the minimum difference is 768. So the answer to question 6 is 6.

[dgreening]

Nicely done Rainman!

The break through was coming up with (x + y) (x - y)!

I dabbled with variations on xⁿ but found that too many of the combinations yielded a zero. So I came to the same conclusion that you had to add another prime number to the mix and that 3 yielded the lowest results.

Interesting puzzle, nice elegant solution.