This is a problem that I've seen used in a movie about math students and a professor beating Las Vegas at blackjack.
And if you like Canadian movies, there is a very similar movie called The Last Casino. (I think that the last casino is > 21)
IMDB says Last Casino = 7.2, 21 = 6.7, ( 7.2 > 6.7 ) so I conclude that this is strictly true. If you were in the group of students that Prof Heap assigned a movie to watch, you might want to try one of these or make it a double feature dvd microwave popcorn stay at home and sit on the couch night. Already, I'm digressing.
The problem is described something like this: (Once upon a time)
You are a contestant on a game show where there are 3 doors. (You are always choosing doors in these questions!) They are named (aptly) door#1, door#2, and door#3.
Behind one of the doors is a Prize. But you don't know which door. And there isn't a knight or knave to be found. so you have to guess.
If it is an American game show, then you might win a car.
If it is a Canadian game show then some sort of foldable magazine rack and some Rice a Roni. (The San Francisco Treat?) Actually my Grandfather once won a couch on Definition when I was quite small. This was better than the foldable magazine rack. Too bad he already had a couch. Oh well. I digress again. Let us play super-pretend and imagine that this is an American game show with the better prizes and the gorgeously gesturing spokesmodels.
Ok To recap: there's 3 doors one door has a prize, and the other 2 don't. You have to guess. People in the audience shout numbers at you. You can't phone a friend, and all of your lifelines are used up.
You pick door #2, since it is even (n=2k) and you don't like odd people or numbers. (n=2k+1) (Its just that pesky +1 you just don't like.)
Then the super-suave game show host, says that he'll reveal to you what is behind one of the two doors that you didn't pick. Thanks a lot buddy, you think. Thanks a lot. Way to go making me feel bad. On Cable TV no less. Everyone is watching. I hope it isn't the car. I hope it isn't the car. Then I might still have a chance.
Invariably, the door he shows doesn't have the new car and the trip to Tahiti with the spokesmodel, but instead a mule and oxcart with a hearty load of stale green bacon fat. Now you are given the option to stay with your door #2 or pick the other door that the host didn't open.
Now, if you're an emotional and sentimental person, you'd stick with door #2. (We'll always have Paris!) Since you've valiantly taken CSC 165, you've become a hard and cold logician. With your steely eyes and heart of pure silicon, you coldly calculate your options. Lets see . . . 3 doors. I pick one. Prize has a 1/3 chance of being behind each door, so it doesn't matter which door I choose.
"I'll stick with door #2 Alex. That's my final answer."
Cue the sad music. (Wah Wah Wah.) You just won the wall clock from LM121. (What time is it? twenty after six!) Ah you say, I knew it was rigged. I never win at anything! (I once won a skateboard, but I lost it)
Counter-intuitively, the best strategy in this problem is to ALWAYS switch doors.
If you pick door #1, and The host reveals door #2, then switch to door #3.
More often than not you will win with this strategy, and not because the spokesmodel is quickly driving the car from door #1 to door #3. (That would be cheating)
The correct explanation, as I understand it is to partition the set of doors into 2 sets. Not 3 as you'd imagine.
set you picked = 1/3
set you didn't pick 1/3 + 1/3 = 2/3
When the host opens one of the doors you didn't pick, the probability of the prize being in the set that you didn't pick is still 2/3 and not 1/3.
At first glance this seems unlikely. Impossible even. Try it again, but with a far longer (and more boring) game show where you pick a door, and then the host opens 998/1000 doors and then asks you to stay or switch.
Of course you switch!
in this case your original door is worth 1/1000
and the set you didn't pick is 999/1000.
The trick to remember is that the Host knows the number of the door that the prize is behind. The host will never ever open that door. There would be no drama and both the audience and the contestant would feel cheated by the host. It is much more exciting veiewing if the contestant is forced to "stay" or "switch."
Thursday, April 1, 2010
TeXnicCenter
Free Open Source Latex editor/IDE (frontend) for Windows
http://www.texniccenter.org/
This might be useful for people that can't always connect to CDF and
use windows on their computer/Laptop
Since this is only a frontend you still need to install some other software for functionality. Details on the above website.
http://www.texniccenter.org/
This might be useful for people that can't always connect to CDF and
use windows on their computer/Laptop
Since this is only a frontend you still need to install some other software for functionality. Details on the above website.
Growing Sequences Problem
UNDERSTANDING THE PROBLEM:
In class we discussed the Growing Sequences Problem:
Input: An unsorted, finite sequence of numbers. (call this list Ulist)
Sample Input: 5, 12, 11, 22, 4, 16, 35, 7, 11, 12, 34, 112, 1
Output: The longest list of numbers found within Ulist, that are sorted within increasing order, and not necessarily adjacent to each other.
Sample Output
The possible (raw) sequences generated would look like: (* = longest.)
---------------------------------------
5, 12, 22, 35, 112 *
12, 22, 35, 112
11, 22, 35, 112
22, 35, 112
4, 16, 35, 112
16, 35, 112
35, 112
7, 11, 12, 34, 112 *
11, 12, 34, 112
12, 34, 112
34, 112
112
1
--------------------------------------
In our case the longest list is actually two lists. being how there is no set criteria to select one list
over another based upon length, I'd say that all lists of the same length are equal.
Sample Output:
------------------------------------------
Longest sequences generated from Source
5, 12, 22, 35, 112
7, 11, 12, 34, 112
------------------------------------------
It is also noted that, if the Input list was sorted (in increasing order)
then the output would be simply the whole list itself, since this
would be the longest increasing sequence of numbers.
Also it can be seen that a lot of time in the program (with a "blind" algorithm is spent generating sequences and sub-sequences.
ie
(5, 12, 22, 35, 112) = A
Has the sub sequences of:
(12, 22, 35, 112)
(22, 35, 112)
(35, 112)
(112)
but 11, 22, 35, 112 isn't a sub-sequence of A since it starts with 11, which isn't even contained in A. A sub-sequence of A would have to contain a subset of A, in the proper sorted order, and contain fewer elements than A.
Eliminating sub-sequence searching, could save time in the algorithm.
This could be an area for optimization, once we get the basic solution.
We might need a "parallel array" that marks which sequences have been already visited. There may not be any easy way to do this, since a sub-sequence of a particular sequence, might be part of another similar (but different) sequence.
ie (22, 35, 112) = M
is a sub-sequence of 3 lists:
(1) 5, 12, 22, 35, 112
(2) 12, 22, 35, 112
(3) 11, 22, 35, 112
In this case 2 is a sub-sequence of 1, but 3, isn't a sub-sequence of 1. The list M, however, is a sub-sequence of all three lists.
list 3 could be longer than list 2, it is just coincidence that they are the same length.
if you just blindly mark numbers in the parallel array as already being visited, then you might accidentally chop of part of a generated sub-sequence, ie (3) above. This would give an incorrect result. We should probably get fancy with our algorithm later, after getting something working.
--------------------------------------------------------------------------------
Also if you have a list of (111,111,111)
then the longest sequence is it (111) or (111,111,111)
I'd say that (111) since all numbers are equal, and thus not increasing. This problem is trivial to avoid. (Just us strictly less than operator to compare numbers)
repeated adjacent numbers could be removed from the list to save search time, but
removing the numbers also takes time, which might be longer than the search itself.
--------------------------------------------------------------------------------
Another thing to note is that you could save time by chopping off all of the numbers in the original list past the maximum number (in our case 112) in the list if you already have a sub-sequence longer than the length of the numbers that follow the maximum number of the list. Again you can't do this blindly, for if the maximum value was at the beginning of the list, then you'd chop off all of the values, in the list except for the first element. This would most likely not give the answer that we are looking for. Again this is a candidate for future optimization.
--------------------------------------------------------------------------------
DEVISE A PLAN
It looks like this is a sort of a problem involving recursion or induction.
Ie
Is the input list empty then exit (base case)
Try to find the sequence generated when starting with the first number of the list.
Search the list until the end of the list.
save this max list
then strip off the first number of the input list, and do the process again.
(Input List - one element)
search the new Input List
compare this list to your current max_list, if longer in length to the current max_list(s), then this is your new max list. If it is the same length as your current max list(s) then add to max list(s)
etc.
so we need probably at least 3 variables to pass.
the original list of numbers
## ( and the smaller versions of this list )
the list (lists) of generated sequences
## (this is what we want, we need to keep a tally)
## the max length of the current generated sequences. (to compare size)
ie Very roughly
Function Grow_Seq (List, Found_Seq_List, Max_Length)
Begin (*function*)
If source list is empty
Then exit
Else check the list for sequences
If found seq length >= Max_Length
Then add to found seq list(s)
Grow_Seq (List[1..end], Found_Seq_List, Max_Length) # recurse with smaller List
End (*function*)
CARRY OUT PLAN
Pseudocode
Function Grow_SEQ (List, FoundSeq, MaxLength, Append)
## LIST is the input list of numbers (an int array)
## FoundSeq is the currently found list of Sequences (could be a file or int array)
## MaxLength is the current length of the longest found list (int)
## Append is a flag that tells what to do with the newly found list (int flag)
-1 = do nothing
1 = destroy/replace (this new found list is better than the old list
2 = append (this list is equal to the lists already found)
## First call List would be the full list, FoundSeq would be empty, MaxLength would be 0, and append would be 1)
Var i, biggest int = 0
temp_foundSeq (int array) *clear array* = 0
Begin {function}
if sizeof(list) = 0 # check base case
then Return (FoundSeq)
## might be a problem here with one element lists
## need to verify, on first glance is ok
## is exit condition when sizeof(list) = 1 or 0?
##
ELSE # input list larger than the empty set
i=1;
lengthNew =1;
biggest = list[0]; # when we start first element is the largest
temp_FoundSeq [0] = biggest;
while i < (sizeof(list) -1)
Begin {while}
if List[i] > biggest
then temp_FoundSeq[lengthNew]=biggest: lengthNew++
# add the new biggest number to the found sequence, add one to the length of
# the found sequence
i++
# advance to the next element of the source list
End {while}
## at this point we have generated a new FoundSeq
## must compare it to other FoundSeq
if lengthnew < MaxLength
## then this sequence is no better than what we've already found
## call with shorter list
then Grow_SEQ (List [1..end], FoundSeq, MaxLength, -1)
if lengthnew > MaxLength
then FoundSeq = Temp_FoundSeq ## change the original value for FoundSeq
## might have to worry about pass by value
## versus pass by variable here
Grow_SEQ (List [1..end], FoundSeq, lengthnew, 1)
## This is the new sequence, better than all yet found
## we can assume that lengthnew = MaxLength if we've made it this far.
Grow_SEQ (List [1..end], Temp_FoundSeq, MaxLength, 2)
End {function}
LOOK BACK
I am confident that the above pseudocode is on the right track.
The easiest way would be to implement the code in some language and see how it goes.
the tricky part, the part that I've not figured out yet is what exactly to do if you have a new sequence that is the same length as the already found sequence(s)
do we store all the found sequences in a file? This might be good, just reset the file when we find a new set of sequences of larger size. Or perhaps some sort of dynamically allocatable variable? Or some sort of linked list. Also some languages pass by value only, so we have to be sure in the function calls if we want to modify the original calling variable. (in this case specifically FoundSeq)
This is just a basic algorithm, when implemented, it could be improved, by removing some of the searches through the subsets of the lists, and by chopping off the end of the original list wherever possible. Care would have to be maintained to not add so many checks that the original function might not be slower.
Also this function may need an auxilliary function
for 1) special cases in the first function call (unlikely)
for 2) functions to take care of appending/destroying the current list of FoundSeq numbers.
In class we discussed the Growing Sequences Problem:
Input: An unsorted, finite sequence of numbers. (call this list Ulist)
Sample Input: 5, 12, 11, 22, 4, 16, 35, 7, 11, 12, 34, 112, 1
Output: The longest list of numbers found within Ulist, that are sorted within increasing order, and not necessarily adjacent to each other.
Sample Output
The possible (raw) sequences generated would look like: (* = longest.)
---------------------------------------
5, 12, 22, 35, 112 *
12, 22, 35, 112
11, 22, 35, 112
22, 35, 112
4, 16, 35, 112
16, 35, 112
35, 112
7, 11, 12, 34, 112 *
11, 12, 34, 112
12, 34, 112
34, 112
112
1
--------------------------------------
In our case the longest list is actually two lists. being how there is no set criteria to select one list
over another based upon length, I'd say that all lists of the same length are equal.
Sample Output:
------------------------------------------
Longest sequences generated from Source
5, 12, 22, 35, 112
7, 11, 12, 34, 112
------------------------------------------
It is also noted that, if the Input list was sorted (in increasing order)
then the output would be simply the whole list itself, since this
would be the longest increasing sequence of numbers.
Also it can be seen that a lot of time in the program (with a "blind" algorithm is spent generating sequences and sub-sequences.
ie
(5, 12, 22, 35, 112) = A
Has the sub sequences of:
(12, 22, 35, 112)
(22, 35, 112)
(35, 112)
(112)
but 11, 22, 35, 112 isn't a sub-sequence of A since it starts with 11, which isn't even contained in A. A sub-sequence of A would have to contain a subset of A, in the proper sorted order, and contain fewer elements than A.
Eliminating sub-sequence searching, could save time in the algorithm.
This could be an area for optimization, once we get the basic solution.
We might need a "parallel array" that marks which sequences have been already visited. There may not be any easy way to do this, since a sub-sequence of a particular sequence, might be part of another similar (but different) sequence.
ie (22, 35, 112) = M
is a sub-sequence of 3 lists:
(1) 5, 12, 22, 35, 112
(2) 12, 22, 35, 112
(3) 11, 22, 35, 112
In this case 2 is a sub-sequence of 1, but 3, isn't a sub-sequence of 1. The list M, however, is a sub-sequence of all three lists.
list 3 could be longer than list 2, it is just coincidence that they are the same length.
if you just blindly mark numbers in the parallel array as already being visited, then you might accidentally chop of part of a generated sub-sequence, ie (3) above. This would give an incorrect result. We should probably get fancy with our algorithm later, after getting something working.
--------------------------------------------------------------------------------
Also if you have a list of (111,111,111)
then the longest sequence is it (111) or (111,111,111)
I'd say that (111) since all numbers are equal, and thus not increasing. This problem is trivial to avoid. (Just us strictly less than operator to compare numbers)
repeated adjacent numbers could be removed from the list to save search time, but
removing the numbers also takes time, which might be longer than the search itself.
--------------------------------------------------------------------------------
Another thing to note is that you could save time by chopping off all of the numbers in the original list past the maximum number (in our case 112) in the list if you already have a sub-sequence longer than the length of the numbers that follow the maximum number of the list. Again you can't do this blindly, for if the maximum value was at the beginning of the list, then you'd chop off all of the values, in the list except for the first element. This would most likely not give the answer that we are looking for. Again this is a candidate for future optimization.
--------------------------------------------------------------------------------
DEVISE A PLAN
It looks like this is a sort of a problem involving recursion or induction.
Ie
Is the input list empty then exit (base case)
Try to find the sequence generated when starting with the first number of the list.
Search the list until the end of the list.
save this max list
then strip off the first number of the input list, and do the process again.
(Input List - one element)
search the new Input List
compare this list to your current max_list, if longer in length to the current max_list(s), then this is your new max list. If it is the same length as your current max list(s) then add to max list(s)
etc.
so we need probably at least 3 variables to pass.
the original list of numbers
## ( and the smaller versions of this list )
the list (lists) of generated sequences
## (this is what we want, we need to keep a tally)
## the max length of the current generated sequences. (to compare size)
ie Very roughly
Function Grow_Seq (List, Found_Seq_List, Max_Length)
Begin (*function*)
If source list is empty
Then exit
Else check the list for sequences
If found seq length >= Max_Length
Then add to found seq list(s)
Grow_Seq (List[1..end], Found_Seq_List, Max_Length) # recurse with smaller List
End (*function*)
CARRY OUT PLAN
Pseudocode
Function Grow_SEQ (List, FoundSeq, MaxLength, Append)
## LIST is the input list of numbers (an int array)
## FoundSeq is the currently found list of Sequences (could be a file or int array)
## MaxLength is the current length of the longest found list (int)
## Append is a flag that tells what to do with the newly found list (int flag)
-1 = do nothing
1 = destroy/replace (this new found list is better than the old list
2 = append (this list is equal to the lists already found)
## First call List would be the full list, FoundSeq would be empty, MaxLength would be 0, and append would be 1)
Var i, biggest int = 0
temp_foundSeq (int array) *clear array* = 0
Begin {function}
if sizeof(list) = 0 # check base case
then Return (FoundSeq)
## might be a problem here with one element lists
## need to verify, on first glance is ok
## is exit condition when sizeof(list) = 1 or 0?
##
ELSE # input list larger than the empty set
i=1;
lengthNew =1;
biggest = list[0]; # when we start first element is the largest
temp_FoundSeq [0] = biggest;
while i < (sizeof(list) -1)
Begin {while}
if List[i] > biggest
then temp_FoundSeq[lengthNew]=biggest: lengthNew++
# add the new biggest number to the found sequence, add one to the length of
# the found sequence
i++
# advance to the next element of the source list
End {while}
## at this point we have generated a new FoundSeq
## must compare it to other FoundSeq
if lengthnew < MaxLength
## then this sequence is no better than what we've already found
## call with shorter list
then Grow_SEQ (List [1..end], FoundSeq, MaxLength, -1)
if lengthnew > MaxLength
then FoundSeq = Temp_FoundSeq ## change the original value for FoundSeq
## might have to worry about pass by value
## versus pass by variable here
Grow_SEQ (List [1..end], FoundSeq, lengthnew, 1)
## This is the new sequence, better than all yet found
## we can assume that lengthnew = MaxLength if we've made it this far.
Grow_SEQ (List [1..end], Temp_FoundSeq, MaxLength, 2)
End {function}
LOOK BACK
I am confident that the above pseudocode is on the right track.
The easiest way would be to implement the code in some language and see how it goes.
the tricky part, the part that I've not figured out yet is what exactly to do if you have a new sequence that is the same length as the already found sequence(s)
do we store all the found sequences in a file? This might be good, just reset the file when we find a new set of sequences of larger size. Or perhaps some sort of dynamically allocatable variable? Or some sort of linked list. Also some languages pass by value only, so we have to be sure in the function calls if we want to modify the original calling variable. (in this case specifically FoundSeq)
This is just a basic algorithm, when implemented, it could be improved, by removing some of the searches through the subsets of the lists, and by chopping off the end of the original list wherever possible. Care would have to be maintained to not add so many checks that the original function might not be slower.
Also this function may need an auxilliary function
for 1) special cases in the first function call (unlikely)
for 2) functions to take care of appending/destroying the current list of FoundSeq numbers.
Wednesday, March 31, 2010
Knights and Knaves
On a magical island of knights and knaves (from chapter 1) there are 2 kinds of people: knights, who must always tell the truth, and knaves that must always lie.
There is a cruel 3-d reality televison show:Your Money or Your Life, in which there are two doors to choose from. Behind one door, lay untold riches, behind the other door, certain doom! One door is guarded by a knight, the other by a knave. You may ask one guard a yes/no question before opening the door of your choosing. What question should you ask?
You don't know which door has the treasure, and you can't tell a knight from a knave based upon appearance.
(again teaser question from chapter 1)
If you were to ask:
"Is the treasure behind the door at yon guard-post my good gentleman?"
(Must speak with a noble tongue)
If the guard were the knight, and the treasure is behind the door, he would say yes.
however, if the guard were the knave, and the treasure is still behind the door, then he would say no. If you followed the knave's advice then you would pick the door of doom.
Knight AND treasure, answer = Yes
Knight And Not treasure answer = No
Knave And treasure, answer = No
Knave And Not Treasure, answer = Yes.
This doesn't help, since half of the time the answer is yes and half no. This is no better than guessing.
After some deliberation, it seems that you should ask either guard this question: "Yon Noblest of Guards, which door would your fine compatriot pick to select the treasures?"
Guard = knight then he would have to tell the truth, so he'd pick the door of doom. this is the door that the Knave would choose as the treasure door. Remember the Knave isn't out to get you, he just can't tell the truth.
Guard = knave, then he'd lie about the door that the knight would select, so he would also pick the door of doom as the treasure door.
So the best thing to do would be to ask the above question and select the door that isn't recommended as the treasure door by the the guard.
With this strategy, you should have a lifetime of fortune and good luck, and a certain victory!
There is a cruel 3-d reality televison show:Your Money or Your Life, in which there are two doors to choose from. Behind one door, lay untold riches, behind the other door, certain doom! One door is guarded by a knight, the other by a knave. You may ask one guard a yes/no question before opening the door of your choosing. What question should you ask?
You don't know which door has the treasure, and you can't tell a knight from a knave based upon appearance.
(again teaser question from chapter 1)
If you were to ask:
"Is the treasure behind the door at yon guard-post my good gentleman?"
(Must speak with a noble tongue)
If the guard were the knight, and the treasure is behind the door, he would say yes.
however, if the guard were the knave, and the treasure is still behind the door, then he would say no. If you followed the knave's advice then you would pick the door of doom.
Knight AND treasure, answer = Yes
Knight And Not treasure answer = No
Knave And treasure, answer = No
Knave And Not Treasure, answer = Yes.
This doesn't help, since half of the time the answer is yes and half no. This is no better than guessing.
After some deliberation, it seems that you should ask either guard this question: "Yon Noblest of Guards, which door would your fine compatriot pick to select the treasures?"
Guard = knight then he would have to tell the truth, so he'd pick the door of doom. this is the door that the Knave would choose as the treasure door. Remember the Knave isn't out to get you, he just can't tell the truth.
Guard = knave, then he'd lie about the door that the knight would select, so he would also pick the door of doom as the treasure door.
So the best thing to do would be to ask the above question and select the door that isn't recommended as the treasure door by the the guard.
With this strategy, you should have a lifetime of fortune and good luck, and a certain victory!
Other Text Books
here is one book that I found to be useful, (along with the course notes)
sometimes it helps to consult another outside reference to better explain what is in the course material. I find it hard to find a book that covers the areas that we are covering in class. There are many books on "discrete mathematics" and many books on proofs, and logic, but not too many that are useful directly for computer science. (That apply to the introductory level.)
This book is on logic and proofs in mathematics.
Houston, Kevin. How to Think like a Mathematician. New York, NY: Cambridge University Press, 2009.
Another good book is called "Concrete Mathematics" by Donald Knuth.
http://en.wikipedia.org/wiki/Concrete_Mathematics
But be warned it is a hard book to read, but it may be useful for later csc courses of this type.
sometimes it helps to consult another outside reference to better explain what is in the course material. I find it hard to find a book that covers the areas that we are covering in class. There are many books on "discrete mathematics" and many books on proofs, and logic, but not too many that are useful directly for computer science. (That apply to the introductory level.)
This book is on logic and proofs in mathematics.
Houston, Kevin. How to Think like a Mathematician. New York, NY: Cambridge University Press, 2009.
Another good book is called "Concrete Mathematics" by Donald Knuth.
http://en.wikipedia.org/wiki/Concrete_Mathematics
But be warned it is a hard book to read, but it may be useful for later csc courses of this type.
Demon in Pentagon Recap
So far, we have
1) Shown that the Demon may be powerful, but he can't change the net sum of the values of the vertices. This number is always constant, and nonzero. His actions have no net effect on the total.
ie
x1+x2+x3+x4+x5 > 0, where x1..x5 are all integers
x1+x2+x3+x4+x5 = c, where c > 0.
START
Find a negative number, can be any negative number in the set
Case #1
IF all numbers in the set of 5 are positive or zero. then EXIT
Case #2
If the neg_num is bounded on both sides by any 2 positive numbers say x1, x2
such that neg_num + x1 >=0, and neg_num + x2 >=0 then the neg_num is removed.
(the middle neg_num, becomes positive, and its neighbours are both positive or zero.)
the signs of (x1, neg_num, x2) go from (+,-,+) to (+,+,+)
CASE #3
(x1+neg_num<0, and x2+neg_num>=0) or (x1+neg_num>=0,and x2+neg_num<0)
If the negative number is bounded on one side by a larger positive number or a number that is equal to that number but different in sign, and on the other by a number that becomes more negative when added to the middle negative number, then the resulting negative number travels around the pentagon in a specific direction.
signs for (x1,neg_num, x3) change from {{-,-,+)or(+,-,-)} to {(-,+,+)or(+,+,-)}
(Remember for our purposes 0, is considered a positve number)
The negative number "rounds the bases" so to speak, in the direction away from the positive number or zero behind it. and after several turns, the negative number, will either cover its tracks, until it collides with a number that is larger, and destroys it or it will meet another negative number that makes it more negative. Eventually the negative number gets canceled out since there are more positive numbers (of total higher value) "manning" the bases than negative ones. each time the negative number meets a positive number, it gets closer and closer to zero, (from the negative side of zero) or itself becomes positive.
Case 4
The only remaining case, is when the Negative number is bounded by numbers x1,x2 such that abs(neg_number) >= x1, and abs(neg_number) >=x2
or in this case x1+neg_num < 0, and x2+neg_num <0
so the numbers x1, neg_num, x2 go from either {(-,-,-)or(+,-,+)} to (-,+,-)
This split in sign leads to either (consider one of the (x1<0,x2<0) to be the new center) {case 3 (-.-.+) or (+,-,-) or case 4 (+,-,+), but eventually to case 2 (also (+,-,+). (we know this since there are an ODD number of vertices, and there is always either a single value larger than any negative number or there is a subset of positive values that are collectively larger than any single negative vertex or the sum of the subset of the negative vertices), which eventually leads to case 1. and we are done. Phew
--------------------------------------------------------------------------------
This is probably easier to see with triangles than pentagons, as the -numbers in
this case can never be surrounded by 2 negative numbers.
upon trying this out with squares it seems that the daemon would finish sometimes and not others. In the case where you finish with a square you would have one negative number on a corner. if you have two negative numbers on opposite corners (kitty corner) to each other, it seems that the situation arises where you always eliminate one negative number and create another, creating a sort of an endless loop that never terminates.
In the case of the odd sided figures, ie triangle, pentagon, heptagon etc., eventually the negative numbers get trapped between 2 larger numbers, or they get reduced. The moving negative numbers make the positive numbers smaller in the same way, while simultaneously and always ensuring that (positive + negative >0). Each of the positive numbers and the negative numbers wobble towards zero. when the values converge, so that they are both positive, the daemon is finished
1) Shown that the Demon may be powerful, but he can't change the net sum of the values of the vertices. This number is always constant, and nonzero. His actions have no net effect on the total.
ie
x1+x2+x3+x4+x5 > 0, where x1..x5 are all integers
x1+x2+x3+x4+x5 = c, where c > 0.
START
Find a negative number, can be any negative number in the set
Case #1
IF all numbers in the set of 5 are positive or zero. then EXIT
Case #2
If the neg_num is bounded on both sides by any 2 positive numbers say x1, x2
such that neg_num + x1 >=0, and neg_num + x2 >=0 then the neg_num is removed.
(the middle neg_num, becomes positive, and its neighbours are both positive or zero.)
the signs of (x1, neg_num, x2) go from (+,-,+) to (+,+,+)
CASE #3
(x1+neg_num<0, and x2+neg_num>=0) or (x1+neg_num>=0,and x2+neg_num<0)
If the negative number is bounded on one side by a larger positive number or a number that is equal to that number but different in sign, and on the other by a number that becomes more negative when added to the middle negative number, then the resulting negative number travels around the pentagon in a specific direction.
signs for (x1,neg_num, x3) change from {{-,-,+)or(+,-,-)} to {(-,+,+)or(+,+,-)}
(Remember for our purposes 0, is considered a positve number)
The negative number "rounds the bases" so to speak, in the direction away from the positive number or zero behind it. and after several turns, the negative number, will either cover its tracks, until it collides with a number that is larger, and destroys it or it will meet another negative number that makes it more negative. Eventually the negative number gets canceled out since there are more positive numbers (of total higher value) "manning" the bases than negative ones. each time the negative number meets a positive number, it gets closer and closer to zero, (from the negative side of zero) or itself becomes positive.
Case 4
The only remaining case, is when the Negative number is bounded by numbers x1,x2 such that abs(neg_number) >= x1, and abs(neg_number) >=x2
or in this case x1+neg_num < 0, and x2+neg_num <0
so the numbers x1, neg_num, x2 go from either {(-,-,-)or(+,-,+)} to (-,+,-)
This split in sign leads to either (consider one of the (x1<0,x2<0) to be the new center) {case 3 (-.-.+) or (+,-,-) or case 4 (+,-,+), but eventually to case 2 (also (+,-,+). (we know this since there are an ODD number of vertices, and there is always either a single value larger than any negative number or there is a subset of positive values that are collectively larger than any single negative vertex or the sum of the subset of the negative vertices), which eventually leads to case 1. and we are done. Phew
--------------------------------------------------------------------------------
This is probably easier to see with triangles than pentagons, as the -numbers in
this case can never be surrounded by 2 negative numbers.
upon trying this out with squares it seems that the daemon would finish sometimes and not others. In the case where you finish with a square you would have one negative number on a corner. if you have two negative numbers on opposite corners (kitty corner) to each other, it seems that the situation arises where you always eliminate one negative number and create another, creating a sort of an endless loop that never terminates.
In the case of the odd sided figures, ie triangle, pentagon, heptagon etc., eventually the negative numbers get trapped between 2 larger numbers, or they get reduced. The moving negative numbers make the positive numbers smaller in the same way, while simultaneously and always ensuring that (positive + negative >0). Each of the positive numbers and the negative numbers wobble towards zero. when the values converge, so that they are both positive, the daemon is finished
Demon in the Pentagon (part 5)
I thought this morning on the bus about an interesting and (perhaps simpler) case.
What if there are only 2 numbers in the pentagon? IE the set of values is: {0,0,0,8,-7}?
Then there is only one negative value to concern ourselves with, and this makes the problem a little easier to digest.
Then (see the scanned sheet) something interesting happens, the negative number "splits or partitions" for the lack of a better word, the number 8 into +7, and +1
then the -7 goes around the pentagon in circular fashion. every time the negative number (in this case -7) passes the 1 (think of it like a finish line) then the -7 becomes a -6. When the -6 starts its trek around the circle it creates a new #1 behind it, thus creating a new finish line.
So we have a progression like this (add both numbers together, you always get a 1.)
(8,-7), (7,-6), (6,-5), (5,-4), (4,-3), (3,-2), (2,-1), (1, 0)
now we are done since both numbers are considered positive or 0.
In this case we have simplified the problem somewhat, but it is indeed the same problem.
The fact that (neg_numbers) + (pos_numbers) = c, c>0
forces this to eventually terminate.
This specific case is actually the same as the general case. This may or may not seem obvious, but when there are only 2 numbers, this is the same as the subset of the negative numbers, versus the subset of the positive numbers.
Subscribe to:
Posts (Atom)