8 replies to this topic

[Mark]

In a shop there is on sale:

fish for $203.02 each
Cacti for $301.09 each
and Apples for $107.04 each

I spend $2752.57 at the store.

how many items of each did i buy?

note: I can only buy a whole number of items.

and tell me how you arrived at your conclusion?

also, is there multiple solutions?

Edited by Mark, 08 August 2010 - 12:07 AM.

[arunma]

Thinking out loud...

You've got 203.02x + 301.09y + 107.04z = 2752.57

Seems like a multivariate problem. I guess I could just start taking every combination of ordered triplets (x,y,z) and then find one that gives 2752.57. But that'd be the cheating way. I wonder if there's an easier solution.

[Crimson Lego]

I call it trial and error.



Is there a certain equation or formula that can be used to solve this?

[Egann]

I call it trial and error.



Is there a certain equation or formula that can be used to solve this?

You CAN use substitution or elimination to write all the variables in terms of each other, but in the end you still have to break up a number by trial and error. A smaller number (because it's a multiple for the variables) but still trial and error.

Me? Oh, I'm too lazy at the moment to crunch it out. In a minute.

[Showsni]

I hate these kind of questions. I still haven't bothered to work out that one on xkcd.

Though, there is a webpage where several people have shown the programmes they used for that xkcd one:

http://stackoverflow.com/questions/141779/solving-the-np-complete-problem-in-xkcd

obviously any of them could easily be adapted for your question, if we had a compiler. Or we could try it in our heads; but if we're going to use trial and error, writing a programme to do it for us seems the sanest way.

If you're looking for a general solution, I should imagine you're out of luck... Wikipedia says

Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a result, the time required to solve even moderately large versions of many of these problems easily reaches into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or not it is possible to solve these problems quickly is one of the principal unsolved problems in computer science today.

[Mark]

Hint:

if in the shop there were, apples costing $1,000,000, bananas costing $1,000, and pineapples costing $1.
if I spent $1,001,001 (and providing I buy less than 10 of each item) then it would be pretty obvious how many of each item i bought... right?...

Edited by Mark, 09 August 2010 - 08:55 AM.

[Mark]

I hate these kind of questions. I still haven't bothered to work out that one on xkcd.

Though, there is a webpage where several people have shown the programmes they used for that xkcd one:

http://stackoverflow.com/questions/141779/solving-the-np-complete-problem-in-xkcd

obviously any of them could easily be adapted for your question, if we had a compiler. Or we could try it in our heads; but if we're going to use trial and error, writing a programme to do it for us seems the sanest way.

If you're looking for a general solution, I should imagine you're out of luck... Wikipedia says

Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a result, the time required to solve even moderately large versions of many of these problems easily reaches into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or not it is possible to solve these problems quickly is one of the principal unsolved problems in computer science today.

yay, so I thought I would make my own C program to do the XKCD one:

#include <stdio.h>

int main(int argc, char *argv[]) {
	int a, b, c, d, e, f;
	
	int val = 1505;
	
	for (a = 0; a < 10; a++)
		for (b = 0; b < 10; b++)
			for (c = 0; c < 10; c++)
				for (d = 0; d < 10; d++)
					for (e = 0; e < 10; e++)
						for (f = 0; f < 10; f++)
							if (215*a + 275*b + 335*c + 355*d + 420*e + 580*f == val)
								printf("%i, %i, %i, %i, %i, %i\n", a, b, c, d, e, f);

	printf("done\n");
	return 0;
}

also, I can assure you that there is at least one solution to my problem that can be reasonably solved without recourse to computer guesswork.


and if you REALLY give in, here is the corresponding program to guess the solution for mine:

#include <stdio.h>

int main(int argc, char *argv[]) {
	int a, b, c;
	
	int val = 275257;
	
	for (a = 0; a < 20; a++)
		for (b = 0; b < 20; b++)
			for (c = 0; c < 20; c++)
				if (20302*a + 30109*b + 10704*c == val)
					printf("%i, %i, %i\n", a, b, c);

	printf("done\n");
	return 0;
}

Edited by Mark, 09 August 2010 - 08:46 AM.

[Mark]

OK, another hint:

if I am in a shop and there is apples for $2,001,001, bananas for $1,002,000 and pinapples for $1.

if I spend $5,004,003 and I buy less than 10 of each item then...


I must have bought 2 apples, 1 banana, and 1 pineapple. yes?

Edited by Mark, 11 August 2010 - 10:48 AM.

[Mark]

gee...

oh well.

fish for $203.02 each
Cacti for $301.09 each
and Apples for $107.04 each

I spend $2752.57 at the store.

how many items of each did i buy?

Ok, if i break the prices down into hundreds, ones and cents, and assume there is no overflow then.
If F is the number of fish that I buy, C is the number of Cacti, A is number of apples, then I can say that:

2*F + 3*C + 1*A = 27.
3*F + 1*C + 7*A = 52.
2*F + 9*C + 4*A = 57.

which you can solve however you like, I solved it as a matrix equation:

| 2 3 1 | | F | = | 27 |
| 3 1 7 | | C | = | 52 |
| 2 9 4 | | A | = | 57 |


(trying to draw matrices on this forum sucks!)

yeilding F = 7, C = 3, A = 4.

I kind of expected someone to see that. oh well.

leads me to wonder if this method could be generalized, perhaps even to the xkcd question...





Ok, so just some stream of consciousness math,
how could this kind of problem be solved analytically?
here is an idea:
lets assume that I can buy fractions of each item, ie. that the solutions can belong to the real numbers.
so if the there are 3 kinds of items that I can buy, and their sum must add to certain X, then the solutions space for the problem must be 2-dimensional.
lets assign an analytic function f(p, a) such that for each point on 3D space p and parameter a, as limit a -> infinity, then f(p, a) = 1 if and only if point p belongs to the solution space, otherwise zero.
if we have another analytic function g(p, b) such that as b-> infinity then it converges to the 3D dirac comb (such that each peak lies on respective whole numbers - and peaks exist only in the positive quadrant).
if we take f times g and multiply it by some kind of normalizing function, and then take a and b to infinity, then we should be left with a function equivilant to a dirac spike on the realistic solution. (or - if there are many solutions - then many dirac spikes scaled down by the number of them)
if there is a single solution then we could integrate x times the function over all space, to get the x coordinate of the solution (ditto for y and z).

- I have NO idea if this technique is even capable of giving analytical solutions... perhaps..., but even if it does give analytic solutions then i would have to presume the kind of math behind it would make it a TOTALLY impractical mongrel.

Edited by Mark, 16 August 2010 - 11:17 AM.