Author |
Topic: 7-11 Riddle (Read 9370 times) |
|
Jimmy Hansen
Guest
|
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
|
|
IP Logged |
|
|
|
Jimmy Hansen
Guest
|
Oops, it's FOUR items, sorry.
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
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).
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
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.
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
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.
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: 7-11 Riddle
« Reply #5 on: Sep 12th, 2002, 1:21pm » |
Quote Modify
|
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*1004 = 711,000,000 and whose sum is 7.11*100 = 711. Still working...
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
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.
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
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.
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: 7-11 Riddle
« Reply #8 on: Sep 12th, 2002, 2:52pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: 7-11 Riddle
« Reply #9 on: Sep 12th, 2002, 2:53pm » |
Quote Modify
|
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); } } } }
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 7-11 Riddle
« Reply #11 on: Aug 25th, 2003, 6:06am » |
Quote Modify
|
factoring 7.11*100^4 gives 26 * 32 * 56 * 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 53 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.
|
« Last Edit: Aug 25th, 2003, 2:56pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|