bonanova

Yes and yes.

You've just found a neat way to place points uniformly randomly inside a unit circle: simply place points at random inside a circumscribed square -- x and y uniformly chosen on [-1, 1] -- and ignore the points near the square's corners that are outside the circle. There are other ways, but this works, and it's simple to do. And why are you excited about this? The reason is that you've often wondered about the expected size of randomly drawn triangles inside a unit circle. And now you can find out. You sequentially place a million sets of three random points in the circle, calculating (and then averaging) the areas of the million triangles they define. And you find something pretty amazing: the million triangles had an average area that is only ~ 7.4% of the circle's area. You also note that the median area was ~ 5.4%. OK, so that's a fairly long set-up for a pretty short puzzle. Read on. You tell a friend about how amazingly small random triangles constrained by a circle are, and he replies with a question of his own: "That's cool," he says, "but I wonder what fraction of those triangles cover the circle's center?" You admit that was a piece of information that you did not take note of. "Oh, that's OK," your friend replies, "I think I can tell you." What answer did your friend (correctly) come up with?

Hmmm. OP does not rule out movement. But it does rule out communicating. So let's say that if the prisoners want to be at some preferred location in the room, that's permissible. But their chosen location can't be in any way influenced by hat color -- i.e., all movement must occur before the hats are placed.

In a long hallway, 100 prisoners are given red or blue hats, whose color only the other prisoners can see. At a signal given by the warden the prisoners must walk single file through a door and take their places inside a large room. The room is circular and its wall, ceiling and floor are featureless. Nothing is said, nor are any gestures made to prisoners as they enter the room and take their place. When the last prisoner has taken his place the warden inspects the configuration of their hat colors. If the colors form two monotonic groups separable, say, by some straight line, then all the prisoners are freed. If their hat colors instead are intermingled, they are all executed. Prisoners are allowed to discuss strategy before receiving their hats. What is their fate? Let's see, what else? Oh ya, they can't just pass their hats around. They're super-glued on their heads. Ouch. And no one has a magic marker to ... uh ... you know, make a line ... or anything like that.

Nope. They act on what they see. Sorry.

Here's a toughie. A room full of prisoners is given hats, whose color only the others can see. And just to be different, let's say they are yellow or green. No communication is permitted. At a signal, given by the warden, the prisoners must simultaneously shout out the color of their own hat. Those who guess wrong are subsequently executed. Beforehand, the prisoners meet to determine a strategy -- a set of rules, not necessarily the same for each prisoner -- that will guarantee the greatest number of survivors. As an added wrinkle, the warden may attend the meeting and then use his knowledge of their strategy when he chooses the colors of their hats. If there are 100 prisoners, how many can be assured of surviving?

This is another puzzle where precise wording is important -- I'll try to get it right, but if anything is unclear, please ask ... I'll start out by saying that all the circles in this puzzle have the same radius, the aspect ratio of the rectangle is not specified and does not matter, and its size, relative to the size of the circles is only indirectly implied. Only the constraints stated in the puzzle should be assumed. I've drawn 17 circles that at least partially overlap a rectangle. Their centers all lie within the rectangle. None of the circles overlap or even touch any of the other circles. There is no room for an 18th circle to be added to the group. That is, the circles are drawn in such a way that even though there is space between them, it is impossible to draw another circle whose center lies within the rectangle that does not at least partially overlap one of the first 17 circles. That is all you know about the relative sizes of things. And it is enough information to answer the following question: First, let's erase the circles that I drew. Then I will paint the rectangle red and give you a large supply of opaque white circles. What is the smallest number of circles you will need to completely cover the rectangle? (so that no red will be showing.) The centers of the circles, again, must lie within the rectangle, but now, of course, the circles can overlap each other, Edit: The puzzle can be solved as stated, but in order to guarantee the solution is the absolute smallest number, the following constraint is added to the original placement: The 17 circles were drawn as densely as possible without overlap. Thanks to @Molly Mae for raising this point.

So when OP says "build exactly one car a day (no more, no less)" it means you can build any number of cars in the interval [1 2) because "and to be clear a partial car is as good as not building a car." So if you built 1 1/3 cars on the first day it would count as "exactly 1 car," because it would pass 1/3 of a car to the second day, when you would then have to build any number of cars in the interval [2/3, 1 2/3)? In general, is it correct to believe that at the end of every nth day you must have built [n, n+1) cars, except for n=7, after which you must have exactly 7 cars?

I'm not understanding something about two shifts building exactly one car. A whole car (in one shift) or two half-cars (in two shifts) seem to be the only cases. Maybe spoiler one other possibility as a means of explaining? Thanks.

It must be symmetric about the NW-SE diagonal, so your figure show all the cases you computed. Nice, btw. Hint

@Thalia,

@plasmid Does the program imply a proof that it can always be done? Or is it a statement that no counterexample has yet been found? A proof could be a repeated procedure which after each application reduces the smallest number of beans on a plate. Does your algorithm always reduce the number on place C?

@ThunderCloud Nailed it. @Izzy Honorable mention

I think it boils down to that, but how to justify doing it?

@Izzy Yes.

@Izzy Very close. @Donald Cartmill OP restricts what each prisoner is allowed to say: Each prisoner must guess the color of his own hat, without having seen it, by saying one of the three colors

@Izzy As you say, the distribution is surprising. To be certain of this expected attendance at the smaller party, you might want to ...

No spoiler needed: There are only three no-win-after-13-digs possibilities: BBBB BBB GGGG RR Win on dig 14 with G or R or H = 60%. Win on dig 15 with B = 40% BBBB BBBB GGG RR Win on dig 14 with R or H = 30%. Win on dig 15 with B or G = 70% BBBB BBBB GGGG R Win on dig 14 only with H = 10%. Win on dig 15 with B or G or R = 90%. Their relative occurrences were not saved in the simulations, so it's a bit uncertain how weight these cases when taking an average. But if they are equally likely, the relative dig-14 and dig-15 wins would be exactly 33.33...% and 66.66...% That is, Win 15 would be twice as likely as Win 14. For the simulations, the last few probability estimates are the least precise, because they are averages of fewer cases. In particular, the probability of going beyond 13 digs is only 5.6%, so that out of 2 million total cases, only about 112,000 14-digs or 15-digs cases were averaged. Those relative win probabilities are 35.7% and 64.3% respectively. I'll point out that the proportions of needed B G R and H (8 4 2 1) are similar to their occurring probabilities ( 40% 30% 20% 10% ). That partially justifies an equal-likelihood assumption. But the proportions do differ, somewhat. In particular, B is needed 8/15 of the time but occurs only 40/100 = 4/10 = 6/16 of the time. This fact might well make a missing-B-after-13-moves (Case 1) the most likely case of the three. That case has the highest win-14 probability. So we might expect an upward bias on the win-14 probability. The simulation suggests that is the case.

One hundred prisoners stand in a straight line seeing those visible to them only from the back. You get the picture, back guy sees 99 others, front guy sees no one. They are fitted, one each, with a hat, whose color is uniformly randomly Red, White or Blue. Each prisoner must guess the color of his own hat, without having seen it, by saying one of the three colors, and he is executed if he is wrong. The guesses are made sequentially, from the back of the line to the front. The guesses are not identified as to their accuracy, and no prisoners are executed, until all 100 guesses are made. The prisoners may collaborate on a strategy, with the object of guaranteeing as many survivors as possible. (Their communication ends, of course, once the first hat is placed.) How many can be saved, in the worst case?

Assuming your interest is in Method 1:

My understanding of the puzzle If that's all true, then Q1: Q2: Q3:

@CaptainEd - Nice solve. Here is a solution i was aware of. I think the two are similar or equivalent, parsed out into a different set of states.

Not sure if it was clear that the run of odd number of heads are contiguous, as in the example, or if I'm misunderstanding your algorithm. Can you add some words here and there?

Peter and Paul, who are neighbors, each threw a party last Friday. Bad scheduling, to be sure, but that's life. Even worse, their guest lists were identical: all 100 of their friends were sent invitations to both parties. When guests arrived, the happy sounds of those already present could be heard through the two open doors, and the old phrase "the more the merrier" figured in their choice of which party to attend: If at any point there were a people present at Peter's party and b people present at Paul's party, the next guest would join Peter with probability a/(a+b) and join Paul with probability b/(a+b). To illustrate: When the first guest arrived only the two hosts were present. (a = b =1.) So that choice was a tossup, and let's say that the first guest chose Peter's party. (a = 2; b =1.) Now the second guest would follow suit, with probability 2/3, or choose Paul's party, with probability 1/3. And so on, until all 100 guests arrived. What is the expected number of guests at the less-attended party?