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!

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.

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

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.

Demon Pentagon Part 4

As you can see in the above graph, the values for the max and min seem to converge towards zero throughout the trial. Probably the way to prove that the trial finishes is to show that the max and min values converge towards zero, always.

The graph only shows what happens for this one specific case.

Daemon in a Pentagon (part 3)

In the last post, I had found 2 simple cases for the demon pentagon to clearly finish. Now it seems that the problem is getting harder.

Case #3

If one vertex is surrounded by 2 negative vertices then it will become positive, but the 2 adjacent vertices will become more negative. (But remember that the sum doesn't get any worse)

ie try

{1,-3,-2,-3,10} If the Daemon picks the -2, . . .

(Hey I'm not going to argue with a Daemon, maybe they breathe fire, or they might have large teeth and hinged jaws that drool green digestive juices . . .)

then the result becomes

{1,-5,2,-5,10} which doesn't exactly finish right away, as the negative fives aren't surrounded by nice larger numbers. (at least the sum is still the same)

It seems that the quantity of negative numbers is getting smaller, I wonder if this is always the case?

It seems not as shown on my sample sheet (the scan from Daemon #1 post) There are originally 4 vertices with the negative numbers. (all -3) each step seems to decrease the number of negative values. This is true until step 4.

The Pentagon goes from having only one negative number (-12) to having 2 negative numbers again (-9,-9) so it is possible for the amount of negative values to increase. We want them to all go away.

In the sample solution, they do all go away. I get an intuitive feeling that they should all go away eventually. In the several examples it always seems to work. but how to prove it?

Progression of Negative Vertices

Step#, # of negative vertices

0,4 START
1,3
2,3
3,2
4,1
5,2
6,2
7,1
8,2
9,2
10,1
11,2
12,1
13,2
14,1
15,2
16,2
17,1
18,1
19,1
20,0 Done

So there does seem to be a progression, with the number of negative vertices decreasing quickly from 4 to 1, and then jumping from one to two and back again until settling on one and then stopping at zero.

If the demon picked other vertices than I did in each step, then the number of steps may be different. (or not? the same?)

Also the fact that this is a pentagon may be another factor. if it was an even sided figure, I'd bet that it would be less likely to finish. I wonder what would happen for a triangle or a square?

It seems to work the same for triangles and squares. So reducing the number of sides doesn't seem to help much.

The triangle and the square do seem to progress faster. I am not entirely sure that if you had an even number of sides that you couldn't get a condition where the numbers flip back and forth.

One example that I tried with a square, with 2 negative sides and 2 positive sides would never seem to finish. Proving that the square would never finish doesn't seem any easier than proving that the pentagon will finish, however, so this isn't exactly a simpler problem.

demon in a pentagon part 2

In the above and last post you can see a picture. If you click on the picture it will resize to something more legible. This is a sample run through of one instance of the Daemon Pentagon.

you will notice at step 0, the values for the 5 vertices are: {-3,-3,-3,-3,15}.

This satisfies the condtions of the problem, that all the vertices are integers, and although some may be negative, their net sum is positive.

In this case it is positive value of 3. One of the first things I noticed, from doing the diagram, is that the sum of the vertices is a constant value that never seems to change. The demon manipulation never changes the sum total of all the vertices. While this may or may not help us to solve our problem, it might be useful. This is what the circled (#3) in the heart of the pentagon represents.

You will also notice that our problem terminates (in this case) after 21 steps when all vertices are 0, except for one vertex that has a value 3. (sum still 3)

I have tried other examples, where the final vertices don't contain any zeros, so the number zero isn't a condition for completion. But in our case, I'd guess that we'd have to consider zero to be a positive number. Ie. the Daemon finishes when all of the numbers in the pentagon are non-negative ie {x1,x2,x3,x4,x5|>=0)

The included example may be too complicated, so I am going to try a simpler example
------------------------------------------------------------------------------------

Simple Case #1,

All vertices are positive, and then the sum of the vertices is positive. We are done, The daemon can't do anything. Could this be a base case?
------------------------------------------------------------------------------------
Simple Case #2

if you consider the simple problem of {1,2,5,-3,5}

note: ** the end of the list is connected to the beginning, imagine the pentagon or write it out on paper **

then the only number that clearly needs changing is the -3. This number is trapped between two fives, so the solution is easy.

{1,2,5,-3,5} goes to {1,2,2,3,2} and we are done.

( Notice the sums in both cases are 10, satisfying our "sum property." )
-------------------------------------------------------------------------------------
in fact, I am going to try to formalize the sum property.

x1+x2+x3+x4+x5 > 0, where x1..x5 are all integers
x1+x2+x3+x4+x5 = c, where c > 0.

the daemon step to remove the negative number basically does this:

(IE assume x3 is negative.)

x1,x2+x3,abs(x3),x4+x3,x5 ## abs(x3) is the absolute value of x3

this is the same as

x1, x2-x3, -x3 +x3+x3, x4-x3, x5.

the 2*x3 added to the negative x3, cancel each x3 subtracted from the adjacent vertices to x3.

so we know that the "sum property" always holds, as the daemon only changes one vertex at a time, and only affects 3 vertices, with no net effect to the sum total of all vertices.

I don't know if this feature of the problem is useful, but now at least we know that the problem can never have the situation where all of the vertices become negative. (The sum is always positive, and it is always the same unchanging positive value c.)

(for each instance of the problem) If all vertices were to become negative then the demon would never finish, as he could spend forever changing the negative numbers to positive and back again.

Daemon in a Pentagon

There is a problem in the first chapter of the course notes called Daemon in a Pentagon. It has nothing to do with some mythical creature living in a Washington military complex, rather it is like one of those puzzles in the paper, that grabs hold of you and won't let go.

I will quote the original text: (Ch1, p10.)

There is a pentagon, and at each vertex there is an integer number. The numbers can be negative, but their sum is positive. A daemon living inside the pentagon manipulates the numbers with the following atomic action. If it spots a negative number at one the vertices, it adds that number to its two neighbours and negates the number at the original vertex. Prove that no matter what numbers we start with, eventually the daemon cannot change any of the numbers.

I am going to try to solve this problem, following the G.Polya, how to solve it guide.

http://www.math.edu/~alfeld/math/polya.html

First you have to understand the problem . . .

Hey, if I understood the problem, I could solve it right away? but it is true that if you don't know the problem, if you aren't familiar with the problem, you will probably dither away your time, rather than solve the problem.

I tried doing several "daemon pentagons" on paper to see what would happen. The worst possible example is included here: