About Last Month (err...two months ago)
Again, I'll start by talking about the last post. There is an observation for the first problem that makes it much easier that nobody seemed to pick up on. If you are to apply one of the moves twice, it's the same as not doing it at all! It's clear that this is true if you immediately apply the second move after the first, but even if you apply other moves in between, it won't make a difference. If you want, see if this observation will help you solve the problem, otherwise, I'll finish the solution after the break!
Armed with this new observation, we note that there are only 25 possible moves we can make with the 3x3 frame and 16 with the 4x4 frame. This gives a total of 41 total moves. Since we have the option to either make or not make each move, this gives at most 241 positions that we can reach. However, there are 264 total colorings so there are many that we can't reach.
An interesting thing about this argument is that it's a non-constructive existence proof. We are able to show that there is some position that we can't reach without explicitly saying what that position is. It is a much harder problem if I give you two particular positions and ask if we can get from one to the other. Interestingly, however, if we pick two positions at random, the chances that we can get from one to the other are no better than 1/223, so we almost certainly cannot!
The second problem is another classic. The idea is to color the chessboard in the normal black-and-white checkered pattern and then note that each domino covers exactly one black and one white square. Since opposite corners have the same color, we end up with an imbalance of colors on the resulting board and so we can't possibly hope to tile it with dominos.
I asked to generalize the problem somewhat. Other than the case of dominos, I wasn't able to do much. I imagine somebody has written about this somewhere, but I haven't bothered to go check. However, I did realize that the general proof with dominos on an arbitrarily sized board with some (possibly none) removed squares is an old case of the famous Hall's Theorem from graph theory.
The reading from the wikipedia page might be a bit much if you're not used to graph theory, so I'll try to explain what it means in our case. Let S be a group of white squares and let N(S) be the set of black squares that are neighbors of a square in S. If N(S) has fewer squares than S, then we clearly cannot tile the squares with dominos because each domino covering a square in S must also cover a square in N(S) and so we can't do this without overlap.
Now, it is clear that for any such set S, we must have at least as many squares in S as in N(S) [also, this must be true if we let S be a set of black squares as well]. So it is clearly a necessary condition that |S| >= |N(S)| for all such S. What Hall's Theorem tells us is that this is also a sufficient condition. So if |S| >= |N(S)| for all S, then we will be able to tile the board with dominos.
The problems
Ok, I may or may not be easing up with these. I think last month was pretty tough, and these may also be tough, but I think they're a bit easier. Both problems are related for a couple of reasons. First, they're both probability problems. Second, they don't require a lot of calculation--just thinking about the problems in the right way should lead to a relatively simple solution. The first is one that I posted on the old site a long time ago. It was actually an extra credit problem for my graduate level prob/stats course--but don't let that scare you! The second one was inspired by between innings diversion at Target Field.
1. AMR and Daneeka's Ghost are playing a game where they flip 2n+1 coins. AMR wins if at least n+1 coins come up heads and Daneeka's Ghost wins otherwise. What are the odds that AMR wins?
2. Sean is playing a modified game of Bingo at Target Field. There are Eight squares on the board. Five of them contain the letters B,I,N,G, and O. The other three contain X's. Sean picks squares one at a time until he either spells BINGO or picks 3 X's. He wins if he spells BINGO. What are the odds that he wins?
I do know I wish I brought my calculator so I didn't have to deal with Wolfram Alpha's random parsing of equations.
Those are correct.
I must really be missing something. The intuitive answer DG gave makes sense, but I'm missing something in my math (Probability was never a strong suit. I don't think I ever actually took that class. I skipped from Algebra I to Pre-Calc, missing Geometry & Algebra II).
Oh, I mis-read it says "picks 3 X's". I was doing just 1 X to lose.
If those were the rules,
That's good to know I got that one right at least.
I'm thinking that I'm missing a wrinkle, but here are my first thoughts.
1.
2. Will have to wait. EAR gave me the "your sister flew here from AK and you're on the computer?" look.
Here's my solution for #2 that I cut off earlier:
Hmmm... Daneeka's Ghost got the complement of my answer and you said that it was right. I guess I did something wrong...
I think you missed a few cases in your two-strike BINGO list.
Probably. If I was doing this for an assignment, I would have checked all of the Strikeout cases to make sure I had covered all possible patterns.
Oops. Yeah, you got it right, I just looked over DG's answer too quickly. But there's a simpler way...see if you can figure it out!
Yay me!
Yep! That's it!
SBG,