Dominoes on a Board

Alright, time for a new puzzle. I have one I found recently I want to post, but some of the discussion first requires I post a puzzle I learned many years ago from my students in physics labs at UBC. It isn't a hard puzzle, which is why I never posted it, but the solution is very elegant, and it is one I like.
Consider an 8x8 chess board with two corner places deleted, in opposite corners. Attempt to tile this board with 2x1 dominoes. Prove or disprove whether such a tiling is possible.

Naturally such a tiling requires exactly (64-2)/2=31 dominoes to do this, as each domino will cover 2 squares and each square must be covered exactly once. Anyway, yeah, its not too tricky.

Josephus Solution

Time for the solution to the Josephus problem from last time. As is common for problems that are basically induction puzzles, its easiest to see what is going on by looking at a few cases.

First of all, you can just work through who wins in the cases N=1,2,3,4,5,6,7,8 and so on, you will see that the winners are 1,1,3,1,3,5,7,1. A bit of an interesting note is that all the winners are odd numbers, of course this note is instantly less interesting when you realize that all the even numbered individuals are killed on the first pass. Actually, if N is even, that brings up a good point, specifically that for N=2K you immediately reduce to the problem with K people, with #1 going first and a bit of a renumbering that person 2m-1 is now person m. But if this new K also happens to be even, then you can half it again. From here you can see that if the initial N is some power of 2, then person #1 will be the last one standing.

At this point, we can realize that whoevers turn it is when the total number of people is a power of two is the person who is going to win. Naturally, if the total is an even number, then that is person #1, but if N is equal to 2k+M, for some M less than 2k (or we would just use k+1 in the power instead), then once M people die, the next person on turn will live. Clearly since M is less than half of N, those first M people will die on the first pass around the table, so when M people have died it is the turn of person #2M+1.

This gives us the general solution for an arbitrary N. Let 2k be the largest power of 2 less than or equal to N, and let M=N-2k. The final person standing will be person #2M+1.

Josephus Problem

Ok, time for a new puzzle, I learned this one some time ago, it is a well known problem with a somewhat cool solution. This problem is well enough known as the "Josephus problem" that you can certainly just look it up along with its solution yourself if you hate my style of writing. The original problem involved N people who, having been captured by the enemy, are performing some sort of suicide pact, where they all kill eachother and there is one person standing at the end. There is a bunch of thematic bubble wrap to go with the puzzle, but I'm going to omit it just for the math. Anyway, here is the problem:
N individuals are in a circle, numbered 1 through N starting somewhere with 1 and increasing with each person to the left. Starting with person number 1, that person will kill the person to their left, and then the next person to the left will take a turn. This will continue until one person remains, which person is it?

Since that explanation is hard to do without an example, lets do one. Suppose N=5, then we start with 1 killing 2, 3 goes next, killing 4. 5 is next to take a turn, and 1 is to their left, so 1 dies and we only have 3 and 5 remaining. 3 goes next, killing 5 and the solution to the puzzle is 3.

So, in general, for an arbitrary N, who is the last person standing?

Then a year passed

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 relevant 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 2N 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-1C1). The next NC2 vertices each have N*(N-1)/NC2 (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-1C2. As you can guess, the number of vertices going forward is always N*N-1Ck, 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-1Ck, which is 1/N times the sum of the recriprocials of the Nth 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.