BrainDen.com - Brain Teasers

# bonanova

Moderator

6893

64

1. ## Coin hunt

Thinking. Meantime I'll call your 10 minutes of cat flight and raise you 25 minutes of Roomfull of Teeth, as they explore new uses for the human voice, which you might actually enjoy.
2. ## Next card is Red

Let there be n red cards and n black cards.
3. ## When midnight strikes

I just re-read this, and my reply wasn't totally responsive. But let's see whether Charlie even makes us address this question. Remember, Charlie doesn't get any more coins to deal with than Albert did. If we believe Albert's box (can) get emptied, we can't say discarding Charlie's coins is an impossible task. We simply have to show that none of Charlie's coins is able to "hide" indefinitely, in hopes of hearing the clock strike while still being in the box. Charlie's coins are not inscribed, so we have to treat them collectively. We can't trace the destiny of any individual coin, as we could in Albert's case. Can we still show they are all eventually discarded, and not face the task of depleting an infinite set along the way? We claim that we can do that. We can refer to each of Charlie's coins as "one of the coins that entered Charlie's box at event n that was also not discarded at event n." The n coins in his box at any such time are indistinguishably equivalent. Their "fate" is countably infinite events with non-zero probability of being discarded. We have shown in a preceding post that each of Charlie's coins has a survival probability of k/n where k is the event when the coin entered his box and n is the current event number. k is fixed. n becomes infinite. The probability of the coin that entered Charlie's box at event k still being in his box after midnight is limit (n->inf) k/n = 0. Since this holds for each k it holds for each coin that entered Charlie's box. Using other words, every coin that is in Charlie's box at midnight is not a coin that entered Charlie's box. A contradiction. Also, at no event time did Charlie have an infinite number of coins.
4. ## When midnight strikes

At an ever increasing pace Al, Bert and Charlie have been receiving into three identical boxes of limitless capacity identical pairs of silver coins engraved with the integers 1, 2, 3, 4, ... etc. These events occur on a precise schedule, each box receiving Coins marked 1 and 2 at 1 minute before midnight Coins marked 3 and 4 at 1/2 minute before midnight Coins marked 5 and 6 at 1/4 minute before midnight Coins marked 7 and 8 at 1/8 minute before midnight etc. But they were instructed at each event to remove a coin from their respective boxes and discard it. After some thought, Al decided each time to discard his lowest-numbered coin; Bert discarded an even-numbered coin; and Charlie thought what the heck and discarded a coin selected at random. Regardless of strategy, at each event the number of coins in each box grew by unity, so that after N events each box held N coins. Needless to say when midnight struck their arms were infinitely tired, but it was a small price to pay for infinite riches. But tell us, now, whether their expectations were met. Describe the contents of each box at midnight.

6. ## Pegity - white to win

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.
7. ## Next card is Red

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.
8. ## Traffic jams

@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.
9. ## Traffic jams

At 5-second intervals, 1024 automobiles enter a straight (and otherwise empty) single-lane highway traveling at initial speeds chosen at random from the interval [50, 70] miles per hour. Cars may not pass nor collide with other cars. When a slower car is encountered, a car must simply reduce its speed, and for the purposes of this puzzle we may consider the cars in such a case become permanently attached, traveling at the slower car's speed. Eventually there will be N clusters of cars. What is the expected value of N? (Equivalently, what is the expected cluster size?)
10. ## Modified checkerboard destruction

@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.)
11. ## A big, big, big hotel

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.

13. ## Next card is Red

The way it's set up, he can say Stop just once.
14. ## Pegity - white to win

Yes. Thatâ€™s a win for white
15. ## Green and Yellow hats again, but harder

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.)
16. ## Green and Yellow hats again, but harder

As promised, a harder hat problem. Prisoners are seated in a circle so they can see all the others. This time the warden flips a fair coin for each prisoner and gives him a yellow or green hat, accordingly. Once all the hats have been placed, and have been seen by the others, prisoners are taken aside singly and given the opportunity to guess the color of his hat. And if instead he chooses not to guess, he is permitted to pass. Now comes the bad part. Unless at least one prisoner guesses, and all the prisoners who do guess are correct, all the prisoners will be executed. That's right, survival requires perfection from every prisoner who guesses his color. Prisoners decide on a strategy beforehand, and after the first hat is placed there is no further communication. Clearly, there can be a single "designated guesser" who ... just ... guesses a color. Half the time they all survive. But what kind of a puzzle would that be? Yes, incredibly, the prisoners can do much better. How? Maybe thinking about a three-prisoner case will answer that question. Once you're convinced they can do better than a coin toss, find their best strategy.
17. ## Baggage on a conveyor belt

Yup. And a bit of possibly helpful thinking: Edit: The math gets a little demanding here. Integrals and stuff.
18. ## A big, big, big hotel

Yeah, I hate annoyances, too...
19. ## Obtuse triangles in a circle

What fraction of triangles in a circle are obtuse?
20. ## Modified checkerboard destruction

Can you think of a reason?
21. ## A big, big, big hotel

OK I think I just found your first blue man.
22. ## Worth the Weight

@aiemdao - Nice solve. @plainglazed - Nice puzzle.
23. ## When midnight strikes

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.

25. ## Worth the Weight

This is a nice puzzle.
×