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^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-1C₁). The next _NC₂ vertices each have N*(N-1)/_NC₂ (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-1C₂. As you can guess, the number of vertices going forward is always N*_N-1C_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-1C_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.

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 again 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 sum 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 smallest S possible. We are looking for two lists I will call L₁ and 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₁ and L₂ 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:

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:

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.

Magical Balloons

Alright, time to make a post so that I have at least managed to keep up 1 a year. I have a new puzzle Ben gave me ages ago, but I still haven't solved it and would feel wrong posting it when I have no ready solution. In the meantime, here is a puzzle I got from Tanya Khovanova's Math Blog:

You have 4 balloons (blue, red, green, and yellow, if you like) and some of them might be magical. You have a machine that you may put any number of balloons in and it will tell you how many balloons inside are magical. Find all the magical balloons using the machine not more than 3 times.

If you like you can also generalise, replace 4 with N and 3 with K, for which K can you solve the N balloon problem?

Modular Boxes

So, there is a bit of a follow-up to my puzzle last time I had intended to post, but then life got all busy on me, or I am just a slacker or something, but I noticed something funny about the puzzle last time.

When I had worked out that the elements of the 9th row of Pascals triangle (getting 1,9,36,84,126,126,84,36,9,1) and I noticed that they were all multiples of 3 (except for the 1's, of course) I instantly knew that this row must need a minus sign, without having to count and realize that the odd rows get a minus sign and the even rows do not. The reason is that if this particular row did not have a minus sign, then the statement "first box + last box = top box (mod 3)" would depend on how you mapped the boxes to the numbers. If blue=0, red=1, and green=2, then red+red would be green, but if blue=2, red=1, and green=0, then red+red would be blue. Clearly it cannot be the case that the solution to the puzzle depends on how you map the boxes to the numbers, so there must be a minus sign (and -red-red comes out to red in any mapping).

So does this mean something fundamental about the numbers that appear in Pascals triangle? Did I stumble on to some new property that I hadn't seen before? I couldn't quite see what it meant, really.

Talking about it with Ben, he noted that the statement "the answer comes out independent of how you map the colours" it actually a statement about linear functions made up of rows of Pascals triangle (so for example 1,3,3,1 makes 1w+3x+3y+1z). It must be the case that shifting all the variables by a constant shifts the answer by that same constant, and multiplying all the variables by a constant multiplies the answer by that same constant (and any 1-1 mapping of {red, green, blue} to {0,1,2} can be shifted to any other mapping by adding constants or multiplying by constants).

Since the linear functions in question are, well, linear, the multiplying by a constant thing is trivial. As for adding a constant, if we shift (w,x,y,z) to (w+a,x+a,y+a,z+a) then 1w+3x+3y+1z becomes 1w+3x+3y+1z+8a, where 8 is the sum of the elements of that row of Pascals triangle, and naturally -1w-3x-3y-1z becomes -1w-3x-3y-1z-8a. Since 8 mod 3 is -1, we can see that the expression with the minus sign is the one that shifts by exactly a when you shift all of its inputs by a.

This means that a row will shift correctly under this linear transformation if it has a minus sign when the sum of the row is -1 mod 3, and no minus sign if the row sums to 1 mod 3, and where will be a problem if any row sums to 0 mod 3.

Of course, we know the sum of a row of the kth Pascals triangle is 2^k, and that is (-1)^k mod 3, so this is exactly the property we needed, the rows alternate summing to 1 and -1.

I'm not sure anybody else found that as interesting as I did, since it was mostly about stuff that went on in my own head and ended with a fact that anybody who knows about Pascals triangle already knew, but I decided it was worth a post anwyay.