And it’s a tricky one this week. Yesterday I went shopping and picked up four items. When I got to the till, the cashier added the price of the four items together and the bill was £7.11. I then noticed that I would get exactly the same total if I were to multiply the four prices. How much did each of the items cost?
As ever, please do NOT post your answer, but do say if you have solved it and how long it took. Solution on Monday!
Advertisement
July 23, 2010 at 5:58 am |
If we allow rounding to the nearest pence, then I’ve found an answer in 3 minutes. If not, then I’m still stumped.
This is the kind of thing that people who go on Countdown do when they’re bored, isn’t it?
July 24, 2010 at 12:11 am
I was on Countdown & am bored. That’s why I start thinking about the fact that the sum and the product are in different units ($ vs $^4).
Now to work out the answer assuming pure numbers.
July 23, 2010 at 6:23 am |
I got an answer but 2 of the prices were imaginary numbers, so it might not be right!
July 23, 2010 at 7:09 am
I love imaginary numbers!!
July 23, 2010 at 7:10 am
I love imaginary numbers!! lol
July 23, 2010 at 11:40 pm
TBH it would make shopping much more interesting.
July 23, 2010 at 6:38 am |
I found this really easy so I’m not entirely sure of my answer. I used very simple algebra.
July 23, 2010 at 6:47 am |
To my embarrassment, I’ve spent 30 minutes scratching on a piece of paper and now I’m giving up in disgust.
July 23, 2010 at 6:54 am |
Wait, just double checking the question – where you say ” the same total if I were to multiple the four prices”, do you mean the product of the 4 prices is the same as the sum of the 4 prices?
July 23, 2010 at 8:04 am
Can’t find any solution that satisfy the question since the question specified that the product is “exactly the same”. I’m thinking that an exact solution possibly doesn’t exist if each item’s price have at most 2 digits after the decimal point and is a positive real number. (I’m pretty certain as I’ve gone through an exhaustive search of all possible permutations of digits…)
Found 980 solutions if rounding is permitted.
July 23, 2010 at 7:13 am |
I looked at this puzzle and thought about it for a bit- and then gave up, I’ve got holiday packing to do and my brain really isn’t working today. (Although I think I may have had a glimmer if inspiration during my musing.)
July 23, 2010 at 7:17 am |
I think I have one trivial answer in about a minute.
July 23, 2010 at 8:01 am |
I found the answer with 15 lines of programming… is there any way to solve it “manually” without inequations?
July 23, 2010 at 8:10 am |
There’s a an infinite number of solutions….
They form 2 disconnected sets on a 2d plane.
July 23, 2010 at 7:04 pm
Presumably you mean 2 connected sets, 1 disconnected set.
July 23, 2010 at 7:35 pm
There is a finite number of solutions if you assume that no items are priced in fractions of a cent.
July 23, 2010 at 11:02 pm
You’re both right.
And given other peoples comments I approached the problem completely differently and found the unique, exact solution that does not require any rounding.
July 23, 2010 at 8:34 am |
About two minutes because I had to do it in my head; the result is unique.
July 23, 2010 at 8:48 am
Unique? Why?
July 23, 2010 at 9:12 am
My bad: I misread a detail and found the answer to the wrong problem. Now I’m embarrassed but I’ll keep thinking.
July 23, 2010 at 9:04 am |
“I then noticed that I would get exactly the same [B]total[/B] if I were to multiple the four prices”
Richard you will not get a “Total”, but a “Product” by multiplying. Is it the catch?!!
July 23, 2010 at 9:07 am |
No, rounding should not be permitted (“exactly the same total”).
So no, there is NO solution. Mr. Wiseman will prove on Monday that he performed some kind of cheating. The way the problem is put, there is no solution.
With integer, if we need to have a+b+c+d = 711 and also a*b*c*d = 711, there is a no-go, because 711 = 79*3*3*1 and that’s all. This is NOT a solution whatsoever.
Besides, multiplying prices is so ambiguous. Multiplying prices in pounds with decimals CAN’T lead to 7.11. And counting in pence (as above) gives no solution either.
I hate tricky phrasing putting people on a wild goose chase…
July 23, 2010 at 9:16 am
With integer, if we need to have a+b+c+d = 711 and also a*b*c*d = 711000000
According to my calculations there is one unique set of four numbers that meets this condition.
July 23, 2010 at 9:52 am
I agree with Béranger. There is no solution as the only solution for the equation:
a+b+c+d = a*b*c*d is {1, 1, 2, 4}
and that gives a total of 8.
So unfortunately this must be a trick question involving the wording, making it so ambiguous as to be pointless.
July 23, 2010 at 10:04 am
I have a working answer which uses four numbers with only two decimal places which have the same product and total.
That said, I had to brute force it, I am not up to determining this in an algebraic fashion any more.
July 23, 2010 at 11:03 pm
What Will says is completely correct.
July 23, 2010 at 9:16 am |
@Béranger: There is no cheating – there is one actual solution, where all four prices are an exact number of pence and the multiplication works exactly.
But yes, the multiplication is done in pounds. So if you express the numbers in pence then
A+B+C+D = 711
AxBxCxD = 711000000
Which has rather more factors to try!
July 23, 2010 at 9:22 am |
No, no, no!
He said: “exactly the same total”.
Which is 711. Not 711000000.
Hence no solution OR tricky phrasing. I cannot accept “711000000 is exactly the same as 711″.
July 23, 2010 at 9:28 am
To convert to integer you are multiplying each number by 100 so you need to adjust the equations accordingly, so
a*100+b*100+c*100+d*100 = 7.11*100
a*100*b*100*c*100*d*100 = 7.11*100*100*100*100
July 23, 2010 at 9:32 am |
OK, Will, you’ve got me. But I still can’t see the solution and no, I won’t make a script to brute-force it (or would I?).
July 23, 2010 at 9:37 am
I wouldn’t know where to start with a non-bruit-force strategy
July 23, 2010 at 9:58 am |
Perhaps we should say how long our bruit-force attacks took, my c# code cracked it in 3.29 seconds, I’m sure someone can do better.
July 23, 2010 at 11:04 pm
One line in Mathematica… 10.12 seconds
July 23, 2010 at 10:48 am |
“I would get exactly the same total if I were to multiple the four prices. ”
That doesn’t sound like correct English to me. Everyone else seems to be assuming that ‘multiple’ = ‘scale or multiply with each other’. Is that correct? Seems a bit too easy if that’s the case.
July 23, 2010 at 2:40 pm
Yeah, multiple is not a verb where I come from, so I don’t understand the question in the least.
July 23, 2010 at 10:59 am |
watching you guys work it out is way more fun than actually doing it
I am wondering if some where you can still get half/penny chews…
July 23, 2010 at 11:10 am |
@Will: I also used thoroughly brutal force, also with C#.
My way took 0.09 sec to find the solution for the first time, and 1.52 sec to be happy that there were no other solutions.
July 23, 2010 at 11:29 am |
I’m throwing out the towel for now. My weirdometer is up the roof in terms of the solutions I already tried and still I don’t have any answer. My admiration for the ones that got it (sorry, but I’m not going to read anything until find something).
And out of here, I go!…
July 23, 2010 at 11:43 am |
Took me about 10 minutes to write a program that found the answer; i first made the error to look for (a*b*c*d)/1000000 == 711, instead of a*b*c*d=711000000, and got lots of wrong answers.
July 23, 2010 at 12:22 pm |
A bit of reasoning and a few minutes of trial and error win the day. Many people are being tripped up by ignoring the decimals when they multiply.
(PS: I never cared for math as a student, only going so far as geometry in high school. I managed somehow to test out of math in college. In other words, I neither know advanced math nor needed any to solve this.)
July 23, 2010 at 12:26 pm |
0.82 seconds with my Delphi code
July 23, 2010 at 12:50 pm |
1.43 seconds in Python.
July 23, 2010 at 12:57 pm |
Would the exchange rate to the only form of currency I know…us dollar….. mess with the out come? I can’t think….so I’m throwing a copy of this puzzle, paper, pen, calculator, flash light and banana juice into Richards box filled with his monkey and hope for the best…..monkey should come up with the answer!
July 26, 2010 at 3:28 am
Just checked in with the monkey….and he has failed me…..someone slipped him a bottle of tequila, a blender, ice and fruit…. all he has done is leave me a list and of all the drinks he could make with what was given him…..I may just join him in the box…….lol….
July 23, 2010 at 2:17 pm |
Unbelievable! The solution actually exists, it’s unique and in full pence!
July 23, 2010 at 2:49 pm |
Hints: one of the four prices is a multiple of 0.79. And they were all bought in a “seven-eleven” (7-11) store
July 23, 2010 at 2:57 pm |
*** Related, but simpler puzzle! ***
«When Jack went back for a late-night snack, he bought three items off the rack.
Zack rang up the snacks and said, “That would be £5.70, Jack.”
“Wait, Zack, you multiplied the prices instead of adding them!”
“Multiply, add, who cares? It still comes out the same. Pay up.”
What the hack is going on there? What were the prices of Jack’s three items?»
So yes, there are 3 prices in pounds and full pence, that added or multiplied give the same value of 5.70.
Google the first phrase for the solution, and select the 2nd result.
July 23, 2010 at 3:25 pm |
Brute force, 5 minutes to write and debug C++ code, code did take a long time to get result, several minutes, very inefficient brute force algorithm. Spent another 5 minutes on a new and improved algorithm to get results faster exploring all possible search space in 0.35 seconds. 24 identical permutations returned. First result took 0.135 seconds. Thought I’d share since other wrote code for this.
July 23, 2010 at 3:30 pm
I’d like to see the resulted code. My brute-force 7-lines code is only too slow (~1 minute?).
July 23, 2010 at 7:57 pm
I’ll post it on Monday (hopefully I remember). The number of lines of code should be close to what you have – I have some timing and std output code in there that makes it a little larger though. I won’t explain the algorithm (i.e. assumptions made – all valid though) but you should be able to figure it out from the code.
July 23, 2010 at 10:52 pm
OK, couldn’t wait, and I don’t think this will spoil the puzzle for anyone – they’d have to write and run this code to get the answer to the puzzle. Here’s my algorithm. Runs in about 0.35 seconds, this solution will generate all 24 identical permutations:
#define NUM 711
for (int i = 1; i < NUM-2; i++)
for (int j = 1; i+j < NUM-1; j++)
for (int k = 1; i+j+k < NUM; k++)
if (i*j*k*(NUM-i-j-k) == NUM * 1000000)
cout << "i = " << i << " j = " << j << " k = " << k << " l = " << NUM-i-j-k << endl;
Now, since all the permutations are all identical, do they all need to be generated? The algorithm could be reduced further by avoiding this repetition yet still covering the entire solution space. This following new solution (slightly modified from the one before) runs in 0.056 seconds:
#define NUM 711
for (int i = 1; i < NUM-2; i++)
for (int j = i; i+j < NUM-1; j++)
for (int k = j; i+j+k < NUM; k++)
if (i*j*k*(NUM-i-j-k) == NUM * 1000000)
cout << "i = " << i << " j = " << j << " k = " << k << " l = " << NUM-i-j-k << endl;
As mentioned it doesn't report all the permutations, but I do believe it covers the entire search space, with the assumption of not duplicating what has already been discovered by the algorithm
July 23, 2010 at 10:55 pm
You can get it running a LOT faster than that
Don’t want to spoil things until Monday, but I can post code then if you’re interested.
July 24, 2010 at 12:03 am
I’m interested. I don’t think it will spoil the puzzle for folks since we’re not providing the answer unless they run this code, the brute force approach has already been described and optimizing code that will get you the answer was never part of the puzzle. I think it’s OK.
July 23, 2010 at 5:35 pm |
I think my c# code is down to 0.024 seconds for a result and 0.026 to complete the search
July 23, 2010 at 7:59 pm
WoW. Impressive, I’d like to see the algorithm on Monday if you’re willing, I’ll be posting my solution then.
July 23, 2010 at 9:02 pm
It’s not that difficult if you only search values of x_n∈{x|x<711 – (3 – n) and x≥711/(4-n)} where x_0+x_1+x_2+x_3=711. The only snagging point is that I don't recall the CLR's performance being that good.
July 23, 2010 at 9:10 pm
Sorry, I meant x_n∈{x|x<711 – (3 – n) and x≥(711-∑_{i=0}^{n-1}x_i})/(4-n)}, obviously…
July 23, 2010 at 10:47 pm
Not sure I understand your description (not sure what the n in 3-n refers to?), anyhow, here’s my algorithm. Runs in about 0.35 seconds, this solution will generate all 24 permutations:
#define NUM 711
for (int i = 1; i < NUM-2; i++)
for (int j = 1; i+j < NUM-1; j++)
for (int k = 1; i+j+k < NUM; k++)
if (i*j*k*(NUM-i-j-k) == NUM * 1000000)
cout << "i = " << i << " j = " << j << " k = " << k << " l = " << NUM-i-j-k << endl;
Since all the permutations are identical, do they all need to be generated? The algorithm could be reduced further. This following new solution (slightly modified from the one before) runs in 0.056 seconds:
#define NUM 711
for (int i = 1; i < NUM-2; i++)
for (int j = i; i+j < NUM-1; j++)
for (int k = j; i+j+k < NUM; k++)
if (i*j*k*(NUM-i-j-k) == NUM * 1000000)
cout << "i = " << i << " j = " << j << " k = " << k << " l = " << NUM-i-j-k << endl;
As mentioned it doesn't report all the permutations, but I believe covers the entire search space. Not sure if this is similar to the approach you were describing.
July 23, 2010 at 11:13 pm
I believe that has roughly the same result as the method I suggested, though it does cover a significant number of permutations twice. I started from the top, rather than the bottom, which is a bit messier, but it cuts out most of the per-loop calculations and doesn’t result in multiple permutations of the (one) solution. http://pastebin.com/pbbTQ951
July 23, 2010 at 11:25 pm
A hint for improving those algorithms: once two of the values have been fixed, we have two unknowns and two equations. So no need to iterate more than two levels deep, at the expense of some math. Doing that improved my solving time at least 4x.
July 23, 2010 at 11:40 pm
@slightly_skeptical
if you are only looking for the permutation with values in ascending order then I think i need not go above NUM/4 and j need not go above (NUM-i)/3 etc
July 23, 2010 at 11:45 pm
@Kevin, I considered that, but I’d decided to keep to basic mathematics. If I were to resort to algebra, I would have gone a lot further than your suggestion.
July 24, 2010 at 12:26 am
Kris, thanks for the algorithm, very fast and elegant coding style, I clocked it at .035 seconds on my machine. I haven’t fully investigated your code, but I don’t think it’s covering the entire solution space. If you try the number 756 you will notice that some solutions are missing. For example if you use 756 instead of 711 one solution 125,125, 378, 128 is not provided by your algorithm as a valid solution. I think there are more solutions missing but one should be enough.
July 24, 2010 at 12:31 am
It’s not very clean, but here’s mine: http://pastebin.com/Ehjyt6ta
The timing stuff is mac specific but is easy enough to change.
solve4() is the optimized routine. Runs in 0.0011 seconds now on this machine.
July 24, 2010 at 12:33 am
Kris, I posted my code (the fast one) at: http://pastebin.com/qLDKp4Jf
July 24, 2010 at 12:39 am
I wouldn’t go that far… It was really quick and dirty. But you’re right. I’m really not awake enough to write this kind of thing, so I won’t gurantee that it’s 100% correct, but changing the condition to >= rather than > (as in the above equation) generates the missing result that you specified.
July 24, 2010 at 12:56 am
Kris, Perfect, that fixed it.
July 24, 2010 at 1:30 am
Kevin I just finished running through your code but it only provides one solution for the case where the value is 7.56. There are 5 unique solutions for that one. The 7.11 problem was solved in .024 seconds on this machine, very fast. Note I uncommented the printf the solution to compare apples to apples between yours, Kris’s and my solutions.
Very fast, but like I said only prints out one solution for the 7.56 problem.
Note I used floor instead of roundl since I couldn’t find it in my math.h, hopefully that didn’t screw things up.
July 24, 2010 at 1:33 am
Oops, 4 not 5 solutions.
July 24, 2010 at 1:35 am
@slightly_skeptical: That’s odd, when I run the variant that runs through every possible total, I’m seeing 4 solutions for 7.56:
The total $7.56 has 4 unique solutions
Replacing the round with a floor can indeed cause problems
For example the floating point representation of the number 1.2 could “really” be 1.1999999999. Round brings it back to the correct value, floor chops off nearly the entire integer value (floor really does nothing in this particular case because we are assigning to an integer so the compiler floors for us).
July 24, 2010 at 1:38 am
… and if you really want to compare apples to apples, I’d keep the console output suppressed and run each solver a couple hundred times at least then get an average
July 24, 2010 at 2:04 am
Kevin, perfect, the floor was the problem, changed it to floor (x+0.5) to be equivalent to roundl(x), got the 4 solutions. Your method seems the fastest, mine’s the slowest and Kris’s is in the middle. I won’t run multiple runs, pretty clear yours is faster. Thanks, and good work to both of you. Cheers.
July 24, 2010 at 2:13 am
@slightly_skeptical If you want to use floorl, you need to define _XOPEN_SOURCE=600 before you include math.h (or alternatively, depending on your compiler, set the c99 flag). You also might tweak your optimizer settings. Mine runs 4 times as fast with moderate optimization enabled.
July 23, 2010 at 5:59 pm |
I think a lot of people are thinking far too hard about this. It took me under a minute to see the answer.
July 23, 2010 at 6:15 pm |
Easy. It’s a lateral thinking, not an algebraic answer. And this is the first Friday Puzzle I’ve ever got
July 23, 2010 at 6:22 pm |
Whilst I accept that there is a typo ‘multiple’ and an error ‘total’ I cannot see what lateral thinking there can be, unless we are saying that the bill is the same, even if we multiply the numbers together, because us doing some maths does not affect the bill.
It’s a simple (or, in fact, bloody hard) algebraic problem with a single unique answer, as far as I can tell.
July 23, 2010 at 7:22 pm |
Slight typo in the wording ["multiple" instead of "multiply"], but I understand the problem and will work on it this weekend.
July 23, 2010 at 8:00 pm |
I thought I’d try out Excel’s goalseek, and it’s actually a pretty crappy method for something like this (probably why you can only use it for 1 value in the first place). Writing the code took all of about 3 minutes. Debugging it and making goalseek work right took another 5. But I’m getting multiple answers, too.
July 23, 2010 at 8:01 pm |
Ouch. Took about two hours of off and on working and the front and back of a piece of paper, but I got an answer I feel is correct
July 23, 2010 at 8:55 pm |
Allowing rounding I get 31296 solutions (well, different permutations of 1304 solutions), but I can’t find any solutions without allowing rounding, even if I do tricky things like allowing for negatively-priced items or whatever.
July 23, 2010 at 9:12 pm
Then you’ve done something wrong. Are you, by chance, using floating point numbers rather than rational integers? Remember that binary floating point can’t accurately represent every base ten decimal value.
July 23, 2010 at 9:26 pm |
Easily solved in code. Only took a minute or two for a simple coded solution, but that was slow and no fun (9.6 seconds). A simple optimization got the time down to 0.42 seconds, a non-trivial further optimization got the time down to 0.016 seconds, and a fairly complicated solution got the time down to only 0.0041 seconds (of course those times depend on the machine you’re using, but they show the different relative times of the various algorithms). This would be an interesting problem to use when teaching about algorithm optimization in computer science courses.
To those people getting multiple answers above: you’re just getting different permutations of the same set of four numbers, right? Just restrict your solutions so that a <= b <= c <= d and consider that your canonical solution. If you're still getting different solutions then I think you're doing something wrong :p
July 23, 2010 at 10:02 pm |
Just for fun I wanted to check how special £7.11 was. Checked all combinations of 4 numbers that had this property for totals between £0.00 and £10.00. There were surprisingly many of them… 105 to be precise. The smallest is £6.44, the largest £9.99. Many of the totals have multiple solutions too (the most was £8.10 with 5 solutions).
July 23, 2010 at 11:01 pm |
After some glasses of whiskey it took me five second but not sure the answer is right…
July 24, 2010 at 12:00 am |
Anyone tried the math after the removal of 17.5% VAT
July 24, 2010 at 12:13 am |
[...] It’s the Friday Puzzle! And it’s a tricky one this week. Yesterday I went shopping and picked up four items. When I got to the till, the [...] [...]
July 24, 2010 at 12:29 am |
Well, if it’s a buy 1 get 3 free deal, I have an answer.
July 24, 2010 at 3:14 am |
Got there by a very bad brute force program. I’d like to think there was a lateral thinking solution I’ve missed so I’ll be tuning in on Monday.
July 24, 2010 at 6:52 am |
I think I have it but only after another poster gave me a clue.ha ha.
July 24, 2010 at 4:50 pm |
Is it even possible for a person to figure this out? I mean, it seems like everybody who found an answer only found it because they asked a computer to do the problem for them. I don’t know any of the programming languages people are using, so does that mean this puzzle isn’t for me?
July 24, 2010 at 5:42 pm
I’ve never seen Richard post a puzzle that’s meant to be solved by computer. Some of the above posters seem to have found ‘lateral thinking’ methods, but the only way I can think of is a directed guess, check, and revise. Since that’s no fun for me, I just used the computer.
July 24, 2010 at 5:56 pm
I worked out the highest and lowest possible numbers first, then played at guess and revise for a bit. I have to say, it was a deeply unsatisfying problem and I ended up giving up on doing it by hand, it was like doing a suduko puzzle – always achievable, so long as one spends enough time trying, but no fun at all.
July 25, 2010 at 11:53 am
I initially thought of using some C++ code to let the computer guess the answer for me, but I then went after quite some thinking for an algebraical way. I still had to use a calculator for that.
My solution has a small rounding error. I am curious regarding an exact solution.
July 26, 2010 at 2:41 am
@Katie I don’t do the math genius bit myself so I think their must be more to it and I just didn’t feel up to it…..but I may just give it a try now!
And @LordManley….I love sudoku very much thank you kindly….lol…
July 26, 2010 at 3:31 am
Never mind I was right the first time…..I don’t know the answer or even where to start…..this one has the better of me…..oh well there will be more……
July 24, 2010 at 9:07 pm |
Having seen the answers from my program I’m trying to work out if I could have got to them by a satisfying lateral thinking method. And that hasn’t happened for me yet either.
Bah!
July 25, 2010 at 12:57 am
Ditto. I thought I had some clever approaches to the problem, but none of them took me all the way. Then brute-forced the answer with a computer to see if I was barking up the right tree. I wasn’t. I’m interested what Richard and some of the lateral thinkers have to say for themselves on Monday. I’ll probably be kicking myself.
July 25, 2010 at 12:29 am |
I gave up manual solving immediately and wrote a little brute force Python program to find out the answer. I have just started learning Python, so this was a perfect little programming task.
July 25, 2010 at 2:37 pm |
Had to work out the ballpark range of possible answers first which can be done pretty quickly then look at those most likely to be part of the solution (an earlier post gave a heavy clue). After I realised I’d made a stupid aassumption solved it by hand with an exact (non-rounded) solution in about 10 mins. Would love to know if there is a general principle to solving these though rather than what was effectively trial and error.
July 25, 2010 at 3:11 pm |
Okay, I still didn’t saw any other comment but I think I might quit. Serves me well for saying Richard’s puzzles has been simple. I even resort to the old pound system… to no avail. I got one solution which in one operation result is 7.11, in another is 7.12… hardly a sum exactly equal to the product. With decimal pounds, the results are worst. I’ll do a last try, but I have no hope. I believe I’m doing the things right… my trials goes now by the millions number… let’s see what cames out Monday.
July 25, 2010 at 6:23 pm |
[...] Richard Wiseman Blog [...]
July 25, 2010 at 9:30 pm |
Okay, I got it, finally, right before the Bell. Is exactly like Richard said, exact sums and products. I quit from being smart, and did an almost brute-force approach. The solution runs in only 0.08 seconds. Plus one hour for the program. Plus half a day in other stupid clever tries that got me in nothing.
July 25, 2010 at 9:49 pm
Care to post your program (pastebin, please)?
July 27, 2010 at 10:55 am
Kris, only now I saw your request. I’ll publish my code in the Monday thread.
July 27, 2010 at 10:55 am
Nice use of defines, by the way.
August 12, 2010 at 12:03 pm |
dfsfd345f
September 30, 2011 at 11:51 am |
apple ipad future…
Gran poste! Gracias por tardar la época de escribir algo que está realmente digno de la lectura. Encuentro demasiado a menudo el Info inútil y no algo que es realmente relevante. Gracias por su trabajo duro….
November 20, 2011 at 6:06 pm |
Solution please?