Prime

But of course! I forgot to take those into account. Nice trick, Prof. T!

If we have this discussion in the open, can someone borrow our findings and make them a subject of their PhD thesis in Math or Computer Science? Would we feel cheated? I don’t quite follow Bona’s "__X" notation. At any rate, (N+1)x(N+1) square does not have to be based on ay NxN square. I see 14 variations – not 6, to paint 3x3 board with 3 hand-painted squares. Here is an illustration: The diagonal path provides only two variations, the other 3 paths – 4 variations each. (Use 90-degree rotation.) The two paths at the top could be based on 2x2 painted board, the other two paths – could not. First, I thought my variation on this puzzle could be solved by determining the order of the algorithm that I suggested (post #28). However, that algorithm can not produce all possible combinations (see illustration, post #31). Suppose, we have devised an algorithm that produces all possible combinations of 8 hand-painted squares, which we seek. Then we’d have to determine, how many duplicate solutions it produced. And figuring out the order of algorithm (how many solutions it produced) could be non-trivial task too. Bona already noted 90-degree rotational symmetry (post #35). Symmetry could play an important role in solving the problem. I’d also like to point out mirror symmetry. Regard b1 square. It has rotational symmetries: (b1, a7, g8, h2) and those have mirror symmetries: (b8, h7, g1, a2). Logically, those squares are similar. If you followed, what I have written here, you may be able to deduce that I am pretty much clueless with respect to the solution of my own puzzle. However, I can figure the upper boundary: the answer is less than combinations of 8 from 64.

I would rephraze the question in your problem as following: "Will you bet an even money, that I will not guess the Final Total?"

The first answer that jumps to mind is 100/991.

When you see two dice showing the reverse of each other -- you still have only 1/2 chance of guessing. E.g. (5,2)-- their sum before flipping could have been either 10, or 4.

I see how your probability is 7/12, but not 2/3.

Some people may ask you for a proof of your proposition (1). To clarify, you mean that each newly painted square removes two borders from the outside perimeter, while it can add at the most two of its remaining borders to the newly formed perimeter.

I must not attempt proofs after midnight. My proof in post #27 suffers from the very flaw, I warned about. It picks a certain method of selecting squares that would paint an entire board. However, that method does derive all possible variations. Here is an inductive/recursive proof that Bona, probably, had in mind: Here is an interesting set of hand-painted squares which will paint the entire board. Yet it cannot be derived using my algorithm from post #28. Another correction: there are not 8 variations (as I said in post #29), where 3x3 square could be constructed from 2x2 one, but only 6. And there are total of 14 variations to choose 3 squares which would paint a 3x3 board. My puzzle stands: How many different sets of 8 hand-painted squares, which would paint the entire board are there?

It can be done in 7.

And here is a next level puzzle that occurred to me: Suppose that you have 8 blobs of magic paint and you throw them at the board using your random paint sprayer. The random paint sprayer guarantees that each blob will paint exactly one different square on the board. What’s the probability that the board will get painted completely?

I'm not so sure about that... Inductive proofs are treaturous and often fallacious. If you want to reuse NxN painted square in prooving your case for (N+1)x(N+1), consider following example. There are but two minimal ways to paint 2x2 square -- use one diagonal, or the other. There are 4 different ways to enclose already painted 2x2 square into a 3x3 one. Thereafter, you can paint just one square in the empty corner of 3x3 and the 3x3 gets painted entirely. HOWEVER, aside from those 8 variations, there are other possibilities. Paint in any 3 corners of 3x3 square and it gets painted from head to toe. THEREFORE, how can you apply inductive proof if minimal painting of N+1 square does not need to rely on painting of any of its subsquares of size N?

For an in-depth discussion and a maximized version of weighing problem, see my "Ultimate weighing problem" topic on this forum.

And here is a simple procedure for choosing a set of 8 hand-painted squares which will paint the entire board: For example, using that algorithm you may choose squares as following: c1, c3, b4, a5, e4, g5, h6, and h8. I believe you can not create a situation where you would not be able to paint the entire board with 8 hand-painted squares using that algorithm. I can't think of a formal proof yet. That's a new puzzle.

Here is a proof (semi-formal) that you can not paint 8x8 board with less than 8 initially magic painted squares. Academically inclined logician may find that proof incomplete, but I think it’s convincing enough.

I never said the distance was the same. On the contrary, I thought the distance they traveled was different, "how far" was the same. But Slomic set me straight and showed most convincingly that not only the "how far" was the same, but the distance as well.

And here is the illustration of the solution:

Oh, my... I missed that possibility. I conceede, this solution is more precise, than what I have suggested.

Suicide has the solutions to both puzzles. I was given a “classical” variation of that problem 40 some years ago by my grandfather, who got it from his grandmother, when he was a little kid. There are 9 like bags, one with gold and 8 with sand. The bags with sand weigh the same, while the bag with gold is slightly heavier. Find the bag with gold with 2 weighings, or less on a balance-scale. To solve, you put 3 bags into one pan, 3 into another, leaving 3 on the side. If one triplet outweighs another – that’s where we have to look for gold. If they weigh the same, the gold is in the triplet on the side. Then we weigh one bag from the isolated triplet against another, leaving one bag on the side. The problem is solved. It works for powers of 3, like 27 bags in 3 weighings, 81 in 4, and so on. What’s interesting, the problem works for any mixture of heavy/light potential faults. For example, you have 3 coins and you know that only one is counterfeit, and you are also given that if it is the first coin, then it lighter, otherwise – it is heavier. (LHH set). Then you drop one potential heavy coin into one pan, another potentially heavy on the other side of the balance scale. And the heavier side is the counterfeit, or if they balance, then it must be the coin on the side and it is lighter. It works for any combination of H/L for any power of 3 for the number of coins. For example, if you have 9 coins with only one counterfeit and their potential faults are: (LLLLLHHHH). Then you weigh HHL against another HHL leaving the remaining LLL on the side. And on the second weighing the problem is solved. You can try it with any other combination to satisfy that it works. Now to 3**N discussion. In my example with 4 coins (post #15) there are 9 different cases, not 12. There is only one case of all four coins being true. Much like when you roll a pair of dice, there are two variations to roll (5,6), but only one – (6,6). But forget about all coins being true for now. Let’s say, one of them has to be counterfeit and is either heavier, or lighter. So there are 8 different cases for 4 coins, right? However, you still can not solve them in 2 weighings. The catch here is whether it is possible to exclude enough cases on a given weighing, so that you remain within 3**N boundary for the remaining N weighings. That is not always possible, as my example with 4 coins/2 weighings illustrates. In my “39 in 4” problem, the tricky situation was 13 coins of undetermined fault with 3 weighings left. The trick was to weigh 9 coins from that set, not 8. For that you’d have to use a reference (true) coin, which was available at that point. As Suicide had found (post #9, spoiler 2). I think this discussion has beaten the balance-scale type problem into the ground. We could stomp on it a little more and then put it to rest. No other balance scale problems shall be posted, unless you find something new, clever, and different therein. P.S. Of course, the Weight Problem of Bachet de Meziriac, published in 1624, where a merchant drops a 40-pound weight, which breaks into four uneven pieces, is different and more interesting.

The puzzle intended that both trains leave and arrive at the same station -- a round trip. But the wording came short of making that implication sufficient. Although being any more specific, would be a giveaway. As a simple algebra problem, it would not be a puzzle.

And thanks to Rookie1ja and Gambit for showing how some other variations submitted here were not a solution.

Congratulations Normdeplume! That's the solution and the only solution!

I thought I gave plenty of examples of additional factors. See my post (#18). Most notably, my use of Amber's bosom.

Not at all. Black made their move after each White's move. Your task is to find those moves. White Black 1. f3 -- ? 2. Kf2 -- ? 3. Kg3 -- ? 4. Kh4 -- ? checkmate Replace question marks with the moves for Black.

You don't have to be a chess player to solve this one. But you have to know the rules of chess. From starting position White moved 1) pawn f3, 2) King f2, 3) King g3, and 4) King h4. Find the moves for Black so that they checkmate White King on their 4th move. All moves must be legal. I gave this puzzle to many a chess master, and they all had very hard time solving it.