wu :: forums - Print Page


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

        riddles >> cs >> 7-11 Riddle
        
(Message started by: Jimmy Hansen on Sep 11^th, 2002, 7:52pm)

Title: 7-11 Riddle
Post by Jimmy Hansen on Sep 11^th, 2002, 7:52pm

You go to a 7-11 convenience store. You bring three items to the counter, and the cashier tells you your total is $7.11. You reply, "That's odd, how did you come to that value?" The cashier replies, "I multiplied your items!" and you respond, "You're not supposed to MULTIPLY them, you're supposed to ADD them!" He smiles and replies, "It would have been the same either way." What were the prices of the three items?

Solving it in code is easy -- solving it QUICKLY is the challenge! Post your CPU speed + time it took if your code to find it. :)

Credit the riddle to Jay Cotton

Title: Re: 7-11 Riddle
Post by Jimmy Hansen on Sep 11^th, 2002, 7:56pm

Oops, it's FOUR items, sorry.

Title: Re: 7-11 Riddle
Post by Yournamehere on Sep 12^th, 2002, 12:42pm

Why does one need to use code to solve this? One could do this just as easily with a hand calculator.

If one item's price is a, then 7.11-a = 7.11/a. Rearranging yields

a^2 -7.11 a +7.11 = 0

Solve this using the quadratic formula gives a. So now you have three items which both sum to 7.11-a and whose product is the same. Apply the same technique to get another item's price, and repeat again.

If you insist on using a computer, here is a Perl program that does this:

#! /usr/bin/perl

sub quad {my $n=shift; return ($n-sqrt($n*$n-4*$n))/2;}
sub round_quad {return int(quad(shift)*100+0.5)/100;}

$t = 7.11;
$a = round_quad($t);
$t -= $a;
$b = round_quad($t);
$t -= $b;
$c = round_quad($t);
$t -= $c;
$d = $t;

print "a=$a, b=$b, c=$c, d=$d\n";

The output is

a=1.2, b=1.28, c=1.46, d=3.17

The execution time is instantaneous (0.01 seconds on a machine with a 0.01 second clock resolution).

Title: Re: 7-11 Riddle
Post by Yournamehere on Sep 12^th, 2002, 1:13pm

I omitted this critical note in the last reply:

Any solution to the system

a+b+c+d = 7.11
abcd = 7.11

is also a solution of the system

a+b+c+d = 7.11
abcd = 7.11
bcd = b+c+d
cd = c+d

since the latter simply has more constraints. Thus we solve the latter system as our goal instead.

Title: Re: 7-11 Riddle
Post by Yournamehere on Sep 12^th, 2002, 1:16pm

Goofed once more: here is what I meant to say:

Any solution to the system

a+b+c+d = 7.11
abcd = 7.11
bcd = b+c+d
cd = c+d

is also a solution of the system

a+b+c+d = 7.11
abcd = 7.11

since the former simply has more constraints. Thus we solve the former system as our goal instead.

Terribly sorry for all the mistakes.

Title: Re: 7-11 Riddle
Post by S. Owen on Sep 12^th, 2002, 1:21pm

It doesn't necessarily follow that bcd = b+c+d, just because abcd = a+b+c+d. But like you say, assuming that it does, you can arrive at an approximate answer. That may be as close as one can get... I can't yet find an exact answer.

I was thinking along these lines:

To make things easier, multiply everything by 100. We are looking for integers a, b, c and d whose product is 7.11*100⁴ = 711,000,000 and whose sum is 7.11*100 = 711.

Still working...

Title: Re: 7-11 Riddle
Post by Yournamehere on Sep 12^th, 2002, 1:54pm

Here is a program (again Perl) which searches for an exact solution. Its style is basically brute force: try all values of a,b,c,d until it finds a match. Inner loops are skipped when it tries some item's price which is not a divisor of the "target price".

#! /usr/bin/perl

foreach $a (1..711) {
$m = 711*100*100*100;
next if ($m % $a);
$m /= $a;
foreach $b (1..711-$a) {
next if ($m % $b);
$m /= $b;
foreach $c (1..711-$a-$b) {
next if ($m % $c);
$m /= $c;
$d = 711-$a-$b-$c;
if ($d == $m) {
print "a=$a, b=$b, c=$c, d=$d\n";
exit;
}
}
}
}
print "none found\n";

This program returns "none found", which indicates no exact solution exists.

Title: Re: 7-11 Riddle
Post by Yournamehere on Sep 12^th, 2002, 2:00pm

Today is not my day: the posted program contains a few bugs. Here is a modified program:

#! /usr/bin/perl

foreach $a (1..711) {
$m1 = 711*100*100*100;
next if ($m1 % $a);
foreach $b (1..711-$a) {
$m2 = $m1 / $a;
next if ($m2 % $b);
foreach $c (1..711-$a-$b) {
$m3 = $m2 / $b;
next if ($m3 % $c);
$d = 711-$a-$b-$c;
$m4 = $m3 / $c;
if ($d == $m4) {
print "a=$a, b=$b, c=$c, d=$d\n";
exit;
}
}
}
}
print "none found\n";

This one does return a solution:

a=120, b=125, c=150, d=316

in under 2 seconds on a P-III 500 Mhz machine.

Title: Re: 7-11 Riddle
Post by S. Owen on Sep 12^th, 2002, 2:52pm

Yeah, that's what I got too... you can optimize a little further by noting that one of the numbers must be divisible by 79... so I just considered multiples of 79 for a.

I take back what I said in my last post, having read your others. Yeah I see why you have assumed bcd=b+c+d and I agree with your arguments. Assuming that does in fact lead you to a non-exact solution, though it can't lead you to the exact one in this case, that's what I meant to say.

Title: Re: 7-11 Riddle
Post by S. Owen on Sep 12^th, 2002, 2:53pm

My Java program...

for(int a=79; a<711; a+=79)
{
int maxB = 711-a;
for(int b=1; b<maxB; b++)
{
int maxC = maxB-b;
for(int c=1; c<maxC; c++)
{
int d = maxC-c;
if(a*b*c*d == 711000000)
{
System.out.println(a+" "+b+" "+c+" "+d);
}
}
}
}

Title: Re: 7-11 Riddle
Post by william wu on Sep 14^th, 2002, 12:24pm

Yournamehere: if you register you can modify your own posts to correct errors; might be helpful :)

Title: Re: 7-11 Riddle
Post by towr on Aug 25^th, 2003, 6:06am

factoring 7.11*100^4 gives 2⁶ * 3² * 5⁶ * 79
So taking the first number as a multiple of 79, it can at most be 4*79, because else you can no longer get 7.11 *100^4.
So we have 6 factors of 5 left for the last three numbers. Which means one of them has at least two 5's, that means it's a multiple of 25. It can't have more than four 5's so there are two left.
Thus another number is left that has at least one factor 5. [e]There is at most a factor 5³ in a number, so there is another one which has at least a factor 25 as well[/e]

These three changes can speed the algorithm up to where only a maximum of ~~4102~~[e]789[/e] calculations are needed. Which is even manageable on paper.