wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Transitive Discounts
        
(Message started by: THUDandBLUNDER on Feb 23^rd, 2005, 9:54am)

Title: Transitive Discounts
Post by THUDandBLUNDER on Feb 23^rd, 2005, 9:54am

You need to buy three items from a store. With your discount coupons an item selling for $x is discounted at y%, an item selling for $y is discounted at z%, and an item selling for $z is discounted at x%. If the total discount percentage is equal to the square root of the total of the original prices, and x,y,z are positive integers with x < y < z, find the values of x, y, and z.

Title: Re: Transitive Discounts
Post by markr on Feb 23^rd, 2005, 11:28pm

(xy+yz+zx) = (x+y+z)^(3/2)
So,
x,y,z are all even or all odd
xy+yz+zx is a cube
x+y+z is a square between 9 and 294, inclusive (there are only 15)

I got the answer in about 5 minutes, using a spreadsheet for trial and error, but that wouldn't cut it on the exam. Curious to see the pure math solution.

Borrowing an idea from somebody else, the answer is in the first n<7 digits to the right of the decimal of 1/0.13597856.

Title: Re: Transitive Discounts
Post by towr on Feb 23^rd, 2005, 11:39pm

on 02/23/05 at 23:28:38, markr wrote:

(xy+yz+zx) = (x+y+z)^(3/2)

Why ^(3/2) ?
And where did the 'percentage' go?
I was thinking more along the lines of (xy+yz+zx)/100 = (x+y+z)^(1/2)

Title: Re: Transitive Discounts
Post by markr on Feb 23^rd, 2005, 11:57pm

x, y, z are integer percentages (as well as prices). As discounts, they need to be divided by 100, and the total discount needs to be multiplied by 100 to make it an integer percentage. Therefore, you have:
[(xy/100 + yz/100 + zx/100) / (x+y+z)] * 100 = (x+y+z)^(1/2)
Cancel out the 100s, and multiply by (x+y+z) to get my original equation.

Title: Re: Transitive Discounts
Post by Grimbal on Feb 24^th, 2005, 2:29am

on 02/23/05 at 23:28:38, markr wrote:

x,y,z are all even or all odd

You can even show that if they are all multiples of 2, they must also be multiples of 4, 8, etc... So, either they are all 0 or they are all odd.

Title: Re: Transitive Discounts
Post by towr on Feb 24^th, 2005, 6:31am

on 02/23/05 at 23:57:00, markr wrote:

Ah, you're right.. I read the question wrong..

Title: Re: Transitive Discounts
Post by Deedlit on Mar 30^th, 2005, 10:04am

Grimbal: how do you prove that if x,y,z are even, then they are all divisible by 16? I was only able to show that that the maximum power of 2 that divides them all is divisible by 3.

Here is a somewhat "purer" solution than markr's:

[hide]

First, let me prove my assertion above. If exactly one or two of x, y, and z are even, then the function (x+y+z)^3/2 - (xy + xz + yz) will be odd. So they are all odd or all even. If they are all even, let 2^i be the largest power of two that divides all three of x,y,z. Since 2^2i divides (xy + xz + yz), it must divide (x+y+z)^3/2, so x+y+z is divisible by 2^(4i/3), hence by 2^(i+1). Thus either one or three of x,y,z are divisible by 2^(i+1). It can't be three by our definition of i, so it's one. Then (xy + xz + yz) has exactly 2i factors of two, so x+y+z has exactly 4i/3 factors of two, so i is divisible by three. In particular, x,y,z are all odd or divisible by 8.

Let c = x+y. Then xy >= c-1, so

(x+y+z)^3/2 - (xy + xz + yz) <= (c+z)^3/2 - (cz + c - 1) = f(c,z)

Note that f(c,z) is a convex function of both c and z. Therefore, the maximum value of f in the region [12,99] x [11,99] is attained at one of the corners. Checking f(12,11), f(12,99), f(99,11) and f(99,99), we see that they are all negative, so f is negative in the entire region [12,99] x [11,99]. It follows that either x + y < 12 or c < 11.

Since x, y, and z are either all odd or divisible by four, and the latter can't occur given the previous restrictions, we have the seven cases (x,y) = (1,3), (1,5), (1,7), (1,9), (3,5), (3,7), and (5,7).

Using the rational root theorem for (x+y+z)³ - (xy+yz+xz)², we have that z divides (x+y)³ - (xy)² = g(x,y). Examining all cases:

g(1,3) = 55 = 5*11.
g(1,5) = 191, which is prime.
g(3,5) = 287 = 7*41.
g(1,7) = 463, which is prime.
g(3,7) = 559 = 13*43.
g(1,9) = 919, which is prime.
g(5,7) = 503, which is prime.

The only valid cases with x+y+z a perfect square are (1,3,5) and (3,5,41), and the first doesn't work. So (3,5,41) is the only solution.

Note if we don't require distinct values, we need to check a few more cases, and get (3,3,3) as the other possible solution.

[/hide]

Still a bit number-cruchy for math contest, but nothing impossible, I guess...

Title: Re: Transitive Discounts
Post by Grimbal on Mar 30^th, 2005, 1:58pm

on 03/30/05 at 10:04:34, Deedlit wrote:

Grimbal: how do you prove that if x,y,z are even, then they are all divisible by 16? I was only able to show that that the maximum power of 2 that divides them all is divisible by 3.

Hm... I checked what I did and indeed, it was not quite correct... :-[

Title: Re: Transitive Discounts
Post by Barukh on Mar 31^st, 2005, 12:13am

Masterly done, Deedlit! :D

As for my taste, it satisfies the standard of being mathematical proof.