bonanova
-
Posts
6975 -
Joined
-
Last visited
-
Days Won
66
Content Type
Profiles
Forums
Events
Gallery
Blogs
Posts posted by bonanova
-
-
@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.Spoilerplainglazed's construction of successively halving the group implies logarithmic dependence on n, while plasmid produces the nth partial sum of the harmonic series. These differ only by the addition of the Euler constant (.577...). Because that's so close to 1/2 it may just represent the dilemma of whether or not, in plainglazed's method, to halve the final car.
Answers given in the posts differ, because I changed n from 100 to 1024 at one point.
-
15 hours ago, harey said:
If the blue are excluded because every room houses a green man, the same way you cannot accept even a single new guest.
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.
-
-
4 hours ago, aiemdao said:
The way it's set up, he can say Stop just once.
-
7 hours ago, aiemdao said:
Is O win if we get XOOOOOX?
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?
-
On 2/23/2018 at 4:52 PM, plainglazed said:
I think I see the pattern here and am encouraged by the beauty of binary symmetry so here goes:
For integers i and the number of prisoners n equal to 2^i-1, the probability of success p is (2^n-m)/2^n or n/2^i where m is the number of strings needed to memorize and is 2^(n-i).
i n=2^i-1 m=2^(n-i) p=(2^n-m)/2^n or n/2^i
1 1 1 1/2
2 3 2 3/4
3 7 16 7/8
4 15 2,048 15/16
5 31 67,108,864 31/32
.
.
.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.)
-
On 2/23/2018 at 10:44 AM, CaptainEd said:
I see, I didn’t pay attention. I really want to count only segments that are surrounded by shorter segments.
Yup. And a bit of possibly helpful thinking:
SpoilerWhile (see previous post for definitions) small, medium and large intervals (segments) are equal in (expected) number, their combined lengths of course will not be equal: the expected length of the large intervals is clearly greater than 1/3. But it's not intuitively clear whether it reaches 2/3.
Edit: The math gets a little demanding here. Integrals and stuff. -
On 2/24/2018 at 3:42 AM, harey said:
Brilliant, surprisingly interesting and leading to a major annoyance.
Yeah, I hate annoyances, too...
SpoilerThis discussion has been a challenge to sharpen my thinking, and my words. And it has been fun. Thanks for that.
Meantime, I recalled the problem of proving that the rationals, { p/q } for integers p and q, are countable. By definition { integers } are countable. And so { p } and { q } individually are countable. But can we establish that { all pairs of p and q } are countable? This was doubted at one time, but in fact they are: { pairs of p and q } can be matched 1-1 with { integers }. However, care must be taken in constructing the proof.
One failed proof first counts { 1/q }, then counts { 2/q }, then { 3/q }, and so on. But there is a problem with this. Once { 1/q } has been counted, we're done counting! Every element of { 1/q } matches to an integer, but every integer points to an element of { 1/q }. Ouch. That leaves { 2/q }, { 3/q }, .... uncounted. Matching two infinite indexes to the integers is a little tricky. It can be done, but it takes a bit of cleverness. If you haven't seen that proof, you can read it here. Fun to recall. Now back to the Hotel.
Let's combine the infinite sets { blue men } and { green men } into the set { men } and try to prove that { men } is countable. We need to find an integer for each man, and a man for each integer. That is, we need to find a bijection between { men } and { integers }: But wait. If we think of { rooms } as { integers } this is precisely our room assignment task: to find a bijection between { men } and { rooms }. And we should be careful in creating it, recalling the failed attempt regarding rational numbers. Some schemes may succeed, but clearly not every scheme.
In fact, one way to fail is to first assign rooms to the green men. That fails because it only serves only to create a bijection of { rooms } with { green men }. Every green man gets a room, true, but (gulp) also, every room houses a green man. Oy vey! The blue contingent got excluded. Yes -- we see them now, trudging down the road to the Holiday Inn. Want their room numbers? Call HI.
But we can house { men } at HH, interleaved. And also prove { men } is countable: just read their room numbers.
That's the crux, I think, of all the matters we've discussed.
-
4 hours ago, CaptainEd said:
Thank you for the kind words, Bonanova. I fear my answer to this one is not so brilliant.
63 is the lowest I can get.
7 vertical cuts of length 8,
56 horizontal cuts of length 1
i get the same result if I divide the board into 4 quarters, divide those into quarters(16), and divided THOSE into quarters(64).
Can you think of a reason?
-
OK I think I just found your first blue man.
SpoilerIf a process can be reduced to an algorithm (a program) that involves no more than countably infinite steps, then the process can be carried out in finite time. At least in theory. But that's sufficient to at least discuss the consequences or effect of the process.
We can do a process with countably infinite steps in finite time by scheduling stepi at a time ti = 1/2i minutes before midnight. The steps are executed at times 1, 1/2, 1/4, 1/8 ...., 1/2i, .... and the process completes in one minute. But what if we wanted to run a (countably) infinite number of such processes. Can we also do that?
Well, the universe will freeze in less than countably infinite minutes. But we can run each successive process in half the time of the previous one and finish everything in finite time. So, Yes, we can do that.
SpoilerLet process1 begin at 2 minutes before midnight and run its steps at these times thereafter { 0 1/2 1/4 1/8 ... } as before, and now end at 1 minute before midnight, at which time process2 begins. We run its steps at these times thereafter 1/2 x { 0 1/2 1/4 1/8 ... }, so that it ends at 1/2 minutes before midnight, at which time process3 begins, subsequently ending at 1/4 minutes before midnight. In general, processj will begin at 1/2(j-1) minutes before midnight with steps executed at times 1/2j x { 0 1/2 1/4 1/8 ... } thereafter, and compete at 1/2j minutes before midnight. At midnight then, a countably infinite number of processes, each with a countably infinite number of steps will have completed. And as before the jth step of the ith process has a unique and unambiguous execution date. So now we can do processes of complexity O(N2) on countably infinite sets. That is another way of saying that { Aleph0 }2 = { Aleph0 }. To get to a higher order of infinity you need 2{ Aleph0 }.
Now lets revisit Hilbert's Hotel and write some algorithms:
We have 3 countably infinite sets: { r = rooms } { b = blue men } { g = green men } and a bunch of things to do. Let's list them.
- Place bi in ri. Blue men have all checked in.
- Evacuate all rooms. Sorry to bother you, but some green men want to check in.
- Place bi in r2i. Check Blue men into even-numbered rooms
-
Place gi in r2i-1. Check Green men into odd rooms, so it's g b g b g b g b g b ....
All these are O(N) processes, which we know we can do.
But now we want to sort the occupants, using a type of bubble sort,
which is an O(N2) complexity process. But hey, we just showed how to do that, as well.
- For all j run processj consisting of
- For all i if b(ri) and g(ri+1) then swap those room occupants
At this point the clock has struck midnight and the horrific job is done. There is now no blue man in a room that has a lower number than a room occupied by a green man.
What have we accomplished? We'd like to say that in a countably infinite linear array of rooms we have placed a countably infinite set of green men, followed by* a countably infinite set of blue men. We know that we have enough rooms, because our rooms accommodated these same men when they were initially interleaved, all of which is to say
SizeOf ( { rooms } ) = SizeOf ( { green men } ) + SizeOf ( { blue men } ) = Aleph0.
So let's note here that Aleph0, the cardinality (SizeOf) of the counting numbers, is unchanged by "multiplying it by," or even "raising it to," any finite number. Those words are in quotes because Aleph0 is not a number and it does not follow the rules of algebra. But now at least we should hear an alarm bell and see a flashing red light if we try to say things like inf+1 or 2xinf or the like. These are not numbers, either.
But can we say anything more about the room assignments? For example initially a blue man was sleeping in Room2. And now we know (just by examining the doubly-infinite set of steps described in lines 5 and 6) that man is soundly asleep, hopefully, in a different room. Presumably he could open his door and read his room number. If we had a really long string with tin cans on the ends we could ask him what it is. How would he answer? Well since { rooms } = { green men } + { blue men } and he is the first blue man, he'd have to say "My room number is ... Aleph0 + 1." What a prestigious address -- like the ultimate penthouse. Wow. There we have it. But what we have is meaningless.
So anyway I was wrong before. We can, by following a well-defined procedure, place all the blue men after* all the green men. But after we've done it, we've lost track, in conventional terms, of their room numbers. Other than to say "they're waaaaaay out there, unspeakably greatly removed from the hotel office." And so much for room service! I think we can say that the blue men originally in rooms 2 and 4 are now neighbors, but maybe we can't even say that. It would be like asserting that (inf+2) - (inf+1) = 1, where the terms on the left are meaningless. Maybe we can just say the blue room numbers are all infinitely large. But maybe we can do better than that, in a different way?
Spoiler* Except that followed by, and after, etc., imply this completion thing again.
We handled the completion of infinite events by clever scheduling. So let's take a page from that playbook so that I can do a better job of describing the new location of the first blue man.
Hilbert's hotel undergoes a re-design:
Room1 is now its most luxurious room with a colossal width of 1 mile. Room2 less grand, but certainly nothing to sneeze at, weighs in at a comfortable width of 1/2 mile. Room3 is "only" 1/4 mile wide. Similarly, each Roomi has a width of precisely 1/2i miles. Thus a countably infinite number of HH rooms fits alongside a workable 2-mile-long parking lot. Let's paint this building a refreshing sea green, and into its rooms let's place all the { green men }. Immediately adjacent to that building lies another set of rooms, the first of which is, again, 1 mile in width. Next to it is a 1/2-mile-wide room, followed, in turn, by rooms 1/4, 1/8, ... miles wide. They comprise a second 2-mile-wide building, which we will paint a lovely azure blue and into whose rooms we now place all of the { blue men }.
If all the rooms are numbered consecutively we still do not know the number of the first blue man's room. But if we want to visit him we can look at a map and clearly locate it! We only have to walk 2 miles from the office. Or we can simply jog down to the blue building, and knock on its first door. Hi, mister first blue man, nice to see you.
How's that?
-
@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.)
-
10 hours ago, harey said:
Maybe an idea. There is an infinite number of numbers between 0 and 1. I have the opportunity to discard an infinite number of numbers between 0 and 1.
How much are you willing to bet that nothing remains between 0 and 1?
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.
-
Spoiler
The paths of each pursuing dog and his target are perpendicular. Because their speeds are equal, the dogs remain at the corners of a (shrinking) square. Although the target dog is not standing still, his motion does not increase or decrease the distance from his pursuer.
Another way to think of it is to rotate the square as the dogs run, so as to keep the sides of their square horizontal and vertical. The dog in the LR corner, then, would be seen to run vertically until he reached the dog in the UR corner, thus running exactly the length of the original square.
If three dogs were at the vertices of an equilateral triangle with sides of unit length, they would run less than 1 unit distance, because the velocity of their target dogs would have a component that pointed toward their pursuers, thus shortening the needed distance to be caught. Five dogs on a pentagon would have to run farther than 1 unit distance. The deviations in each case are given by the sine of the angle at the vertices. For a square sin(90) = 0, and so on.
-
This is a nice puzzle.
SpoilerThe solution seems to consist of (1) choosing the right number of coins for the first comparison and (2) what to do if weights are equal. (1) depends on how many heavy coins you want to find. I thought I had (2) figured out, and I think it's on the right track, but it's still not quite definitive. I'll edit this post when I get it.
-
2 hours ago, rocdocmac said:
"Al:
On step 1 Al discards coin 1." Al therefore retains coin 2. "On step 2 A discards coin 2." He retains coins 3 & 4, "... On step N Al discards coin N." Thus, he retains coins N+1, N+2, ...., and 2N. "As N -> inf, every coin is discarded." What happened to the N coins not discarded?
"If there were a coin in Al's box at midnight it would have a number. What number would that be?" There ought to be N coins left, numbered n+1, 2+2, ..., 2N.I still can't get to grips with this one!
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.
-
4 hours ago, harey said:
If a coin can be discarded, it does not mean it will be discarded. I would reformulate it: The key question is this: will all coins that are kept at a certain event ever be discarded at a later event?
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.
-
Spoiler
Still waiting for the blue and green men to switch rooms.
Check back later. (Much later.)
I have a hunch that the required room swaps are not countably infinite. But if they are, if the swaps can be described in sequence order and associated 1-1 with the integers, then we might schedule them to complete in finite time by scheduling the swaps to occur at 1, 1/2, 1/4, 1/8, ..., 1/2^n, .... minutes before midnight. And then the questions could be asked, and it would be fun to consider their possible answers.
Otherwise it's akin to find a reordering of the integers that places all the even integers after the "end" of all the odd ones. That place does not exist; there is no "final" odd integer. The last question seems to ask for a finite value of N as N -> inf. What is the (finite) room number for a room that lies infinitely far from Room 1? There is no finite number that associates with infinity.
-
@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. -
Spoiler
Let's take the OP to be a riddle of sorts that implies precisely 4 light coins in the group of 48 coins.
That means in the first weighing, the heavier side, if there is one, has at most 1 light coin.
If neither side is heavier, both sides can have 0-2 light coins.
That gets us close, but I think it's not quite enough.Compare any two groups of 14 coins.
If there is a heavier group (at most 1 light coin), compare any 7 of that group with the other 7.
The heavier group of 7, if there is one, otherwise both groups of 7, are free of light coins. DoneIf the 14-14 comparison balances, both groups of 14 contain 0-2 light coins.
Compare 7 of either group of 14 with the other 7 of that group.- If there is a heavier side, it contains 0 light coins. Done.
- Otherwise both sides contain 0 or 1 light coins. Fail.
Alternative scheme
If the 14-14 comparison balances, Take any 7 (A) from either group of 14.
Compare (A) with any 7 (B) from the remaining 20 coins and take the heavier group if there is one, else either group.
Three cases:- (A) has two light coins. (B) must have 0 light coins. Done.
- (A) has one light coin. (B) can have 0-2 light coins. Fail.
- (A) has no light coins. Done.
-
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.
SpoilerIf coins remain in Al's box, one of them must have a number that is lower than the others. But at every event Al discards the lowest numbered coin. More directly, if any coin remains it must bear a number, say k. But coin ck was discarded, prior to midnight, at time tk.
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.
-
5 hours ago, flamebirde said:
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.
Next card is Red
in New Logic/Math Puzzles
Posted
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.