Alright, that was a good year of not blogging, but I'm back, for today, who knows for how long. Anyway, time to post the solution to the funny Knights and Knaves puzzle from last time.

First, I will refer to each person at the party by naming them with the number of truth tellers they claim to have shaken hands with. Now, you can determine right away that person 99 must be a liar, as if he did shake hands with 99 truth tellers then everybody would be a truth teller, including the individual who claims to have shaken hands with nobody. This is a contradiction, so person 99 is a liar. One can continue this down by looking at person 98 next. Since 99 is a liar, in order for 98 to be telling they truth, everybody else must be a truth teller, but this agian would make person 0 a liar, since 98 shook hands with everybody (except possibly 99) in this assumption. So 98 is also a liar.

This logic continues down, making all individuals who claim to have shaken hands with a positive number of truth tellers liars. This leaves only person 0 as a possible truth teller. As there were no other truth tellers at the party, it is certian that person 0 shook hands with no truth tellers, thus person 0 is in fact a truth teller. This gives the answer to the puzzle as 1, there is only 1 truth teller at the party.

Somebody had pointed out to me that there is a silly solution that works out, since the answer is independent of the knowledge of who shook hands with who, it is possible there were no handshakes. In that case person 0 is telling the truth, and everybody else is a liar. This has no contradictions and must be a possible solution, so if there is actually a solution to the puzzle, then the solution must be 1. I'm always reluctant to actually use this sort of solution, as it feels like something of a hack to assume a solution exists and then go from there, but it does often work to use this trick.

### Knight Party

Oh right, I have a blog I'm supposed to maintain. All sorts of new puzzles these days, means I will proably forget them all before I manage to post them.

So, this is a knights and knaves puzzle, which I have in the past said I don't like, but I keep finding interesting ones (for those that don't recall, "knights" are people who always tell the truth, and "knaves" are people who always lie, not that that is actaully relavent for this puzzle, but it sets the tone a bit).

I got this puzzle from Presh Talwalkar's YouTube channel:

Naturaly, you can take it as given that if A shakes hands with B, then B also shook hands with A, you may also assume that nobody can shake hands with themselves. It is possible that everybody shook hands with everybody else, or simply that there were no handshakes, or anything in between of course. The solution is nothing special, but it is a nice logical solution.

So, this is a knights and knaves puzzle, which I have in the past said I don't like, but I keep finding interesting ones (for those that don't recall, "knights" are people who always tell the truth, and "knaves" are people who always lie, not that that is actaully relavent for this puzzle, but it sets the tone a bit).

I got this puzzle from Presh Talwalkar's YouTube channel:

There is a party with 100 people, and each person is either a truth teller or a lair. At the party, some of the people may shake hands with eachother, and after the party you ask each person "How many truth tellers did you shake hands with?". The people each give a different answer, with each integer from 0 to 99 appearing as an answer.

How many truth tellers are at the party?

Naturaly, you can take it as given that if A shakes hands with B, then B also shook hands with A, you may also assume that nobody can shake hands with themselves. It is possible that everybody shook hands with everybody else, or simply that there were no handshakes, or anything in between of course. The solution is nothing special, but it is a nice logical solution.

### Pascals Cube

Well, summer has now mostly gone by with no posts from me on that puzzle about the cube of resistors, so I guess I'll solve it now.

The thing to do for the initial puzzle in three dimensions is conisder the eight vertices of the cube and apply a potential difference of V between one vertex and the opposite corner. We could then find the current and the ratio would give us the resistance. The trick is then to notice that the three vertices that are one edge away from the starting vertex are an equpotential, so they can be fused into a single vertex. Then notice that the three vertices that are adjacent to the final vertex are also an equipotential. We then have only 4 vertices, the first is connected to the second by 3 resistors, the second connected to the third by 6 resistors (takes a bit of work to confirm that 6) and the third is connected to the fourth by 3 resistors. Since M 1-Ohm resistors in parallel have an effective resistance of 1/M, the equivalent resistance of this is 1/3+1/6+1/3=5/6

OK, thats fun, and should generalize pretty fast, but we need to see exactly how. In N dimensions, each vertex can be represented as a series of N zeros and ones, and this is a complete list of the 2

So, in order to find the total resistance, we simply need to add up 1/N*

The thing to do for the initial puzzle in three dimensions is conisder the eight vertices of the cube and apply a potential difference of V between one vertex and the opposite corner. We could then find the current and the ratio would give us the resistance. The trick is then to notice that the three vertices that are one edge away from the starting vertex are an equpotential, so they can be fused into a single vertex. Then notice that the three vertices that are adjacent to the final vertex are also an equipotential. We then have only 4 vertices, the first is connected to the second by 3 resistors, the second connected to the third by 6 resistors (takes a bit of work to confirm that 6) and the third is connected to the fourth by 3 resistors. Since M 1-Ohm resistors in parallel have an effective resistance of 1/M, the equivalent resistance of this is 1/3+1/6+1/3=5/6

OK, thats fun, and should generalize pretty fast, but we need to see exactly how. In N dimensions, each vertex can be represented as a series of N zeros and ones, and this is a complete list of the 2

^{N}vertices, each vertex is connected to the N vertices next to it, so any vertex has N edges on it. So N edges lead out from the initial vertex to the first equipotential. Next, the N vertices have 1 edge leading backward, and N-1 leading forward, so there are a total of N*(N-1) edges leading to the next equipotential (This is N*_{N-1}C_{1}). The next_{N}C_{2}vertices each have N*(N-1)/_{N}C_{2}(which is 2) edges from beind them, so there are N-2 going forward. This means there are a total of N(N-1)/2*(N-2) vertices going forward (this is N*_{N-1}C_{2}. As you can guess, the number of vertices going forward is always N*_{N-1}C_{k}, with k going from 0 to N-1.So, in order to find the total resistance, we simply need to add up 1/N*

_{N-1}C_{k}, which is 1/N times the sum of the recriprocials of the N^{th}row of Pascal's triangle. This doesn't really have much of a closed form, but its enough to let you figure out the specific number for any particular value of N. There is a bit of a question left of the infinite limit, and fortunately Ben found a paper called "Sum of the reciprocals of the binomial coefficients", which should be easy enough to find if you are interested, the main point here though is that the limit of the sum at large N is 2, therefore the effective resistance is 2/N. Not much of an answer I guess, but I'm always happy when Pascal's triangle shows up.### Resistor Cube

Two posts in one month? Crazy. Anyway, I got a new puzzle, which I learned from the electromagnetism course I was teaching this term....well, sort of, I expanded a simpler puzzle into a surprisingly awesome one.

Sad that its really a physics puzzle, I prefer doing more math when I can, but I'm not sure how to turn this puzzle into a fully mathematical one. Anyway, the real puzzle is to generalize that puzzle into N dimensions. So, have fun with that.

Consider a cube, whose edges are 1 Ohm resistors, what is the effective resistance between opposite corners of the cube?

Sad that its really a physics puzzle, I prefer doing more math when I can, but I'm not sure how to turn this puzzle into a fully mathematical one. Anyway, the real puzzle is to generalize that puzzle into N dimensions. So, have fun with that.

### Partitioning

So, I have a few new puzzles in the bank now, so I need to get to blogging agian to spend them. I guess I need to start with my solution to the number puzzle from last time.

So, we have a list of numbers L, with n elements, whose some is S, and the sum is known to both people. Further, they have a product P and if you knew P, n, and S, the list is not uniquely specified. We want to find the list that has these properties with the smalles S possible. We are looking for two lists I will call L

Its easy to see that L must have more than 2 numbers, since if you adjust two numbers and keep their sum the same, the product must get larger for the list that has the numbers closer together (you maximize the area of a rectangle by making it more square). So the list will need at least 3 numbers. Further, if L

At the point it is basically a matter of playing around, the first solution I found was {2,2,10} and {1,5,8}, which was just playing around with the possible prime factorizations of numbers that seems like good canditates. I was quite certian this was the smallest solution, I am quite sure (but less than 100% sure) that there are no solutions with n=3 that have a smaller S, and I had assumed there wouldn't be a smaller S that used larger n, but then Ben told me he had a solution with S=12, so I had to go looking. Eventually I found it as {2,2,2,6} and {1,3,4,4}. Ben says he has proved with a computer that there are no smaller S solutions, but I am interested if there are any solutions out there with a smaller P, however I doubt it.

Anyway, thats all I got here.

So, we have a list of numbers L, with n elements, whose some is S, and the sum is known to both people. Further, they have a product P and if you knew P, n, and S, the list is not uniquely specified. We want to find the list that has these properties with the smalles S possible. We are looking for two lists I will call L

_{1}and L_{2}.Its easy to see that L must have more than 2 numbers, since if you adjust two numbers and keep their sum the same, the product must get larger for the list that has the numbers closer together (you maximize the area of a rectangle by making it more square). So the list will need at least 3 numbers. Further, if L

_{1}and L_{2}have any numbers in common, we may as well delete the common numbers from both lists, as they will still have equal total sums and products after common numbers are deleted.At the point it is basically a matter of playing around, the first solution I found was {2,2,10} and {1,5,8}, which was just playing around with the possible prime factorizations of numbers that seems like good canditates. I was quite certian this was the smallest solution, I am quite sure (but less than 100% sure) that there are no solutions with n=3 that have a smaller S, and I had assumed there wouldn't be a smaller S that used larger n, but then Ben told me he had a solution with S=12, so I had to go looking. Eventually I found it as {2,2,2,6} and {1,3,4,4}. Ben says he has proved with a computer that there are no smaller S solutions, but I am interested if there are any solutions out there with a smaller P, however I doubt it.

Anyway, thats all I got here.

### Numbers In A Room

Guess its time for a new puzzle, so I can claim to post at least once a month. This is one Ben showed me, but I am rewording it heavily from the original:

The "theme" might be a bit thin, but it wasn't any better in the original, and at least this makes it clearer.

Walking through a building, you overhear a conversation two people are having in a room:

Person 1: I have written down a list of positive integers whose sum is the room number of this room.

Person 2: If you were to tell me how many numbers were on the list and their total product, would I be able to figure out what numbers were on the list, given that I already know the room number we are in?

Person 1: No, you would not.

Person 2: Alright, I now know the total product of the numbers.

What is the smallest room number they could be in?

The "theme" might be a bit thin, but it wasn't any better in the original, and at least this makes it clearer.

### Order or Not

Solution time?? Solution time. Puzzle last time was the one about magical balloons. The solution is far from unique, but here is the one I found:

One flaw that I didn't like about this strategy is that it isn't memoryless, the tests I intend to do each step depends on the results of previous steps, and you can come up with memoryless strategies. However, if you look at the last path of my strategy: Test 1&2, then 2&3, then 1&3&4, that will work to be a memoryless strategy, you just have to analyise your results when you are done. I do not know of any strategy that is totally memoryless, that is, one that there is no path through it that you couldn't have just used from the start as a memoryless strategy.

Other things I don't know about this puzzle: how the heck to generalize it to N balloons and K measurements, so thats a thing to work on.

Step 1: Name the balloons 1,2,3,4, measure 1 and 2 in the machine. If the machine tells you that either zero or two of them are magical, you can just test the other two balloons one at a time using your remaining two measurements. So proceed assuming we got a result of one.

Step 2: Test 2 and 3 in the machine. If the result is zero, you know 1 is magical and you can test 4 alone. If the result is two, you know 1 isn't magical and agian you can test 4 alone. If the result is one, then either 1 and 3 are both magical and 2 is not, or 2 is and 1 and 3 are not.

Step 3: Test 1, 3, 4 together in the machine. The result being odd will point at 4 being magical, while being even will indicate 4 is not magical. The result being two or three will mean 1 and 3 are magical and 2 is not, while the result being zero or one will mean 1 and 3 are not magical and 2 is.

One flaw that I didn't like about this strategy is that it isn't memoryless, the tests I intend to do each step depends on the results of previous steps, and you can come up with memoryless strategies. However, if you look at the last path of my strategy: Test 1&2, then 2&3, then 1&3&4, that will work to be a memoryless strategy, you just have to analyise your results when you are done. I do not know of any strategy that is totally memoryless, that is, one that there is no path through it that you couldn't have just used from the start as a memoryless strategy.

Other things I don't know about this puzzle: how the heck to generalize it to N balloons and K measurements, so thats a thing to work on.

Subscribe to:
Posts (Atom)