Jump to content
BrainDen.com - Brain Teasers

All Activity

This stream auto-updates     

  1. Past hour
  2. A big, big, big hotel

    If 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 now suppose we need 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. Let 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 }. 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. Evacuate all rooms. Place bi in r2i. Place gi in r2i-1. 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. 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 no blue man in a room that has a lower number than a room occupied by a green man. What have we done? 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 the men when they were initially interleaved as g b g b g b g b g b .... 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. But now it should raise a flag if we say things like inf+1 or 2xinf and the like. They're 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 in lines 5 and 6) that man is soundly asleep 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 you have it. So I was wrong before. You can, by following a well-defined procedure, place all the blue men after* all the green men. But having done so, we lose track, in normal terms, of their room numbers. Other than to say "they're waaaaaay out there, unspeakably removed from the hotel office." 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. * 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 first of the { blue men }. 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. And into these rooms we place all the { green men }. Now immediately adjacent to that freshly painted sea green building there is another set of rooms in a building painted a beautiful azure blue. Its first room, again 1 mile in width, houses the blue former occupant of Room2. Next to him, in a 1/2-mile-wide room snores the blue former occupant of Room4. These rooms are followed, in turn, by rooms 1/4, 1/8, ... miles wide, and they complete the 2-mile-wide green building, and in its rooms we place all the { blue men }. Now if the rooms are numbered consecutively we still do not know the number of the first blue man's room. But if you want to visit him we can look at a map and find his room! Or we can simply walk 2 miles from the office, or, even more easily, just walk down to the blue building and knock on its first door. There. I answered your question. Sort of.
  3. Today
  4. Worth the Weight

    @aiemdao - Yes, nice solve indeed Aiem. Well done. @bonanova - thanks.
  5. Right Prime

    Any other prime numbers less than 1000.
  6. Worth the Weight

    @aiemdao - Nice solve. @plainglazed - Nice puzzle.
  7. Worth the Weight

    4 light ones/48
  8. @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.)
  9. 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.
  10. Right Prime

    Some amount of primes.
  11. Yesterday
  12. Right Prime

    Say 5939 is a "right" prime because it remains prime after dropping any number of digits from the right: 5939, 593, 59, and 5 are all prime. How many right primes are there less than 1000?
  13. Four dogs are positioned at the corners of a square (d=1m), chase each other in clockwise direction with the same constant speed . As their target is moving, they will follow a curved path, eventually colliding in the center of the square. Why is the total length of the path just 1m?
  14. Worth the Weight

    I think I've got it. Nah, I definitely don't have it. I can't account for one particular case.
  15. When midnight strikes

    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?
  16. Worth the Weight

    This is a nice puzzle.
  17. When midnight strikes

    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.
  18. When midnight strikes

    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.
  19. Destroying a checkerboard

    @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.
  20. There is a hotel with an infinite number of rooms, all rooms occupied by little green men (one man in a room). An infinity of little blue man arrive and each one asks for a room. No problem, the manager moves the blue man from the room n to the room 2*n, freeing the odd-numbered rooms for the green men. So far, loosely copied from https://en.wikipedia.org/wiki/Hilbert's_paradox_of_the_Grand_Hotel. It turns out that the blue men sing between noon and midnight and sleep between midnight and noon while the green men sleep between noon and midnight and sing between midnight and noon. Complaints. The manager decides to group them. Conveniently, the rooms are in a straight line, numbered from left to right. While there is a green man left to a blue man, he makes them change the rooms. Eventually, all the blue men leave. - how many rooms are free? - how many rooms remain occupied? - what is the number of the first occupied room?
  21. When midnight strikes

    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? BTW, we can establish a bijection between Al's and Bert's coins. The coins bear green numbers. After each step, Al renumbers them and assigns them blue numbers 1, 3, 5, ... His blue numbers will match the (green) numbers in Bert's box. For any number of steps. I think it is legal to assume it is true even for N-> inf. Another way to prove that Bert's box will not be empty: graphical presentation. The number of coins in his box is a straight line (at 45 degrees). How is that it suddenly drops to 0? And maybe a corollary: Bert never discards more coins that he receives. How is that when he has, let's say 8 coins, he can have less in a later stage? If we reason with {coins} and {events}, don't you see a 1-1 relation?
  22. Worth the Weight

    hey bn - Thanks for getting this one started. You are correct in all you say above including your initial summary of the problem. Have edited the OP to include that explanation. I assure you there is a scheme in which one can guarantee finding seven heavy coins. Perhaps start off by finding one guaranteed heavy coin in two uses of a balance scale. Or not. I have no doubt you or others here will discover the method for finding seven heavy dimes.
  1. Load more activity