# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Message body

 Emoticons View more Emoticons
 [quote="DrJones"]This isn't a complete waste of time, as give you ideas you could use in other problems. Also, sciencist may be wrong. [img]/Forums/tongue.gif[/img] And is funny! [img]/Forums/biggrin.gif[/img] This formula doesn't work to all values either, only those that satisfy the following: For i:=1 to n-2 (where n is the lenght of V[i]) -> (V(i)-2V(i+1)) / V(i+2) is an integer; And the algorhytm is:
code:
After the first algorhytm, we have T[i] with the total number of coins and V[i] with its values.  For i:=1 to n-2 do    While (T(i+2)+V(i)) * V(i+2)) >= 2*V(B) do       Begin           T(i)-=1;           T(i+1)+=2;           T(i+2)+= (V(i)-2V(i+1)) / V(i+2);       End;

Why T(i+1) increases by 2? Well, that's because decreasing T(i), we obtain enough cash to increase T(i+1) and remains V(i)-V(i+1), that increase T(i+2) in V(i)-V(i+1)/V(i+2). (as V(i)>V(i+1)) But, this increase if T(i+2) could be enough to make another coin in T(i+1), so:
code:
if T(i+2)*V(i+2) >= V(i+1) then        Begin              T(i+1)+=1;               T(i+2)-= V(i+1)/V(i+2);        End;

And, when do we decide it's better to decrease T(i)? When we predict that with the remaining (V(i)-V(i+1))/V(i+2) plus the present T(i+2) we will have enough to make 2 coins in T(i+1), which at the worst case will be the same number of coins that the ones we have when started. (Ex: 1 0 1 -> 0 2 0) Let's Merge: (T(i+2)+(V(i)-V(i+1)/V(i+2))) * V(i+2) = (T(i+2)+V(i))*V(i+2) - V(i+1)
code:
If (T(i+2)+(V(i)) * V(i+2) >= 2V(i+1) then      Begin           T(i)-=1;           T(i+1)+=2;           T(i+2)+=(V(i)-2V(i+1))/V(i+2);      End;

T(i+2) could decrease this time. After all this write, I discovered that I was wrong with the election of decrease T(i), as I took always V(A)<=2V(B). So now I need to find a way to deal with both problems. [list] [*] Fix the decrease-chosing method, so it works too for every V(A)>2V(B). [*] Find a solution to the round problem. [/list] Wake up! I finished the class! [img]/Forums/tongue.gif[/img] [This message has been edited by DrJones (edited 06-20-2003 12:39 PM).][/quote]
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
 Topic review
Author Message
DrJones
Posted: Fri Jun 20, 2003 4:35 pm    Post subject: 1

This isn't a complete waste of time, as give you ideas you could use in other problems. Also, sciencist may be wrong.

And is funny!

This formula doesn't work to all values either, only those that satisfy the following:

For i:=1 to n-2 (where n is the lenght of V[i]) -> (V(i)-2V(i+1)) / V(i+2) is an integer;

And the algorhytm is:
code:

After the first algorhytm, we have T[i] with the total number of coins and V[i] with its values.

For i:=1 to n-2 do
While (T(i+2)+V(i)) * V(i+2)) >= 2*V(B) do
Begin
T(i)-=1;
T(i+1)+=2;
T(i+2)+= (V(i)-2V(i+1)) / V(i+2);
End;

Why T(i+1) increases by 2? Well, that's because decreasing T(i), we obtain enough cash to increase T(i+1) and remains V(i)-V(i+1), that increase T(i+2) in V(i)-V(i+1)/V(i+2). (as V(i)>V(i+1))

But, this increase if T(i+2) could be enough to make another coin in T(i+1), so:
code:

if T(i+2)*V(i+2) >= V(i+1) then
Begin
T(i+1)+=1;
T(i+2)-= V(i+1)/V(i+2);
End;

And, when do we decide it's better to decrease T(i)? When we predict that with the remaining (V(i)-V(i+1))/V(i+2) plus the present T(i+2) we will have enough to make 2 coins in T(i+1), which at the worst case will be the same number of coins that the ones we have when started. (Ex: 1 0 1 -> 0 2 0)

Let's Merge:

(T(i+2)+(V(i)-V(i+1)/V(i+2))) * V(i+2) = (T(i+2)+V(i))*V(i+2) - V(i+1)

code:

If (T(i+2)+(V(i)) * V(i+2) >= 2V(i+1) then
Begin
T(i)-=1;
T(i+1)+=2;
T(i+2)+=(V(i)-2V(i+1))/V(i+2);
End;

T(i+2) could decrease this time.

After all this write, I discovered that I was wrong with the election of decrease T(i), as I took always V(A)<=2V(B). So now I need to find a way to deal with both problems.

• Fix the decrease-chosing method, so it works too for every V(A)>2V(B).
• Find a solution to the round problem.

Wake up! I finished the class!

[This message has been edited by DrJones (edited 06-20-2003 12:39 PM).]
Bicho the Inhaler
Posted: Fri Jun 20, 2003 12:27 pm    Post subject: 0

Try PSPACE-complete problems. It can be frustrating, let me tell you. Nevertheless, there's quite a bit of research going into algorithms of PSPACE-complete problems. Anyway, more power to you, dude!

*Goes off to work on quantified Boolean formulas*
DrJones
Posted: Fri Jun 20, 2003 12:14 pm    Post subject: -1

I enjoy wasting my time from time to time trying to solve problems with NP complex algorhytms in a polinomial time. These problems haven't algorhytms that solve them in polinomial time, of course.

One of them is "The Money Exchange Problem":

«We have a list with values in decreasing order, and we also have an endless amount of coins (first unsolvable problem) of each value. Find an algorhytm that, with an initial amount, returns the minimal number of coins needed to reach that amount.»

• This problem is unsolvable if not every amount is achievable with the list of values.
• The simplest algorhytm:
code:

- V: Array with values A, B, C, D... with A>B>C>D...
- Amount: X
- V[i] -> Value of the 'i' Position in the list.
- T[i] -> Number of coins of the 'i' value;
- For i=1 to End -> T[i]:=(X div V[i]);
X:=X-(T[i] * V[i]);

Doesn't work for all lists of values. As an example -> X = 180, works with V = 100 50 25 10 5 2 1. (1 1 1 0 1 0 0)
But not with V = 100 90 1. (1 0 80, instead of 0 2 0)

I made a "Fixer" algorhytm to use after the first one, but also has a round problem that need solve. I will post it after a break.

(To be Continued)

------------------

[This message has been edited by DrJones (edited 06-20-2003 08:16 AM).]