• 0

Couple Candy Shopping

Question

Posted · Report post

  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?
-1

Share this post


Link to post
Share on other sites

2 answers to this question

  • 0

Posted · Report post

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

2-y2 = (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. {(x1+y1),(x1-y1)} = {(x2+y2),(x2-y2)}. We have two cases:

  1. x1+y1 = x2+y2 and x1-y1 = x2-y2. Add the equations to get 2x1 = 2x2, which implies x1 = x2 contradicting the requirement of each number being different.
  2. x1+y1 = x2-y2 and x1-y1 = x2+y2. Subtract the equations to get 2y2 = -2y2, which implies y2 = 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 2M+1*3, where M is the number of couples. The total number of candies bought is sum(i from 1 to M)(max(2i, 2M+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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

Nicely done Rainman!

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

I dabbled with variations on xn 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.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.