BrainDen.com - Brain Teasers

bonanova

Moderator

6962

65

1. Ants on a checkerboard

@CaptainEd I agree with your reasoning but my numbers different enough for me to recheck them. @plasmid The fact you're that close to the Captain, I suspect my numbers are the incorrect ones. What I have convinced myself of, though, is that
2. Emergency! Lynch Mob coming. Can you help?

@Molly Mae Consider that the sheriffs are simply talking to each other, using statements like, "my pair of suspects has this property: (describes property.)" Would generating and using common key agreements be doable with such low-complexity statements?
3. Line segments of two types

Good start, but there are more.
4. Tiling a hexagon

True, and that is a proof by construction, getting you a point. There is an unexpected proof that comes from looking at the hexagon from a slightly different angle, literally. Can you find it for the win?
5. Painting a checkerboard

Can you prove that's minimal? Can you think of a necessary property for your red squares?
6. Pairing the points

For each n it's a fresh start. So really it's just one question: For any (every) n, can n red dots and n blue dots be joined pairwise with n line segments no two of which intersect?
7. Order the cards

You have three cards in front of you labeled in some order 1, 2 and 3, and three card-sized bins labeled with a letter that signifies Left, Middle and Right, in the order shown. The cards, all of which remain face up, have been placed at random in one or more bins, in such a way that, if any cards are stacked, only the top card is visible. And, if only two cards are visible, one cannot tell which bin holds the hidden card. +-----+ +-----+ +-----+ | | | | | | +---| L |---| M |---| R |---+ | | | | | | | | | +-----+ +-----+ +-----+ | +---------------------------------+ You are to devise an algorithm that ends with all cards in the L bin with 1 on top and 3 on the bottom, in a bounded number of moves. Each move in the algorithm consists of taking a single card from the top of one pile and placing it on the top of another (possibly empty) pile. An independent observer will keep track of things and will signal completion. Your algorithm, on the other hand, may not keep track of things. Each move it makes must take its cues only from the visible information at each point in the process. Specifically, a move cannot depend on any invisible cards, its previous move or the number of moves it has made. Further, it must be able to begin from a random starting point. A move might take the form "If a 2 is visible, move it one bin to the right." In that case, the 2 card would move to L if it happened to start in R. In that sense, the configuration functons as ring, with "move to the right" meaning CW, and "move to the left" meaning CCW. To restate: For any configuration with one, two or three visible cards, distributed in any order in L, M and R, your algorithm must specify the next move to make. And since your algorithm can't distinguish an L stack of 1 2 3 from 1 3 2, it will be told when it has (successfully) completed.
8. Emergency! Lynch Mob coming. Can you help?

There was a killing last night at the *gasp* Double-R-Bar Ranch out between Dry Gulch and Tombstone. Each town's sheriff has investigated a list that contains the eight men who are the only possible suspects. And kudos to them both, because already each sheriff has a short list of just two suspects. They intend to compare their lists via telephone call and, if they agree on exactly one person, an arrest will be made. Unfortunately some of the town-folk know the names of the original eight suspects, and they instead intend to lynch the culprit, if they can identify him. Wait, there's more. They have tapped the sheriffs' telephone. If, by listening to the sheriffs' conversation, the mob can identify the culprit with certainty, the bad guy will be lynched before he can be arrested. How can the sheriffs, who have never met*, discuss their findings, opaquely to the eavesdropping lynchers but with clarity to each other, so that the mob is left in the dark, while both sheriffs end up knowing the culprit -- and thus allow either sheriff to make the arrest? *Specifically, they have no commonly-held information to use as an encryption key. (If something is not clear, please ask.)

10. Painting a checkerboard

Hi WorldDev and welcome to the Den.
11. Green and Yellow hats again, but harder

I'm missing I think I understand your analysis, but wonder how you would implement this. Given they sit in a circle and guess (or pass) privately,
12. Painting a checkerboard

You are given a huge white nxn checkerboard and tasked with painting it red, one square at a time. You find the task tedious, so you quit after painting m of the squares red, and then you give the job to your assistant Bob. Bob is not a workaholic either, so "compassionately" you tell him he only needs to paint a square when he finds that it has two sides that border with red squares, regardless of who painted them. That is, Bob cannot quit painting until no white squares having two red borders remain. Clearly by wisely choosing your squares, and if m is large enough, you can compel Bob to paint all of the remaining squares. Clarifications: To border another square an entire side must be shared, not just a corner. If two red squares touch diagonally, Bob must paint the white square(s) that they both share a side with. If m = 1, or if you've painted squares sufficiently distant from the others, Bob won't have to paint any squares. Prove there is a least amount of work you must do (smallest m) that makes Bob complete the job.
13. Tiling a hexagon

A regular hexagon is divided into 2n equilateral triangles. Pairing triangles that share an edge produces diamond shapes with three distinct orientations, as shown. Prove that any n-diamond tiling of the hexagon will use the three types in equal numbers.
14. Pairing the points

2n distinct points in the plane, no three of which are collinear, are colored red or blue in equal numbers. Is there a red-blue paring of the points that permits the pairs to be joined by n line segments with no crossings?
15. Line segments of two types

Six line segments serve to connect pairwise any four points in the plane, no three of which are collinear. It's clear that no placement of the points permits all six to have the same length. How many unique placements permit the segments to have only two distinct lengths? Example:
16. Green and Yellow hats again, but harder

In this puzzle, they're not in a line.
17. Green and Yellow hats again, but harder

In games of this type every guess, on average, is wrong 50% of the time. For the 3-prisoner strategy, if we count the number of guesses made in all 8 cases, we find six of them are correct and six are incorrect. We "rescue" the other cases, (when both colors are seen, and no guidance is available,) with the "Pass" option. The same is true in the previous G-Y puzzle. The difference is that in the first puzzle every wrong guess produced a fatality, so survival also was only 50%. In the 3-prisoner case here, death uses up three wrong guesses (while survival still requires only a single correct guess.) We "packed" the incorrect guesses into the fewest possible of the eight cases and thus raised survival to 75%. But since 2x3 = 6x1 randomness still got its due. The 3-prisoner solution is trimmed-down version of the n-prisoner strategy. Have fun...
18. 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.
19. Best words

Have fun with this one. A bull stands in a pasture, unaware that he has just swallowed a time bomb that is due to explode in five minutes. Which word best describes the situation? Awful Abominable Dreadful Shocking Five minutes have passed, and all that's visible from the above scene is a sizable hole in the ground and scraps of bone and flesh. Which word best describes this situation? Amazing Silly Messy Noble
20. Where are we?

What shall I do, Gerry? Asking nutty questions can be most annoying A gold key is not a common key. Horace tries in school to be a very good boy. People who drive too fast are likely to be arrested. Did I ever tell you, Bill, I once found a dollar? John came late to his arithmetic class. I enjoy listening to music at night.
21. The word that won't quit being a word

Can you write down a 9-letter word that permits you to erase it, one letter at a time, such that after each erasure a valid (English) word remains? (As implied, the letter order remains the same throughout.) Clue: Example:
22. What's the only word?

Here are nine words before, after, and in-between which only one word can be placed that gives ten different meanings to the sentence. The word is used only once, in only one space at a time, to obtain the ten different meanings. What's the only word that works? _____ TOM _____ HELPED _____ MARY'S _____ DAUGHTER _____ CLEAN _____ MARY'S _____ PARROT'S _____ CAGE _____ YESTERDAY _____.
23. Circles covering a rectangle

@Molly Mae Fair question.
24. Random triangles in a circle

Yay! And does it seem strange to anyone else that something 7% the size of the circle on average covers the center 25% of the time? (My red herring was soooo totally ignored. Good job for doing that.)
25. Green and Yellow hats

Ah!
×

• Activity

• Riddles
×
• Create New...