bonanova

Pencils down. Discussion time over. For the believers in the utility of clever play, choose a convenient number of cards (e.g. pick a small number and enumerate the cases) and quantify the advantage that can be gained. For the nay-sayers, give a convincing argument that all the factors already discussed (permission granted to peek at spoilers) exactly balance each other out.

@plainglazed (first) and @plasmid (with a formula) both have it. Both posts show how to get the answer, with the formula garnering "best answer" designation. Nice job both.

Precisely. If every room houses a green man, new customers have no place to sleep. This does not work: { g1 g2 g3 ... gi .... b1 } <=> { r1 r2 r3 ... ri .... rinf+1 } Do we want another guest? We can't assign gi to ri. This does work: { b1 g1 g2 g3 ... gi .... } <=> { r1 r2 r3 r4 ... ri+1 .... } gi is no longer in ri.

The way it's set up, he can say Stop just once.

Yes. That’s a win for white

OK so I was a kid once, back in the 40s and 50s, and we had this game called Pegity. It had a board with a 16x16 array of holes, and in turn each of 2-4 players inserted a peg of his own color into a hole. The object was to get 5 pegs of your color in a row: vertically, horizontally or diagonally. Not every game was won: similar to tic-tac-toe, you could run out of holes. But with only two players, there was usually a win. For simplicity let's shrink to a 9x9 board, mark the holes like in chess (A1, E7, etc.) and say that after O and X have each made three moves we have this position, with O to move: 1 2 3 4 5 6 7 8 9 A + + + + + + + + + B + + + + + + + + + C + + + + + + + + + D + + + + + + + + + E + + + + O + + + + F + + + O + O + + + G + + + + X + + + + H + + + X + X + + + I + + + + + + + + + With best play by both players, how soon can O win? Use chess notation (naming the holes, in two columns) to list the moves.

@CaptainEd shuffles a standard deck of playing cards and begins dealing the cards face up on the table. At any time @plainglazed can say Stop and bet $1 that the next card will be red. If he does not interrupt, the bet will automatically be placed on the last card. What is the best strategy? How much better than 50% can @plainglazed do?

That is amazing. And you've shown that 1 fewer than a power of 2 is the optimal value for n. Can you reduce it to only q memorized strings, and the success rate to (q-1)/q, where q is the highest power of 2 less than or equal to n? (Purposely leaving this un-spoilered, cuz this is a tough problem.)

Yup. And a bit of possibly helpful thinking: Edit: The math gets a little demanding here. Integrals and stuff.

Yeah, I hate annoyances, too...

Can you think of a reason?

OK I think I just found your first blue man.

@aiemdao - Nice solve. @plainglazed - Nice puzzle.

@CaptainEd brilliantly answered a puzzle that I mis-worded into a much tougher one. Nice job. Here's the puzzle I had intended to post: You have just lost your 143rd straight game of checkers and have vowed never to play another game. To confirm your vow you decide to saw your wooden checkerboard into pieces that contain no more than a single (red or black) square. With each use of the saw you may pick up a piece of the board and make one straight cut, along boundaries of individual squares, completely through to the other side. You wish to inflict as much damage as possible with each cut, so you first calculate the minimum number of saw cuts needed to finish the job. And that number is ... (spoilers appreciated.)

Isn't this fun? The { real numbers } between 0 and 1 comprise two infinite groups: { rationals } and { irrationals }. Rationals (expressible as p/q where p and q are integers) are countably infinite. We can order them, by placing them in an infinite square of p-q space and drawing a serpentine diagonal path. But the irrationals are not countable. The cardinality (notion of size used for infinite sets) of the rationals is called Aleph0 and for the irrationals (and reals) it's called Aleph1 or C (for continuum.) So first off, what we can do with the { numbers } between 0 and 1 depends on { which numbers } we want to deal with. Next, there's a problem that points are not objects that can be moved from place to place, as coins can. Points are more descriptions of space than of autonomous objects. If 0 and 1 are on a number line, the location midway between them is the point denoted by 0.5. It can't be removed. (We could erase the line, I guess, but that would not produce an interval [0 1] devoid of numbers, either.) But we can finesse this matter by "painting" a point. Kind of like what we did when we inscribed a number on each coin. Painting does a little less - it puts a point into a particular group or class but it does not distinguish among them. We can tell coin 2 from coin 3 and also distinguish both from a coin with no inscription. Two blue points, however, are distinguishable from unpainted points, but not from each other. But for our purpose here, painting is actually enough. Since the { rationals } are countable, we can paint them, in sequence, and if we do that at times of 1, 1/2, 1/4 .... minutes before midnight, all the rationals between 0 and 1 will be painted blue by midnight. (I don't know of a similar scheme for completing uncountable task sets, so the irrationals alas must remain unpainted.) Next, instead of asking whether all the points in [0 1] were removed, we can ask, with pretty much the same meaning, whether at this point the entire interval [0 1] has been painted blue. It should be, right? After all, between any two rationals lie countably infinite other rationals. So the paint must have covered the entire interval, right?. Well ... actually ... the answer is counter-intuitively No. And this is because even though the { rationals } are "dense" meaning there are no "gaps" between them, as noted above, the { irrationals } are even "more dense." That is, between any two irrational numbers there are uncountably many other irrationals. That means, for every blue point we created in the interval [0 1] there are uncountably many unpainted points. We can't magnify the line greatly enough to "see" individual points, but "if we could," if we were lucky enough to come across a single blue point we'd have to pan our camera over uncountably many unpainted points before we saw another blue one. In measure theory, the measure of the rationals over any interval is zero. The measure of the irrationals over [0 1] is unity. So what of our quest of emptying [0 1] of points? It's the same as our quest to paint [0 1] blue by painting all the rational numbers in that interval. (Reminding ourselves that there were too many irrationals to paint one at a time.) Turning again to measure theory, the measure of the "blueness" of the interval would be zero. That means we would not see even the hint of a faint blue haze. Back to our "empty the interval by removing the rationals" quest, Nope. [0 1] would not be empty: uncountably many points (numbers) would remain.

This is a nice puzzle.

That is what infinity does to our brains. Al retains coin 2 at step 1. But Al discards coin 2 at step 2. What is true for coin 2 is true for every coin. Every coin has a scheduled pre-midnight discard date. So "what happened to the N coins not discarded?" If N is finite, then it's not midnight yet, and the box does in fact contain coins. We have to be patient. The process has to run its course. And, specifically, {coin n+1} will be discarded at step n+1, at time t n+1, prior to midnight. So after midnight, it will be gone. Along with all the others. Every coin, identified by the number engraved on it, has a well-defined pre-midnight discard date. But then if we're Bert, who never schedules the discard of an odd coin, we'll have a ton of coins.

I would dispute your first point. I can't immediately think of a scenario that permits a discard which will not eventually happen given an infinite number of opportunities. Can you provide one? We agree on the second point. My previous post answers precisely that question.

@CaptainEd Wow. Not the answer I had in mind -- a much better one! Nice. Bonus (slightly modified) version. Same question, but this time no cut may end short of the opposite edge. It must go entirely through the piece being cut.

@harey Hilbert's hotel tells us not to treat countably infinite sets the same way we treat finite sets. There is no 1-1 correspondence between { 1 3 5 7 9 } and { 1 2 3 4 5 6 7 8 9 10 } as there is between the (infinite set of) { odd integers } and the (infinite set of) { integers.} Hilbert's hotel always has room for more. Completion (of an infinite set of tasks) is another tricky concept. If we number some tasks 1 2 3 ... and there is no final integer, how can there be a final task? And if there's no final task how can we complete infinitely many tasks, or describe the state of things after they have transpired? We finesse that point with a 1-1 correspondence of event times to the terms of an infinite series, 1 1/2 1/4 1/8 ... 1/2^n ...., which (conveniently) converges. We pack a countably infinite set of events into a time interval that ends at midnight. "Completion" is cleverly accomplished in two seconds. It's non-physical enough that it never could happen, but we can reasonably discuss the post-midnight state of affairs nonetheless. We have two countably infinite sets, {coins} and {events}. At each event, two coins are added to a box and one coin from that box is discarded. So, of the two added coins, at least one is kept. We know that at midnight the entire set {coins} has entered each box, and some (proper or not) subset of them has been discarded. The key question is this: can a coin that is kept at a certain event ever be discarded at a later event? For Al, the answer is yes. Al always discards his lowest coin, so at each event time ti he discards coin ci. Thus eventually that is, upon completion of the infinite set of tasks, every coin that is initially kept is later discarded. At midnight no coins remain. Al's box is empty. For Bert the answer is no. Bert discards the highest-numbered of his coins, and that is always the even coin that he just received. At no event is Bert ever scheduled to discard an odd coin. Every odd coin that enters Bert's box is kept, and it stays there forever. Bert's box contains a countably infinite set of coins. For Charlie the answer is ... well ... um ... actually ... I guess ... yeah, but it might take an infinite number of events for it to be discarded. Well it just so happens that we have an infinite number of events that follow the keeping of every one of Charlie's initially kept coins. So, yes. All of Charlie's coins that are not immediately discarded are eventually discarded. At midnight, Charlie's box is empty.

That would not be permitted. The OP says with each use of the saw you may pick up one piece of the board and make a straight cut.