Post by: alfonz1986 on July 16, 2011, 03:34:55 PM
His carcass sinks straight to the bottom. What will happen to the overall water level of the lake? Will it
(a) Rise
(b) Fall
(c) Stay the same
Write your answers on a postcard, and give a little reasoning as to why you think its the right answer
Post by: Simon on July 17, 2011, 06:40:37 AM
Answer is that the level falls (or stays the same in a corner case). The reasoning is as follows. If he's in the boat, his weight displaces water (putting this water above the regular level) equal to his weight (pressure), whereas if he's in the lake, he displaces water equal to his volume. The water amount equalling his weight is more than his volume; if it were not, he wouldn't have drowned, but floated.
The corner case happens with exact same densities, in which case inertia from falling would have made him drown.
-- Simon
Post by: alfonz1986 on July 17, 2011, 02:38:45 PM
Post by: chaos_defrost on July 17, 2011, 07:04:44 PM
I'm not sure what u mean by the 'corner case'
I think he means when the density is the same as water -- the lemming then sinks because he has downwards force from gravity.
Post by: alfonz1986 on July 17, 2011, 07:35:31 PM
Post by: finlay on July 17, 2011, 09:06:31 PM
Post by: ccexplore on July 18, 2011, 12:31:03 AM
So unless the lemming is so careful in entering the water that he has no downward velocity when he hits the water, he will continue going downwards until he is able to have an upward force exerted on himself to change his velocity from down to up. For example, once he hits the bottom he could push against the floor to create an upward force on himself, and then he would be able to get back up on the surface. But if he's a true lemming he would not know to do anything
, and therefore would've stayed under water.[edit: I might've simplified the situation a bit when the lemming hits the bottom. Depending on the material characteristics of the floor, the impact force can be such that I suppose the lemming can also bounce back up, like a billiard ball bouncing off a wall.]
Post by: alfonz1986 on July 18, 2011, 12:40:20 AM
Post by: ccexplore on July 18, 2011, 12:47:27 AM
@finlay and ccexplore, the force is dissipated quickly by drag force. The water effectively acts like damping system (suspension system in a car) and slows his velocity to a standstill (assuming he was neutrally buoyant).
Okay that's reasonable, but ultimately it still depends on how fast the lemming is when he hits water. In other words, if the lemming jumped off a 10-floor building he's probably fast enough that even the drag force would not have prevented him from being fully submerged. Your problem did state that he sinks all the way to the bottom, so for the corner case to occur, it does imply an unrealistic situation (in terms of falling off from a boat) where the lemming hit the water so fast, and the lake shallow enough, that the lemming is still able to hit the bottom despite the drag force. Still, given that these aspects of the problem is unspecified, it is fair for Simon to posit a corner case to cover this situation as well.
[edit: Hmm......due to the way you posit the problem, technically it can also describe a situation where the lemming first drowns by being fully submerged in water (w/o hitting bottom due to neutral buoyancy and drag), then having swallowed water, the increased density puts him out of neutral buoyancy and then he finally sinks to bottom. Not sure how the water level works out in that case, although the among of water swallowed should be negligible, since even one molecule of it is enough to put the density past neutral buoyancy.]
Post by: alfonz1986 on July 18, 2011, 12:54:33 AM
Will the water level rise, fall, or stay the same? and why?
EDIT: for the puposes of the problem, assume that the lemming doesnt swallow any water, or release any air. I only specified the problem with two lemmings in a boat to relate it to all u guys
the real problem was two people in a boat and someone drops a solid object off the boat. although, the basic logic remains the same. Post by: ccexplore on July 18, 2011, 03:04:48 AM
We're going off topic a bit here. The problem asks about the water depth, not whether or not the lemming ultimately sinks or floats.
I think Simon already answered your question, you're the one who is disputing the corner case scenario he proposed. At this point it's just hashing out the details of the corner case to get a better understanding of what is to happen or not happen in that case. If someone else has a different puzzle I'm sure we're happy to look at it.
Also if the lemming enters the water with more velocity the normal force (drag force) just increases to counteract it. Haven't you heard of firing bullets into water? They completely disintegrate into shrapnel and do not travel far due to the massive drag force counteracting their large velocity.
They've actually done a TV show related to bullets firing into water. There's no question that you get higher drag force with higher velocity, but not knowing the exact numbers, it doesn't directly answer the question of how much distance it takes to reach 0 velocity with drag. For example the TV show found that slower-speed bullets can travel for at least 8 feet in water. I'll grant you that water exerts far higher drag than air, so I don't disagree with what you suggest will happen even if I'm not certain either.
I think this calls for an experiment. Who has a lemming we can drown?
=========
Aside: the highly physical nature of the problem makes me think it's not really a logic puzzle to start with. So we already started a bit off-topic.
Post by: Simon on July 18, 2011, 06:46:06 AM
Physics sucks!
Beavis has 23 fleas in his hair, and 32 spiders. Butt-head thinks this sucks too, and decides to remove the critters with a fork. The fork will always pick 2 critters at once.
If at least one of the two is a spider, he flings it out the window and puts the other critter (either flea or spider) back into the hair. If both are fleas, he carefully takes them to the trash bin outside. While Butt-head is underway, Beavis gets bored, searches the living room walls for a fresh spider, and puts that in his hair.
Butt-head continues this, until eventually, only a single critter is left in the hair. What species is it?
-- Simon
Post by: alfonz1986 on July 18, 2011, 10:29:13 AM
[edit - added] That being said, the final combinations are:
FSS - FS > FS > F
or
FSS - SS > FS > F
FFF - FF > F
even if he adds the spider right at the end it would give FS > F
Post by: Simon on July 18, 2011, 12:58:01 PM
Post another one or declare open floor. :-)
-- Simon
Post by: alfonz1986 on July 18, 2011, 01:13:04 PM
if u know the answer to this next one already - let the others ponder it a bit longer
Ok here it is:
Theres an airplane on a giant conveyor belt on a runway. As the airplane speeds up, the conveyor belt matches the airplane's speed but in the opposite direction. Will the plane be able to takeoff or not? and why?
Post by: finlay on July 18, 2011, 02:02:15 PM
Post by: Simon on July 18, 2011, 02:30:06 PM
Unsure because it's not the wheels, but the the englines on the wings who provide acceleration. They shouldn't move enough air surrounding the wings though, they only pull in the air in front of them.
alfonz: I did not attempt the water level puzzle seriously before seeing its solution for the first time. I don't know whether I would have solved it correctly back then.
-- Simon
Post by: Johannes on July 18, 2011, 06:07:00 PM
In which case I have to ask, how do you define "matching speed" of the conveyor belt?
Velocity of belt backwards = velocity of plane forwards, in regards to the ground?
Post by: alfonz1986 on July 18, 2011, 06:17:08 PM
Post by: ccexplore on July 19, 2011, 01:30:51 AM
[edit: completely rephrase again after Johannes corrected some fundamental misceptions I have around the setup of the scenario]
Imagine two absolutely identical airplanes. Airplane "A" sits on a normal runway, while "B" sits on a giant conveyor belt. We now start and turn up both airplane's propellers at completely matching rates at all times. Obviously, A will start to move forward and eventually lift off.
Now imagine that with B, while we are ramping up its propellers at matching rate with A, we also have the conveyor belt turned on, and its speed ramp up at a rate always matching the speed of A, but going backwards. What will happen with airplane B? Can it takeoff or not, and why?
Post by: Johannes on July 19, 2011, 08:28:48 AM
the conveyor belt ... speed is continuously adjusted to match the airplane's speed but in the opposite direction, so that relative to the runway, the airplane is neither moving forward nor backwards.Not quite - the way you describe it it's quite obvious that the plane won't take off. The speed of the conveyor belt is adjusted to run backwards as fast as the plane moves forwards, yes. The question is, does this keep the plane stationary?
Post by: ccexplore on July 19, 2011, 09:32:52 AM
the conveyor belt ... speed is continuously adjusted to match the airplane's speed but in the opposite direction, so that relative to the runway, the airplane is neither moving forward nor backwards.Not quite - the way you describe it it's quite obvious that the plane won't take off. The speed of the conveyor belt is adjusted to run backwards as fast as the plane moves forwards, yes. The question is, does this keep the plane stationary?
Hmm, I sort of see your point now. I think I sort of misunderstood this aspect of the setup but to be honest, I'm still not sure I quite get all the physical interactions around this scenario the more I think about it.
I've edited my scenario description hopefully to better capture the setup...maybe. I need to think more about it.
Post by: Clam on July 19, 2011, 09:41:57 AM
)This all depends whether you're talking about the plane's velocity relative to the ground, or to the conveyor belt. "Speed" isn't a good term to use, since movement has to be measured relative to something. That said, given what's been said in the above posts, I'm guessing we mean velocity relative to the ground.
Relative to the conveyor belt, the plane is travelling at twice its apparent (relative to the ground) speed: enough to balance the action of the conveyor belt, and the same amount again to produce actual movement (which, again, is what I'm guessing the conveyor belt is supposed to match). In other words, the conveyor belt effectively halves the speed of the plane. So, assuming the plane needs to attain a given velocity relative to the ground in order to take off, it needs to be able to attain twice that speed on a normal runway without the conveyor belt. Whether it can do this probably depends on the plane in question. (For example, if it's a Harrier Jump Jet, the entire question is moot since it can take off vertically
)
Post by: ccexplore on July 19, 2011, 09:50:41 AM
(Not sure how "logic puzzles" came to mean physics problems, but anyway...
Well, so far only alfonz1986 has actually been posing physics problems. Not that I mind; while not what I think of as "logic" puzzles, they can nevertheless be pretty thought-provoking, simply because our human intuition about physics is not very good, and at the same time, accurate applications of the various principles, laws and equations of physics can be subtle sometimes.
Anyway, I completely re-edited how I framed the problem, because after what Johannes said, I feel my original way of trying to frame the problem may actually be totally off from what's intended, despite reading superficially similar. I'm also going to post a follow-up question (in spoilers to avoid hinting one way or another at original problem) to see if I really understand this better now.
Post by: Simon on July 19, 2011, 10:30:10 AM
(Not sure how "logic puzzles" came to mean physics problems, but anyway...they can nevertheless be pretty thought-provoking, simply because our human intuition about physics is not very good, and at the same time, accurate applications of the various principles, laws and equations of physics can be subtle sometimes.
Hrm. The main thoughts they provoke are clarification requests. :> And without grinding through enough theory, one can never verify answers despite being interested in it, only believe the eventually presented solution. Both issues (clarification and relative theory-heaviness) rarely happen with logic puzzles; maybe sometimes with math (note that I require being interested in the question at hand), but still much less than with physics.
-- Simon
Post by: alfonz1986 on July 19, 2011, 11:01:39 AM
@ClamSpam The plane's velocity relative to the ground is what we're talking about in this case. Assume the plane is a small aircraft with two propellers, not a harrier jump jet
I'll give you guys a hint (invisible) Imagine yourself in a swimming pool up to your armpits in water. You're standing on a conveyor belt on the swimming pool floor, wearing a pair of rollerblades. If the conveyor turns on, what will happen? If you breakstroke forward and the conveyor matches your speed, what will happen?
Post by: ccexplore on July 19, 2011, 11:29:18 AM
@CCE The newly editted way you describe the problem is basically identical to the way I described it.
I agree. I didn't think your original phrasing was ambiguous, it's just that some of the first answers and questions to your original phrasing makes me wonder if people even understand the basic description correctly. My 1st rephrasing is mainly an attempt to describe the frame of reference more precisely, to eliminate confusion about "speed" (and to make it clear that the airplane propellers are indeed in operation). And then Johannes raised a point about my 1st rephrasing which makes me think (I'm still thinking
) maybe it is a bad formulation, so then in my 2nd rephrasing, I decided to use 2 airplanes as a way around his objections.I guess these are physics rated problems but I don't believe you need to have studied much physics to solve it if you have strong logic.
I'm not so sure, I think you may be overestimating people's ability to properly analyze physical situations. Our intuition in most cases are just plain wrong, as history have readily shown through the "natural philosophies" of Aristotle etc.
But I never majored in physics, so maybe you can enlighten me. For example, how would you explain your 1st problem about water level to someone w/o asserting Archimedes' principle? (or alternatively, how to explain that principle purely in terms of logic?)
Post by: Johannes on July 19, 2011, 11:36:28 AM
I've edited my scenario description hopefully to better capture the setup...maybe. I need to think more about it.I really like your new scenario description, as it still poses the same core problem but avoids all the definition issues and physical impossibilities usually accompanying this "riddle".
Post by: Clam on July 19, 2011, 11:52:16 AM
I'll give you guys a hint (invisible) Imagine yourself in a swimming pool up to your armpits in water. You're standing on a conveyor belt on the swimming pool floor, wearing a pair of rollerblades. If the conveyor turns on, what will happen? If you breakstroke forward and the conveyor matches your speed, what will happen?
Well...
Quote from: in response to hint
When the conveyor belt turns on, won't the wheels of the rollerblades just spin, while you go nowhere? Doesn't this analogy break down because of (a) the massive difference in density between air and water (and thus force required to move you through it), and (b) your buoyancy in water, which takes much of the weight off your feet?
Anyway, is the assessment in my above post (twice normal take-off velocity, otherwise you stay on the ground) correct?
Also, I agree with Simon's sentiment that physics puzzles will result in a lot of back-and-forth and clarifications. But, on the other hand, they are fascinating in their own right
Post by: Johannes on July 19, 2011, 12:10:26 PM
Anyway, is the assessment in my above post (twice normal take-off velocity, otherwise you stay on the ground) correct?
No, not correct.
Quote
Hint: Is the aircraft exerting a force (aka pushing) on the conveyor belt to move forward?
Post by: alfonz1986 on July 19, 2011, 12:17:02 PM
I'm really posing these questions to you guys because I regarded epic lemmings players as very logical people who come up with creative solutions to challenging problems. I was interested to see how you all faired at some tough physics/science puzzles.
EDIT: I dont know how the f*** to make it invisible
Post by: Johannes on July 19, 2011, 12:18:45 PM
Somewhere in Northern Eurasia, a group of 20 lemmings is planning a special group suicide this year. Each of the lemmings will be placed in a random position along a thin, 100 meter long plank of wood which is floating in the sea. Each lemming is equally likely to be facing either end of the plank. At time t=0, all the lemmings walk forward at a slow speed of 1 meter per minute. If a lemming bumps into another lemming, the two both reverse directions. If a lemming falls off the plank, he drowns. What is the longest time that must elapse till all the lemmings have drowned?
Quote
Hint: Minimal math is required if you make a certain, correct observation.
Edit: Extra credit for anyone who builds an appropriate lemmings level to test this out
Post by: ccexplore on July 19, 2011, 01:08:00 PM
Here's my answer. I feel this is a neat enough problem that I should give others a chance to solve on their own as well, hence spoilers:
Quote from: spoiler
All lemmings will have drowned by 100m / 1 m/s = 100 minutes. Reason: suppose we give each lemming a shirt with a different number, and stipulate that whenever 2 lemmings bump into each other, in addition to both reversing their directions, they also exchange each other's shirts (instantaneously). It should be obvious that this rule about shirts have no impact to their actual movements on the plank, and therefore is equivalent to the original situation.
Now imagine that given the same starting positions, facing directions, and shirt assignments, we now change the rule so that whenever 2 lemmings bump into teach other, they don't exchange shirts, and instead of reversing directions they just pass through each other.
Hmm...wait a minute. They describe the exact same situation! At every point in time, for each position in situation #1 that has a lemming, in situation #2 you also have a lemming in same position facing same direction, with same shirt color.
Now the answer should be obvious.
[edit: I made a minor edit about 10 seconds after initial posting, to correct a silly brainfart
][edit2: minor clarifications]
Post by: Johannes on July 19, 2011, 01:11:21 PM
Quote
I remember the first time I saw this puzzle, and I quickly filled a sheet of paper with some possible scenarios, without really getting anywhere except horrific formulas. The simple math hint gave me the little nudge in the right direction I needed to rethink the problem.
Post by: ccexplore on July 19, 2011, 01:19:53 PM
Quote from: not really big spoiler but anyway
the symmetrical nature of how 2 lemmings interact with each other strongly suggests to me it's the key to why the answer should play out the way it does. And with a little effort along that line of thought, I was able to come up with a really simple argument to illustrate the equivalences.
Post by: alfonz1986 on July 19, 2011, 01:51:26 PM
EDIT: I didn't read your hints before coming to this conclusion
I will just read it now.
Post by: ccexplore on July 19, 2011, 07:16:33 PM
I'm really posing these questions to you guys because I regarded epic lemmings players as very logical people who come up with creative solutions to challenging problems. I was interested to see how you all faired at some tough physics/science puzzles.
It's nice to think that the skills translate across disciplines that directly, but from personal experience I don't think my adeptness at lemmings even translate to adeptness at other games like chess or even Sokoban that have strong mental components.
I think it's conceivable that given an "epic" lemmings player vs someone really bad at it, there is a higher chance that the former person has greater rate of success at correctly answering any given physics/science/math/logic puzzle than the latter. But that's very different from comparing one individual's rate of success in one domain vs another.
There has also been relatively well-documented cases of puzzles that defy even otherwise highly competent people in fields of mathematics etc. Like the Monty Hall problem.
Post by: alfonz1986 on July 19, 2011, 10:14:21 PM
Post by: Clam on July 20, 2011, 12:32:27 AM
The conveyor belt pushes on the wheels, but this doesn't necessarily push the plane backwards since the wheels can just spin. So the conveyor belt is a complete red herring and the plane can just take off as normal (possibly with some extra wear on the tyres).
The tricky part here, which threw me off, is that if you have a plane sitting stationary on the conveyor belt, and then start the belt running, the plane will move backwards. But, once you start applying thrust (which comes from the engines/propellers and doesn't go through the wheels), this doesn't hold any more. If you replace the conveyor belt with something that imparts a force on the whole plane (like maybe a giant electromagnet? NOT wind force though, since that will generate lift), then the plane will need to be capable of doing twice its take-off speed.
Post by: alfonz1986 on July 20, 2011, 01:39:35 AM
The plane will take off just as normal (as proven by mythbusters) the only difference is that the wheels spin 2x as fast as they would if they were on a normal runway.
Post by: Simon on July 20, 2011, 06:11:26 PM
I have the following one, and for once, it's not one you will find on every riddle site. I knew the question for a while, and worked out the (surprisingly easy) proof today after giving it a proper shot, so it should be doable. I have no clue how easy this is for people who aren't used to tackling math problems, so I will give hints generously if necessary.
Consider the sequence (an) for n = 0, 1, 2, 3, 4, ..., with possible values only 0 and 1 for each an, constructed as follows:
- If n = 3k for some integer k, then an = 0.
- If n = 3k + 1 for an integer k, then an = 1.
- If n = 3k + 2 for an integer k, then an = ak.
We define a triple to be any non-empty substring of the sequence (an) together with two repetitions of itself immediately following it. E.g. 101010 somewhere in the sequence is a triple, but 0010 is not, since the second repetition of 0 isn't immediately after the 00.
Show that there are no triples in the sequence (an).
-- Simon
Post by: finlay on July 20, 2011, 06:49:59 PM
Quote from: Spoiler
OK... let's ignore the third digit in the sequence for now.
0 1 x 0 1 x 0 1 x 0 1 x 0 1 x 0 1 x 0 1 x
we can trivially conclude that there are no 2 digit triples by noting that for any n=3k or n=3k+1, a_n=a_n+3, whereas we need it to be equal to a_n+2. This would be true wherever you start... the three possible triplets are:
0 1 x 0 1 x
1 x 0 1 x 0
x 0 1 x 0 1
, all of which contain x 0 and 0 1 as one of their two digit segments, which are an invalid mismatch because 1≠0.
For three digit triplets, the possibilities are
01x 01x 01x
1x0 1x0 1x0
x01 x01 x01
Here we have to say that they're invalid because you never have the same x three times in a row, because the x's are in the same distribution as the sequence itself – ie there must be a 1 and a 0 at least every 3 digits. we can say the same thing about 1 digit triplets – you'll never get the same digit three times in a row because there can be a maximum of 2 1s or 0s in a row.
I'm sure there must be some kind of inductive proof at this point. For 4 digit triplets, for instance, the possibilities are
01x0 1x01 x01x
1x01 x01x 01x0
x01x 01x0 1x01
; here we can see that the sets 01x0 and 1x01 must occur in any 4 digit triplet sequence and are trivially a mismatch. similarly, for 5 digits, the sets that comprise any triple (in any order) are
01x01 x01x0 1x01x
ie there must be a substring that starts with 0 and one that starts with 1. We can similarly eliminate any n-digit triple where n=3a±1 for integer a
Um... yeah, and then... with n=3a triples, the x's in the sequence become important, but we know that they're in the same distribution as the main sequence, so an n=3a digit triple becomes equivalent to an n=a digit triple...
Something like that... I'm not very eloquent at maths.
Post by: Simon on July 20, 2011, 07:13:37 PM
The only thing left to make it super-formally correct would be to organize the "something like that". However, this is minor work (only hard if one doesn't do maths regularly), the main work is finding the underlying idea, which you have.
-- Simon
Post by: finlay on July 20, 2011, 10:34:19 PM
Post by: ccexplore on July 20, 2011, 11:02:43 PM
Here's a hint that I think might help, for those not used to the general reasoning of mathematical induction:
Quote from: hint
The 3k+2 part of the definition leads to this very special property about the sequence. First, lay out the sequence in this special tabular format:
a0 a3 a6 a9 ...
a1 a4 a7 a10...
a2 a5 a8 a11...
Here's what it looks like from a0 to a29 for example:
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1
0 1 0 0 1 1 0 1 0 0
The key is to notice that the recursive 3k+2 definition (which says a2 = a0, a5 = a1, a8 = a2, etc.) means that remarkably, the bottom row of numbers (a2, a5, a8, ...) is actually a copy of the original sequence of a0, a1, a2, ...
The tabular layout also helps with visualizing what happens when you try to layout a candidate triple, by observing what happens with an element, its first repeat, and its second repeat when laid out in this table (in particular, which horizontal rows each winds up at).
Post by: geoo on July 24, 2011, 01:43:49 PM
EDIT: Added for clarification: always prove the correctness of your result.
#1. Assume you have a chocolate bar consisting, as usual, of a number of NxM
squares arranged in a rectangular pattern. Your task is to split the bar into
small 1x1 squares (always breaking along the lines between the squares) with a
minimum number of breaks. A break consists of a straight line cut through a
piece of the bar that goes from one side to the other. You can not break the
squares. You can only break one piece at a time. Stacking two pieces and
breaking them in one go counts as two breaks. What is the minimum amount of
breaks needed?
#2. Let N be the set of integers from 0 to n-1. How many ways are there to choose subsets A, B and C of N so that the union of the three sets is N, and the intersection is the empty set? Solutions that result as permutation of another solution are counted separately.
#3. There is a positive, finite amount N of spherical planets of radius R in space. We consider a point on the surface of a planet as non-exposed if it cannot be seen from any other planet. What is the total surface (summed over all planets) that is made up by non-exposed points?
#3.5. There's an infinite amount of light bulbs in a row, labeled 1, 2, ...
At the beginning, all of them are switched off. Now you toggle the state (i.e. off -> on and on -> off) of every light bulb, then you toggle every second one (i.e. those with index numbers dividible by 2), then every third one (i.e. those with index numbers dividible by 3), and so on. Once you're done with that (haha), which ones are switched on?
#4. You're given an acute-angled (this is not actually required, but then you can freely choose the base side) triangle with a base side. You're supposed to put N disjoint rectangles into this triangle so that the first is aligned with the base side and its edges touch the other two sides, the next is aligned on top of the previous rectangle and its edges touch these same two sides of the triangle, and so on, stacking these rectangles on top of one another. What is the optimal arrangement to cover as much of the area of the triangle as possible with these N rectangles?
#5. There are two persons, A and B. There are two secret positive integers whose sum is less than 100. A is told the product of the numbers, and B is told the sum. There is the following conversation:
A: I don't know the two numbers.
B: I knew that you didn't know.
A: Now I know them.
B: Now I know them too.
What are the two numbers?
Post by: ccexplore on July 24, 2011, 02:35:17 PM
Quote from: spoiler but com'on
If you can only break one piece at a time, then each break can only increase the total number of pieces you have by 1, so duh!
Unfortunately I've been exposed to the types of puzzle as #5, but #2-#4 is new to me and does seem tricky so far.
Speaking of exposure, I've actually tried to contribute to this thread, but since I'm unable to come up with any original puzzles myself, I'm sure anything I post someone else probably already have heard.
Post by: geoo on July 24, 2011, 03:24:38 PM
Bonus question (still simple): Now you may stack pieces and then break them all in one go. What's the optimal solution then?
Please don't hesitate to post puzzle you think some people may already know, probably they will be new to at least some. I didn't come up with my puzzles myself either.
EDIT: I added another one I forgot to my post, labeled #3.5 because I feel it fits in the range #2-#4 style-wise.
Post by: alfonz1986 on July 24, 2011, 06:44:40 PM
Is #3.5 4^n, ie 1, 4, 16, 64, 256, 1024...
Post by: geoo on July 24, 2011, 08:14:41 PM
#3.5 is incorrect, but the numbers you got are a subset of the numbers that correspond to switched on light bulbs.
Here's another fun one I just remembered, don't know how well known it is:
A camper has set up his tent, and is going for a hike. He walks 2 miles to the south, 5 miles to the west, and 2 miles to the north. Having arrived at his tent again, to his dismay he sees a bear plundering his tent.
Question: What color is the bear?
Post by: alfonz1986 on July 24, 2011, 09:45:15 PM
EDIT: Aha! Is it all squared integers? 1,4,9,16,25,36,49,64 , n^2 ?
Post by: geoo on July 24, 2011, 10:17:44 PM
btw, that wu::riddles site Johannes pointed to is really awesome!
Post by: Clam on July 24, 2011, 11:33:31 PM
Quote from: spoiler
The union of A, B, C is all numbers, so each number is contained in at least one subset. The intersection of A, B, C is empty, so each number is absent from at least one subset (i.e. present in at most two). This means each number is in either one or two of the subsets, meaning there are 6 possibilities for each number: A only, B only, C only, A and B, A and C, or B and C. There are n numbers, and thus there are 6^n ways to choose the subsets.
Post by: alfonz1986 on July 25, 2011, 12:38:44 AM
Post by: geoo on July 25, 2011, 12:43:46 AM
Anyway, as always, you still got to prove the correctness of your solution, i.e. that it applies for any amount of arbitrarily positioned planets.
(I silently assumed in the problem statements that the correctness is to be proven, which is kinda self-evident to a mathematician.)
As for Clam's solution to #2, that is correct of course.
Post by: ccexplore on July 25, 2011, 01:18:06 AM
Quote from: spoiler (sketch only)
With n rectangles you can cover at most n/(n+1) of the triangle's area, by making all rectangles have the same height.[edit: correct a mistake in wording near the end]
n=1: if the original rectangle has base B and altitude H, and the rectangle's width is b', then simple geometry shows its height will be H (1 - b'/B). So the ratio of rectangle's area to whole triangle is 2 * (b'/B) * (1 - b'/B). You can then use calculus techniques (find where derivative of function is zero) to show that the maximum occurs at b'/B = 1/2, resulting in a rect/triangle ratio of 1/2 also. So f(1)=1/2.
n from n-1: Similarly, consider that the bottommost rectangle's width is b'. You get a smaller triangle with base being the top edge of the rectangle, where you should fit the remaining n-1 rectangles in optimal manner. With a bit of geometry, math and calculus similar to what we did for n=1 (which I'll gloss over because it's just literally doing the math), you wind up with this relation for f(n) the area ratio of recntangles to triangle: f(n) = 1 / (2 - f(n-1)).
Calculating the first few values by hand (starting from f(1)=1/2) readily shows that f(n) = n/(n+1), and then formally using mathematical induction and the recurrence equation above you can formally proved that f(n) = n/(n+1). Also as you do the math for the recurrence relation for f(n), you'll find that the value of b'/B ratio for optimal f(n)chop is itself always equals f(n), which gives you the construction method to realize f(n).
[edit: move edit to correct post!]
Post by: ccexplore on July 25, 2011, 01:40:19 AM
Quote from: spoiler
Instead of triangle, I think if we do the exercise on a trapezoid instead, and using 2 rectangles, one can show that the 2 rectangles must have equal height to maximize coverage of the trapezoid.
Back to the original triangle problem, you can see that the "strip" of triangle that spans over 2 consecutive rectangles in the stack, is a trapezoid. So using the "equal height" property we can show that each pair of consecutive rectangles, and therefore all rectangles, must have equal heights.
This gets us to the desired construction more directly, but notice we still end up with 2 maximization problems to deal with:
a) showing that we want equal height on the 2-rectangle-in-trapezoid problem
b) Even though we show that all rectangles must have equal height, it doesn't tell you what height to use to maximize coverage for the triangle (eg. you can have the n rectangles of equal but very small heights, so that the stack leaves most of the upper portion of the triangle not covered, obviously not optimal).
So I'm not sure if we're at a better place than before, but maybe the math for these maximization problems are slightly easier?
[edit: hey, here's an improvement. But you still have 2 maximization problems, but hopefully easier ones]
Quote from: "spoiler
Solve the following 2 problems:
1) the 2-rectangles-in-trapezoid problem, showing that the optimal arrangement is for both rectangles equal height.
2) the 1 rectangle in triangle problem, showing that the optimal arrangement is for rectangle's height be half the triangle's altitude.
With these two properties, we can go back to show that in the original problem, each pair of consecutive rectangles must be of equal height, and at the very top, the height of that top rectangle must equal the height of the "leftover triangle tip" that we run out of rectangles to cover with. Together we can find an explicit construction with explicit height value for each rectangle and we're done.
I'm still using calculus to solve #1 and #2, but with both problems involving only small number of rectangles, perhaps it's possible to handle them with pure geometric techniques instead?
[edit: hey, just notice the 2 sub-problems are the same]
Quote from: "spoiler
The 2-rectangles-in-trapezoid problem is totally equivalent to the 1-rectangle in triangle problem: to see this equivalence, just chop off two triangles from the trapezoid like this:
____
/| |\
/ | | \
/ | | \
----------
Post by: ccexplore on July 25, 2011, 03:29:42 AM
[edit: diagram attached, explanation below]
Quote from: spoiler
First, you can split any triangle by the altitude (top half of diagram) to get 2 right triangles, and apply the same reasoning to both "halves". So now lets look at one of the right triangles (bottom half of diagram).
If the rectangle's height is not exactly half of the original triangle's altitude, then the corner of rectangle on the hypothenus will be off the midpoint of the hypothenus. The rectangle splits the right triangle into 3 areas: the rectangle itself, and 2 smaller right triangles whose hypothenuses are 2 parts of the big right triangle's hypothenus. Take the smaller of the 2 right triangles and rotate it as shown in the diagram. Because it is the smaller of the two triangles, it will not reach or reach past the topmost vertex.
Now obviously this rotation preserves area, but notice that with this new shape of same area, you can readily identified it as 2 rectangles of identical width and height (and therefore same area) plus the leftover triangular "tip": as shown in the bottom right part of the diagram, you get this by extending the base of the rotated right triangle to form the 2nd top rectangle.
So what we're saying is that 2 * the area of the rectangle we're trying to maximize (ie. the bottom one) + the area of the leftover tip = the whole area of the new shape = the whole area of the big right triangle we started from. With the area of the tip being positive (or zero in the degenerate, maximal case where both smaller triangles are congruent, resulting in no tip), we see that we get 2 * area of rectangle we try to maximize is less than or equal to the area of the whole big right triangle, so area of rectangle must be less than or equal to half the whole big right triangle. This is just another way to say that the maximum area of rectangle is half the whole big right triangle, the result we want for the base case.
Post by: geoo on July 25, 2011, 04:16:07 AM
I still think the solution I found is a bit more short and elegant (but not quite so fully elementary as yours), even though technically it reduces the problem to an optimization problem, which has an obvious solution however:
Quote
Hint: Consider the shape of the area that is not covered by the rectangles.
Solution:Divide the tringle along the altitude into two halves and consider them separately (tringle from now on refers to one half):
The part of the triangle that is not covered by the rectangles consists of n+1 triangles which are similar to the main triangle, i.e. scaled versions of it. Let the scaling factors be denoted by l_i, 0 <= i <= n, they add up to 1, as the sum of the altitudes of the small triangles is the altitude of the main triangle. The area of each triangle is (l_i)^2*A where A is the area of the main triangle. So we want to minimize the sum over the squares of the l_i. It is kinda obvious that the value is minimal iff all l_i are equal (e.g. realize that you can lower the value if you got two l_i that are not equal by replacing both of them with their mean), proving our claim that heights of the rectangles are the same and of value h/(n+1).
(Alternatively this identity can be proven using the Cauchy-Schwartz inequality: let v = (1,...,1) and l the vector containing the l_i. Cauchy-Schwartz now implies <v,l>^2 <= |v||l| and equality iff v and l are linear dependent. Now the scalar product on the right is 1, as the l_i add up to 1, and |v|=(n+1)^2. So we got 1/(n+1)^2 as a constant lower bound on |l|, and the lower bound is reached iff all entries in l are the same.)
Post by: ccexplore on July 25, 2011, 10:27:49 AM
Quote from: spoiler
Picture the following: imagine coloring the non-exposed areas of each planet red, and then move each planet by translation (so no orientation changes) until they all merge into one sphere (possible since all planets are same size). [Note: we're not adjusting the coloring during the translation process; another way to think of it is to map each red point of each planet onto the surface of one planet]
I can show that during this translation process, the red areas of 2 different planets will never end up as overlapping areas on the merged sphere. This would show that the sum of red areas from all planets is less than or equal to the area of one sphere.
What I would like to then show is that every point on the merged sphere belongs to at least 1 red point of some planet, but unfortunately that is not true. For example, with just 2 planets, when we merged the red areas together, we're missing the set of points that form the boundary of the 2 hemispheres, namely a great circle. So I think what I need to do is also to show that the "missing points" always belong to the boundaries of red areas (this is the technical issue I need to resolve). With that established, then I can say their inclusion or exclusion will simply add or subtract 0 from the total area, and therefore doesn't matter whether we include or exclude them.
Anyway, I'll try to fill out the details when I have time. I find it hard to explain without a bunch of diagrams, so it's going to take some time to put everything down on paper even though intuitively the ideas are easy to grasp once seen. And my work week has started again.
Post by: ccexplore on July 25, 2011, 03:25:16 PM
Bonus question (still simple): Now you may stack pieces and then break them all in one go. What's the optimal solution then?
Hmm, it's still harder than the original problem, here's where I'm at:
Quote from: spoiler
I know the lower bound is ceil(log2(n*m)) = ceil(log2(n) + log2(m)), and the upper bound is ceil(log2(n)) + ceil(log2(m)), but I'm not sure yet which is the right answer.
Please don't hesitate to post puzzle you think some people may already know, probably they will be new to at least some. I didn't come up with my puzzles myself either.
Okay, here's a relatively famous one, hopefully it's new to at least one person but we'll see:
Problem description: You have 12 balls, all but one have identical weight. The "bad" one may have weight greater or less than the a "normal" ball. You have no further information about the actual values of the weight of either a normal ball or the bad ball.
You are given a scale. You can put a pile of balls on one end of the scale, and another pile on the other end, and the scale will either tip to the heavier side showing you which pile is heavier, or will show that the two ends are of equal weight. We will further stipulate that after using the scale as described above, you must take all balls simultaneously off the scale before you use the scale again on other piles of balls. (I'm not sure/don't remember if this really changes the solution, so I'll be conservative and make this part of the rule of scale usage; feel free as an additional exercise to establish that it does or does not matter.)
So we count a single "usage" of scale as taking any and all balls from a previous scale usage simultaneously off the scale, follow by putting 2 piles of balls of your choosing on each end of the scale, and finally reading the result (tellling you which pile is heavier, or that both piles are of equal weight). Your challenge is to find the minimum number of times you must use the scale to identify which one of the 12 balls is the bad ball.
================
To simplify things (read: I forgot the details of this part at the moment, so I won't make you do it, but feel free as an additional exercise), you don't have to prove optimality. You merely have to somehow arrive (by guessing or otherwise) at the correct minimum number, and then prove that it is sufficient, meaning that you can come up with a scheme provably guaranteed to always correctly identify the bad ball, using no more than this number of weighings.
Post by: EricLang on July 25, 2011, 08:39:44 PM
Post by: geoo on July 25, 2011, 11:18:24 PM
So I gave it a shot. I found a lower bound on the amount of weighings, and using that idea, I got a systematic approach to constructing the weighing procedure:
Quote
Each weighing gives you one ternary unit of information (henceforth referred to trit, just like in that one topic from ages ago, where ccexplore avoided the more natural naming for certain reasons
Now we try to construct a solution. I will henceforth refer to balls that have been verified to have the correct weight as 'verified', ones that are possibly too heavy but not too light as 'heavy', ones that are possibly too light but not too heavy as 'light', and ones we don't know anything about as unknown.
So we start off with 12 unknown balls. The first weighing has to be chosen so that independent of the outcome, it reduces the solution space to at most 9 possible solutions, as that's what fits into 2 trits. As we can only choose how many balls to put on the scale, there's not many solutions to scan through, and we find that we have to put 4 on either side. If the outcome is '=', then we got 8 verified balls and 4 unknown ones (1), reducing the solution space to 8 possible solutions. If the outcome is '>' or '<', then we got 4 verified balls, 4 heavy and 4 light balls (2), also reducing the solution space to 8 possible solutions.
Consider (1) first: we want to reduce the solution space to at most 3 possible solutions after the weighing, independent of the outcome. One will find that one solution to this is weighing 2 unknown balls against 1 unknown and 1 verified one. If the result is '=', then we verified the weighed ones and got 1 unknown ball left (1.1), i.e. 2 possible solutions. In the case '<' we got that the two unknown balls on the one side are light, and the unknown one on the other side is heavy, and the one we didn't weight is verified (1.2), reducing the solution space to 3 possible solutions. '>' is essentially the same with light and heavy switched (1.3). To solve (1.1), we simply weigh the unknown ball against a verified one, and get whether it is too light or too heavy. For (1.2), we weigh the two light balls against each other. If the result is '=', then they are verified and the heavy ball is indeed too heavy. If the result is '<' or '>', then the heavy ball is verified, and the light ball on the lighter side is too light while the other one is verified. (1.3) works analogously.
So let's consider (2). After a bit of searching, we see that if we weigh 2 light and 1 heavy balls against 2 light and 1 heavy balls, we can reduce our solution space sufficiently: Is the result '=', we got two light balls left (2.1), while the 6 weighed balls are verified, solution space reduced to 2. Otherwise, either one of the light balls on the lighter side is indeed too light, or the heavy ball on the heavy side is too heavy, so we got 2 light and 1 heavy ball (2.2), while the other 3 and the not weighed 2 balls are verified, solution space reduced to 3. (2.1) can be solved by weighing the two light balls against each other to see which of the two is really too light. (2.2) is analogous to (1.2).
Following this procedure, we are certain to get the solution after 3 weighings.
As for the problem with the planets, I think it's indeed a bit tricky to accurately prove that it is the surface of a sphere minus a set of measure 0. But I think I found a solid proof to this.
As for the second chocolate bar problem, you can tighten one of the bounds to match the other one, I think it's actually not so hard to see.
Post by: ccexplore on July 26, 2011, 12:55:49 AM
So I gave it a shot. I found a lower bound on the amount of weighings, and using that idea, I got a systematic approach to constructing the weighing procedure:
Wow, good job!
It's a tricky problem (and an easy one to forget the details off top of head because it's somewhat intricate), but not only did you nail it, but you have a very nice systematic approach that not only proves the weighing procedure is sufficient, it actually provides the logic behind how to come up with the procedure in the first place.As for the problem with the planets, I think it's indeed a bit tricky to accurately prove that it is the surface of a sphere minus a set of measure 0. But I think I found a solid proof to this.
My current progress on the problem reduces the measure-0 (aka "zero area") issue to an appeal to intuition, that we can consider the boundary curves for each non-exposed area from a sphere to each be a well-behaved curve that has measure 0. If we accept that we don't need to rigourously prove that particular assertion, then I think I can complete the proof. But again a bunch of words and diagrams that will have to wait. I think this is a reasonble concession, given that a rigorous proof seems likely more of an exercise in analysis (ie. the mathematical topic, not the general meaning of the word) than is the core concepts behind the proof.
As for the second chocolate bar problem, you can tighten one of the bounds to match the other one, I think it's actually not so hard to see.
Yeah, I'm pretty sure the two bounds only differ by at most 1, and I think I know which bound is the right one, but somehow I haven't convinced myself 100% yet. I guess that's what I get for saying the original problem is too obvious.
Post by: Clam on July 26, 2011, 01:52:07 AM
1. I'm at a cafe and I find a fly in my coffee. I ask the waiter to take it away and bring back another cup. However, when he comes back with a cup of coffee, I can tell it is the same coffee as before. How?
2. What occurs once in a minute, twice in a week and once in a year?
3. Imagine you are a taxi driver as opposed to a taxi drier or taxi diver and you are driving a 1978 yellow cab. Your passengers are an older couple, and they want to travel 6 miles. You are driving at 40 miles per hour with the tank one-third full, when, 2 miles into the trip, the tank is down to one-quarter full. Ten minutes later, the trip is over. What is the age of the cab driver?
4. I have five cupcakes in a basket. How can I give one cupcake to each of five people and still leave one in the basket?
5. How far can you go into a forest?
6. Why do black sheep eat less grass than white sheep?
Post by: ccexplore on July 26, 2011, 02:20:33 AM
4. I have five cupcakes in a basket. How can I give one cupcake to each of five people and still leave one in the basket?
Not my type of riddles, but nevertheless here's an answer I come up with for #4.
Quote from: spoiler
Imagine the basket in question is really the "basket" for a hot air balloon (ie. where the passengers would be located; maybe it's not really called a basket in English but humor me, or imagine instead maybe you have a ridiculous giant basket that can fit people in). If one of the receiving person is himself sitting inside the basket, you can give the cupcake to him while allowing the cupcake to remain inside the basket along with that person.
Since I didn't laugh nor groan, somehow I think the actual intended answer is something else.
[edit2: Okay, here's a more likely answer for #4, although it still doesn't fit into the groan/laugh category I was expecting]
[edit3: move position of edit2 in the post to intended place]
Quote from: spoiler
Give the cupcake and the basket to the fifth person, so the person can receive the cupcake while the cupcake remains inside the basket
[edit: here's a hint for #3, I'm pretty sure I know what the expected answer is]
[edit4: updated hint since "sentence" is not specific enough]
Quote from: "#3 hint/spoiler
Read the first sentence (up to but not including the word "and") carefully again.
Post by: Clam on July 26, 2011, 03:25:15 AM
Since I didn't laugh nor groan, somehow I think the actual intended answer is something else.
I guess you're more likely to groan if you see the answer instead of figuring it out for yourself. I like the creativity of your first answer though, very nice
(and yes, your second answer is the "right" one)
Post by: alfonz1986 on July 26, 2011, 11:03:11 AM
#3 my age is 25
#4 I give 4 cupcakes to 4 people and the 5th one I give to myself, keeping it in the basket
#6 black sheep are far more rare than white sheep
Post by: ccexplore on July 26, 2011, 12:04:40 PM
As for the second chocolate bar problem, you can tighten one of the bounds to match the other one, I think it's actually not so hard to see.
Okay, I finally got it, but somehow the proof ends up going much longer than I thought. It's not hard, but it feels nowhere as straightforward as the 1st chocolate bar problem. Maybe there's a better way about this that better appeals to logic and intuition:
Quote from: spoiler
Lemma: to reduce any set of rectangular pieces to 1x1 squares in K cuts, each rectangular piece must fit within one of the rectangles from the set of rectangles of dimensions 2^i x 2^(K-i), i ranging from 0 to K. This is both necessary and sufficient.
Proof by induction: base case (K=0): This is trivially true, with no cuts all pieces must already be 1x1 squares (and trivially true conversely), and they of course all do fit within a 2^0 x 2^0 = 1x1 rectangle.
Induction case (K ==> K+1): We need to show necessary and sufficient.
Sufficient: this is obvious. A 2^i x 2^(K+1-i) rectangle can always be cut down the middle into two 2^j x 2^(K-j) rectangles. So take any piece and consider the 2^i x 2^(K+1-i) rectangle bounding it. The same cut on the bounding rectangle will split the piece into one or two subpieces, one fitting in one of the 2^j x 2^(K-j) rectangle, the other (if any) fitting in the other rectangle of identical dimensions. Now consider stacking all pieces together to do this cut on all pieces in one go, and it's clear that with 1 cut, we have reduced all pieces into new pieces, all of which will fit within a 2^j x 2^(K-j) rectangle. Induction then shows that it's sufficent to use the remaining K cuts to get everyone down to 1x1.
Necessary: Let's say we have a rectangular piece that can't fit into any rectangles of dimension 2^i x 2^(K+1-i). I'll show that a single cut to that piece will always leave a rectangle that will not fit into any 2^j x 2^(K-j) rectangles, and therefore it can't be further reduced to 1x1 rectangles with only the remaining K cuts. And so to reduce everything to 1x1 with only K+1 cuts, all rectangular pieces must indeed fit into a 2^i x 2^(K+1-i) bounding rectangle.
There are a few subcases to examine. A diagram is probably easier to show and understand, but it's a hassle so instead I'll try words/algebra only:
A) the piece is so large that its area is larger than 2^(K+1). Then any way of splitting the piece in 2 must result in a piece of at least half the original area, so larger tha 2^K, which is the area of any rectangle of dimensions 2^i X 2^(K-i). So it definitely can't fit (anything that could fit must have area smaller or equal, not larger).
B) the piece has dimensions SxT, S >= T >= 1, and area (which happens to be S*T) smaller than or equal to 2^(K+1). So clearly T is smaller than or equal to 2^(K+1). The piece can't fit into any 2^i x 2^(K+1-i) rectangle, so in particular, consider the rectangle of dimension 2^(ceil(log2(T)) x 2^(K+1-ceil(log2(T))). The T part of the rectangle can fit against the 2^(ceil(log2(T)), so the S part must not fit against the other dimension, meaning S > 2^(K+1-ceil(log2(T))). [$]
Also note that 2^(ceil(log2(T))) = 2^(log2(T) + t'), where t' is what you add to log2(T) to bring it up to the ceil(log2(T)). Obviously t' < 1, so 2^(ceil(log2(T))) < 2^(log2(T) + 1), equivalent to T > 2^(ceil(log2(T)) - 1). [$$]
Now, if we do the 1st cut on the SxT piece across S, then the resulting two rectangles still has T in one dimension, and one of the two will have at least ceil(S/2) in the other dimension. We now need to show that we can't fit this ceil(S/2)xT subpiece into any 2^j x 2^(K-j) bounding rectangle. The relation T > 2^(ceil(log2(T)) - 1) shows that you need one side of the bounding rectangle to be at least 2^(ceil(log2(T))) to fit T, but then we have at most 2^(K-ceil(log2(T))) to try to fit ceil(S/2). But ceil(S/2) >= S/2 > 2^(K-ceil(log2(T)) (from [$]), so no fitting possible with a cut across S.
If we instead do the cut across T (assuming T > 1 so that you can even do such a cut), then the resulting 2 rectangles still has S in one dimension, and one of the two will have at least ceil(T/2) in the other direction. But ceil(T/2) >= T/2 > 2^(ceil(log2(T)) - 2) (from [$$]), so to fit ceil(T/2) we need one side of bounding rectangle to be at least 2^(ceil(log2(T)) - 1), leaving the other side of bounding rectangle at most 2^(K+1-ceil(log2(T))). But then as established earlier (from [$]), S > 2^(K+1-ceil(log2(T))) = 2^(K-(ceil(log2(T))-1)), so again no way to fit the ceil(T/2)xS subpiece into any 2^j x 2^(K-j) bounding rectangle.
QED
Now go back to the original problem, which is really a set consisting of a single NxM rectangular piece. The lemma we just proved shows that it has to fit within a 2^a x 2^b rectangle and then we know it can be reduced to 1x1 with a+b cuts. The lemma also shows that with a 2^c x 2^d rectangle of smaller (c+d) that the NxM piece can't fit in, you cannot reduced to 1x1 with c+d cuts only.
This effectively shows that we indeed need ceil(log2(N)) + ceil(log2(M)) cuts, because 2^ceil(log2(N)) x 2^ceil(log2(M)) is the smallest rectangle the NxM piece can fit within.
Post by: ccexplore on July 26, 2011, 12:26:28 PM
1. I'm at a cafe and I find a fly in my coffee. I ask the waiter to take it away and bring back another cup. However, when he comes back with a cup of coffee, I can tell it is the same coffee as before. How?
It seems there's really only one good answer to this:
Quote from: spoiler/my take
I rarely visit cafes but it seems like most of them have kind of "open counter" setup, as opposed to something like a restaurant where everything happens in a closed kitchen hidden from view behind double steel doors. At the very least I don't think they go out of their way to make what they do totally hidden.
With that in mind, it's pretty reasonble to say that you know exactly what the waiter did with the coffee because you were able to see how he handled the coffee from where you're sitting.
I somehow have a feeling that my answer is not the point of the question, but if the question is aiming towards other solutions, I feel I can argue that any other such solutions are inferior in some way:
Quote from: spoiler/my take
If you are indeed unable to actually see what the waiter did with the coffee, then any method you rely on to support your hypothesis that the coffee remained the same, can in principle also be explained by the waiter doing whatever it takes to make the second cup of coffee as identical as possible to the first coffee, including what you did with it before it was returned. For example, if you based it on temperature, or maybe something as crazy as you drop some specific chemical marker in the coffee before it was returned, it is conceivable (however unlikely) that the waiter could've done a bunch of stuff behind the scenes to mimic all the effects on the original coffee between the time you received it and the time it was returned, so that it really is a new cup of coffee that just happens to appear like the original cup under the set of tests you devise.
So given any situation in which you can't actually see what the waiter did, but you strongly suspect that he gave you back the same coffee, there is an alternative hypothesis in which the coffee is not the original. The probability of such alternative hypotheses may be astronomically small, but it's still non-zero.
So what I'm saying is that any solution in which you can't observe what the waiter actually did with your coffee, your certainty that the coffee was unchanged is less than the certainty when you can observe. Therefore the solution that you can observe what the waiter did is the superior answer.
======================
It wouldn't surprise me if the "real" solution is probably one that takes advantage of language ambiguity and other things, and ends up describing a situation that is not quite how you normally picture/interpret things based on the given statements (and thus making my proposed solutions all not applicable). However, while I've briefly considered that sort of reasoning, I've yet to find a good "alternative interpretation" that works well across all the given statements of the problem. But we'll see I guess......
Post by: Simon on July 26, 2011, 09:18:13 PM
You have a hollow cube-shaped box, measuring 5 x 5 x 5. You wish to completely fill out this box with wooden cubic blocks, but no filling block may stick out of the box after you're done. At your disposal are arbitrarily many cubic blocks of side lengths 1, 2, 3 and 4.
What is the smallest number of blocks necessary to fill the box? (Some proof of minimality would be nice, it's not that many cases fortunately.)
-- Simon
Post by: ccexplore on July 26, 2011, 09:32:58 PM
Okay, I finally got it, but somehow the proof ends up going much longer than I thought. It's not hard, but it feels nowhere as straightforward as the 1st chocolate bar problem. Maybe there's a better way about this that better appeals to logic and intuition
Hmm, my brain must be fried. I can explain it a bit easier than what I posted earlier, in fact this better captures the original intuition that led to the proof I posted.
Quote from: spoiler
Once again the key is the lemma that to reduce any set of rectangular pieces to 1x1 squares in K cuts, each rectangular piece must fit within one of the rectangles from the set of rectangles of dimensions 2^i x 2^(K-i), i ranging from 0 to K. [This is both necessary and sufficient.] I just find an easier way to explain the induction proof step:
Proof from case K to case K+1: the process of reversing a cut of any piece is to find the two resulting smaller pieces and join them back together at their cut sides. From case K, we have that the two smaller pieces must each fit inside a 2^i x 2^(K-i) bounding rectangle. Let T be the length of the common cut side of the two rectangles. Then the smallest 2^i that can fit T is 2^(ceil(log2(T))), any smaller and we can't fit length T. This means both smaller piece's bounding rectangles, the lengths of the non-joined sides must each be at most 2^(K-ceil(log2(T))), in order to have both rectangles each fit inside a 2^i x 2^(K-i) bounding rectangle. Now observe that joining the two bounding rectangles together at their common 2^(ceil(log2(T))) sides, results in a new bounding rectangle covering the original bigger piece before the cut, and this new bounding rectangle has one side of length 2^(ceil(log2(T))), and other side of length at most 2^(K-ceil(log2(T))) + 2^(K-ceil(log2(T))) = 2 * 2^(K-ceil(log2(T))) = 2^(K+1-ceil(log2(T))). So this new bounding rectangle for the pre-cut piece is a 2^j x 2^(K+1-j) bounding rectangle. Thus we've just proved that case K implies case K+1.
Below is an ASCII art example depiction of what I just described above, for the case where we join two 3x3 pieces back together to form the 6x3 piece they originated from before getting a cut. The 3x3's bounding rectangles can correspondingly be joined together to form an 8x4 bounding rectangle for the whole 6x3 piece:
XXXXXXXX
X***+++X
X***+++X
X***+++X
Post by: ccexplore on July 27, 2011, 10:07:20 AM
You have a hollow cube-shaped box, measuring 5 x 5 x 5. You wish to completely fill out this box with wooden cubic blocks, but no filling block may stick out of the box after you're done. At your disposal are arbitrarily many cubic blocks of side lengths 1, 2, 3 and 4.
What is the smallest number of blocks necessary to fill the box? (Some proof of minimality would be nice, it's not that many cases fortunately.)
Yeah, seems like a simple exercise in case analysis more than anything else. Maybe it's a sign for us to give this thread a rest.
Though I don't think I'd personally mind another alfonz1986-style physics problem or a Clam-style riddle.[/font]Quote from: spoiler
If there's a 4x4x4 cube then the rest has to be 1x1x1 to fit. You end up with 62.
If there's a 3x3x3 cube then the rest has to be 2x2x2's or 1x1x1 to fit, and to make use of 2x2x2's you have to put the 3x3x3 against a corner. It's pretty easy to see that you can fill the rest with at most 7 2x2x2's. You end up with 50.
With 2x2x2's only and nothing larger, it's pretty clear that you can't fit more than 8 of them, so you're clearly doing worse than 3x3x3. And 1x1x1's only is silly.
Post by: Clam on July 27, 2011, 10:54:55 AM
(Re. #1) It seems there's really only one good answer to this:
While that's not "the" solution (i.e. the solution given by the author of the puzzle), I guess the wording of the puzzle is vague enough to allow numerous answers. I'm not sure I understand your idea of an answer being "superior" to another, but that's probably just because I have a specific answer in mind, and it's not the same as yours. Actually, you were perilously close to "the" solution at one point:
Quote from: spoiler
You mention a "chemical marker"...
But rather than dissecting the scenario and debating possible answers, the point of these types of puzzles is to find a simple solution, groan (or laugh), and move on. Though I will say, despite me having some background in maths and physics, when I think of "logic puzzles", these kinds of riddles are the first thing that comes to my mind. Maths and physics puzzles are logical too of course, but (as we've seen) they often require some specific knowledge, which these riddles don't.
By the way, strictly speaking, the whole thing is a trick question since I don't drink coffee
Post by: ccexplore on July 27, 2011, 09:24:16 PM
While that's not "the" solution (i.e. the solution given by the author of the puzzle), I guess the wording of the puzzle is vague enough to allow numerous answers. I'm not sure I understand your idea of an answer being "superior" to another, but that's probably just because I have a specific answer in mind, and it's not the same as yours.
Yeah, don't take it too seriously. But it is a very logical argument don't you think?
Quote from: spoiler
I'm merely saying that if you can't actually see what the waiter did, then theoretically, the waiter can always make a second cup of coffee that nevertheless has characteristics as close to the original coffee as possible (with decreasing plausiblity the closer the characteristics are). You added sugar and cream? The waiter could've done that to your second cup of coffee also even though it's not usual practice, or the exact same thing that happened to you could've happened to a 2nd customer, and the waiter ends up swapping you and the other customer's coffees, and by coincidence both you and your customer added the same amount of sugar and cream. And so forth with many other scenarios. Even if you say you tested for your DNA, there is the theoretical (and disgusting
So what I'm saying is, the answer that you saw what the waiter did is the one where you have the least uncertainty about the coffee. What I glossed over of course, is that there can also be a small probability that what you saw happening is not necessarily what actually happened, as anyone observing a magician's act can attest to. So it was never really a watertight argument to begin with but hey, I was hoping at least it was funny to think up all these implausible alternatives that you can't rule out 100% when you lack the observation.
Post by: ccexplore on July 27, 2011, 09:30:17 PM
But rather than dissecting the scenario and debating possible answers, the point of these types of puzzles is to find a simple solution, groan (or laugh), and move on.
Well #2 #3 and #6 fits the bill the most in that regard so far, at least I'm unable to find any other sensible interpretation leading to different answers (although I must admit, I tried to see if I can come up with a different answer to #6 after peeking at the answer
).And in theory, to a person coming from a culture unfamiliar with sheep (Inuit say?), #6 isn't necessarily general knowledge, but I digress.
I'm also aware that dissecting these kinds of riddles is not really the point, on the other hand, I'm fascinated because I feel that closely examining these kinds of riddles highlights some interesting points for natural language processing and other related topics.
Post by: ccexplore on July 27, 2011, 09:44:51 PM
So I disagree that you must fall to the level of Clam riddles to have generally accessible logic puzzles. Also, the problem is that some of the riddles aren't really about logic at all. I do agree they can be good for a laugh though, especially the less they are about logic.
Post by: alfonz1986 on July 27, 2011, 11:01:54 PM
Hence the cup of coffee can be whatever you want it to be.
Ok, and back to the not-so-logical puzzles:
You're in a DIY store looking to purchase some items for the house. If 1 costs $0.50, 12 costs $1.00 and 144 costs $1.50 .....
What is it you are buying?
Post by: Simon on July 27, 2011, 11:11:55 PM
This one here should be a bit more in the logic department again. I'll translate the story that goes with it, because it's really neat.
Have I told you how the mollusc tried to trick me?
Mollusc is the nickname of a collegue of mine, she teaches biology at our school. She got the name from her students as she has a faible for molluscs. One day, she sat next to me in the teachers' room, and raged about an exam she had just graded. "For years, I explain the seven classes of molluscs to the kids, and each year, the tests about this subject are catastrophically bad!"
She gave me a sheet of paper, which showed five pictures of some random slugs or worms. The task was to classify these five animals. "Here are the six best tests.", she continued. "Each of these kids gave exactly two correct answers, the twenty others didn't even get a single one right!" And then she announced, making sure everyone in the room could hear it, "Every somewhat intelligent person knows what these animals are, don't they?" Of course, I had no clue, and the mollusc knew that exactly. I carefully examined the six tests. Below the pictures, the students had written:
Student A: 1. Worm Snail, 2. Hairy Back, 3. Worm Snail, 4. Head Footer, 5. String Worm
Student B: 1. Worm Snail, 2. Band Worm, 3. Hairy Back, 4. Worm Snail, 5. Beetle Snail
Student C: 1. Scratch, 2. Clam, 3. Band Worm, 4. Amoeba, 5. Tusk Shell
Student D: 1. Wheel Animal, 2. Clam, 3. Worm Snail, 4. Clam, 5. Monoplacophorum
Student E: 1. Snail, 2. Clam, 3. Amoeba, 4. Insect, 5. Tusk Shell
Student F: 1. Worm Snail, 2. String Worm, 3. Amoeba, 4. Amoeba, 5. Tusk Shell
Luckily, I was able to classify all animals from these answers, without knowing even a single one. The mollusc stared at me with an open mouth. She never tried to trick me again. Can you do it as well?
-- Simon
Post by: alfonz1986 on July 27, 2011, 11:43:43 PM
The only way you could walk two miles south, five miles west and two miles north again while managing to return to the starting point is if you began on the north or south pole. Polar bears live in the north pole, hence the colour of the bear is white
Post by: Simon on July 28, 2011, 12:00:21 AM
- South pole is not possible even if there were bears, since one cannot walk south from there.
- North pole is not the only point. There are more points on earth that allow walking as given. Each of these points lies 2 miles north of a latitude circle whose circumference is 5 miles, or 5/n miles with n nonzero natural number, or even equal to the south pole. Since a circle with radius 2 miles has circumference greater than 5 (even on the earth surface, since the earth is large enough), none of this extra stuff can be close to the north pole, so all of the additional points lie close the south pole -- even though south pole itself isn't a possible starting point, but north pole is.
Post by: alfonz1986 on July 28, 2011, 12:56:36 AM
Post by: ccexplore on July 28, 2011, 01:08:20 AM
Quote from: spoiler
You have 12 correct answers to distribute across 5 questions. Notice that there are no questions with same answer from 4 or more people, so each question is answered correctly by at most 3 people. Let's focus on question 1, 2, and 5 since each has the same answer from 3 people. Notice also that for each of those 3 questions, the remaining answers within the question are all different.
If only 2 of the 3 such answers are correct, then we have 6 more correct answers distributed amongst the remaining 3 questions, with no same answering appearing more than 2 times in each question. So actually all 3 questions must be answered correctly by two people. This includes the 3-same-wrong-answer question. But none of the 3-same-answer questions has remaining answers that are the same from two people, ruling out this case.
So all 3 answers are correct. We have 3 more correct answers to distribute amonst the remaining 2 questions, so at least one of the two questions are answered correctly by 2 people. It can't be the amoeba because doing so results in someone answering 3 different questions correctly, which mollusc say isn't the case. We're then left with the two "worm snail" answers from question 3, making it the correct answer for that question. Now the only student left we haven't completely determined his 2 correct answers to is B, and the only question left is 4, so we're done:
1: worm snail
2: clam
3: worm snail
4: worm snail
5: tusk shell
[edit: minor wording edit]
Post by: Simon on July 28, 2011, 01:38:27 AM
Quote from: spoiler
Another possible initial approach with the pidgeon hole principle: For any 3 of the six tests, there exist 2 ouf ot the 3 who share a correct answer (because we have six answers to five questions). Observe that A, B, and C share only the answer to question 1...
-- Simon
Post by: alfonz1986 on July 28, 2011, 01:44:39 AM
Solution for mollusc puzzle (click to show/hide)
Post by: Simon on July 28, 2011, 01:59:04 AM
Edit: I want geoo to reply now, stating that animal 1 is a scratch, 4 is an insect, and 5 is the beetle snail. >_>
-- Simon
Post by: ccexplore on July 28, 2011, 11:05:37 AM
), enough to satisfy geoo, say. Ultimately I think the main concepts behind the proof is not too hard to visualize, but there are many technical details, enough that a full proof pretty much turns into a full-on exercise in advanced math. (Indeed as mentioned earlier, I glossed over the 0-measure issue by simply asserting that curves have area 0. Take a class in uni if you really want to know why. ) [edit: minor reformatting]Quote from: spoiler
First, a lemma A to characterize visibility and exposure:
Let P be a point on a planet. Ignoring other planets, visibility of P from other points in space can be characterized as follows: take the plane tangent to the planet at P. The plane divides 3D space into two sides. All points on the tangent plane, as well as all points in space on the opposite side of the plane from the planet, will have full visibility to P. The remaining points outside the planet that's on same side of plane as the planet, will have no visibility to P, the line of sight being blocked by some other point on the planet. It's pretty easy to see when you consider drawing the line of sight from P to another point in space.
Lemma A has a corollary (call it lemma A'): for P to be a non-exposed point, all other planets must be fully on the same side of the tangent plane as P's planet. If another planet even merely "dips" slightly past the plane onto the other side, or even just tangent to the plane, then P becomes exposed.
In order to address the 0-measure issue, we also need lemma B concerning cases where a plane is tangent to more than 1 planet: in that case, at least one of the tangent points will be a point on a boundary curve enclosing a non-exposed region (henceforth referred to as "a boundary point"). The key is to note that to be a boundary point, in all sufficiently and arbitrarily small neighborhoods of the point, you can find one point that's non-exposed, and another point that's exposed. The basic idea of proving this is to consider what happens when you perturb the tangent plane around one of the tangent points. To give the basic gist of the argument, let's consider a simpler but roughly analogous situation, with 3 circles from left to right, and a line tangent to all 3. Perturb the tangent line around (say) the rightmost tangent point, by rotating the line a small amount around that point, and then shift the line in an orthogonal direction until it becomes tangent to the rightmost circle again. It's not hard to see that when you rotated the line counterclockwise (even by an arbitrarily small amount), the line ends up not touching the other two circles, while in the opposite direction (again even by an arbitrarily small amount, and even accounting for the shift to re-tangent the line to the rightmost circle) the line ends up fully intersecting both other two circles.
The 3D version of this observation is a little more intricate but basically the same idea. You can perturb the plane around one of the planet's tangent points, so that all other planets came off the plane on the same side as the chosen planet. By lemma A', you just found a non-exposed point on the chosen planet. You can also perturb the plane in a different direction such that it intersects all of the other planets, which by lemma A', means you just found an exposed point on the chosen planet. Lemma B proved.
Now consider the vector from a planet's center to a point on the surface, call it the orientation vector for the point. Lemma C: you can't have two non-exposed points on different planets whose orientation vectors both point in same direction. This is not hard to see by noting that the tangent planes on those two points are parallel, or in the degenerate case, one plane tangent to both planets at the two points. It's then easy to see that with the parallel tangent planes, one planet will always dip past the tangent plane of the other planet, so lemma A' tells us one of the two points must be exposed. For the degenerate case, lemma A' already showed that both points will be exposed. Lemma C proved.
One final lemma D: given any direction, we can find at least one planet that has either a non-exposed or a boundary point, whose orientation vector points to the chosen direction. The proof is basically a continuity argument involving "sweeping" the tangent plane orthogonal to the orientation vector in the orthogonal direction. It's not hard to visualize and see that you can always end up moving the plane to a position such that every planet ends up on the same side of the plane (particular the side opposite to the direction of the orientation vector), with one or more planets tangent to the plane itself. By lemma A' and lemma B, you've found a non-exposed point if exactly one planet's tangent to the plane, and a boundary point if multiple planets are tangent to the plane.
=============
Now back to the main problem. The trick is to imagine merge all planets into one planet by translation only (ignore their solidity and imagine that they can freely pass through each other, and recall that they are all of same size), but don't adjust the exposed/non-exposed/boundary classification of the planet's points (ie. keep them classified to their original condition even as you move the planets). Translation means no orientation changes, in particular, it preserves directions of orientation vectors. With this transformation, lemma C transform to the property that after the merge, the non-exposed regions from two planets cannot overlap. Lemma D transforms to the property that after the merge, every merged point of the merged sphere correspond either to a non-exposed point of some planet, or to a boundary point on at least one of the planets.
So we get sum(area of non-exposed regions) + area(remaining points on merged sphere) = surface area of one planet. Regarding the remaining points, they are the result (by Lemma D's implication post-transformation) of tranaslating all the boundary curves onto the merged sphere, possibly with some overlap to each other. So their total area on the merged sphere is no larger than sum(area of each boundary curve). We now appeal to the boundary curves being normal, well-behaved curves, so we know each has area 0 and therefore the total is still area 0. Thus area(remaining points on merged sphere) = 0, leaving us with sum(area of non-exposed regions) = surface area of one planet. QED.
Post by: geoo on July 29, 2011, 04:34:47 PM
Quote
Here's to wrap up geoo's #4 (the sphere/planet problem) once and for all. [...]Nicely sketched out proof. I use essentially the same idea of merging the planets into one and the tangential plane for each unit vector, and also make use of most of your lemmata, but I went with one simplification:
Quote
As you proved, if we got two or more points on one of these bordering tangential planes, they are exposed. Now pick any two planets, and any plane that touches both; the bordering tangential planes that touch 2 or more planets are obviously a subset of all these planes. Now for each pair of planets, the union of all the point pairs that are touched by such a plane are 1 great circle on each of the planets, thus a measure-0 set. Now there are only finitely many planets, so the union of these great circles from all pairs is still a null set. Now we translate/merge all the spheres into one, and the merged set of these great circles has the actual exposed points as subset, and has measure 0. So the exposed points on the merged sphere have measure 0 as well. The details to show that this is correct have to be copied from your proof.
I find your proof to the second chocolate problem pretty complicated though. I sketched out my line of thought below, and I don't think it has any leaks.
Quote
Let (m,n) denote a rectangle of the given dimensions. We know that if we break a single rectangle apart parallel to one of the sides, we always get two new rectangles. Now if we ignore the smaller one and only continue with the larger one, we have simplified the problem and analysing this, we get a lower bound (it's easy to see that it's also an upper bound because we can just fit the smaller piece somewhere under the big one). So lets model the breaking operation on (m,n) as replacing either of the two values with a new value larger or equal to its half. We know that after the breaking, both values must be 1. So we see that the operations on m and n are independent, i.e. it doesn't matter whether we start with m or n (rotating or anything else doesn't matter, obviously). So for each m and n, always dividing it by 2 gives us a lower bound, and to get this lower bound to 1 or lower, we need ceil(log m) and ceil(log n) respectively.
I thought about some of the other problems as well, and came up with possible solutions to the unsolved ones and also some alternative solutions:
Quote
Have I told you how the mollusc tried to trick me?They're all Clams.
Nice puzzle though, first looks like brute force, until you see that there's three columns with a triple but no double entries.
Quote
You're in a DIY store looking to purchase some items for the house. If 1 costs $0.50, 12 costs $1.00 and 144 costs $1.50 .....You're buying sticks of constant length with the aim lay out iterations of some kind of Koch curve to decorate your room, and thus have to break the sticks into bits, and you're counting the substicks you get. But thinking of it, 144 should cost $2.00 then. Hmm...
What is it you are buying?
Perhaps this is the answer then:
Quote
You're buying digits.
On to Clam's puzzles:
Quote
1. I'm at a cafe and I find a fly in my coffee. I ask the waiter to take it away and bring back another cup. However, when he comes back with a cup of coffee, I can tell it is the same coffee as before. How?You ask the waiter to take it away, but nowhere is it said that he actually does. So it is possible that the coffee remains on the table, and the waiter brings just another cup, and 'it' in the last sentence refers to the coffee on the table. Then it obviously is the same.
4. can also be solved if there happens to be a cupcake baking device in the basket.
5. The forest is a subset of the sphere. For each point in the forest, take the supremum of the radii of balls around that point that are still completely in the set. Now take the supremum S over the radii. For any epsilon > 0, you can walk S - epsilon into the forest.
6. As black sheep absorb more sunlight than white sheep, they naturally gain more energy from the sunlight, thus requiring them to gain less enery from eating grass.
Simon doesn't want to post the infinite hats problem yet (and instead posted the boring 5^3 puzzle), so I'm gonna post 3 hard but elegant algorithmic puzzles here (sorry, but here you really need at least a bit of knowledge about complexity theory), so Simon can get a clear conscience that he's not posting too many puzzles while solving too few himself.
#C1: You got a mobile that is essentially arranged like a binary tree, i.e. each node has either two children nodes (in the mobile, this would be like a bar with submobile on each of its ends), or is itself a leaf with a positive integer weight. Now the mobile is not in equilibrium however, that is there is some submobile (subtree), where the weights of the left and the right submobile differ. The task is to design an algorithm that finds out how many of the weights you have to change at minimum (to an arbitrary, possibly non-integer weight) so that the mobile gets into equlibrium. Run time complexity: O(N log N), where N is e.g. the number of leaves.
#C2: You're given a subset of the decimal digits {0, 1, ..., 9} and a positive integer N, and you're to find out whether there is a positive multiple of N that only consist of these digits when written in decimal, and if there is, the smallest of these multiples. Run time complexity: O(N)
#C3: (This is more of an algebra problem) You're give a polynom of degree N with coefficients being integers (integers isn't really necessary here, but for computational purposes their are convenient). Your task is to find out whether it has root of degree greater than 1 in the complex numbers, i.e. a linear factor that appears at least twice. Run time complexity: O(N^2) I think
EDIT: Decided to add #C4:
Consider the following exercise, found in a generic linear algebra textbook.
Let A be an n × n matrix. Prove that the following statements are equivalent:
- (a) A is invertible.
- (b) Ax = b has exactly one solution for every n × 1 matrix b.
- (c) Ax = b is consistent for every n × 1 matrix b.
- (d) Ax = 0 has only the trivial solution x = 0.
one can proceed by showing that (a) implies (b), that (b) implies (c), that (c) implies (d),
and finally that (d) implies (a). These four implications show that the four statements are
equivalent.
Another way would be to show that (a) is equivalent to (b) (by proving that (a) implies
(b) and that (b) implies (a)), that (b) is equivalent to (c), and that (c) is equivalent to (d).
However, this way requires proving six implications, which is clearly a lot more work than
just proving four implications!
I have been given some similar tasks, and have already started proving some implications.
Now I wonder, how many more implications do I have to prove? Can you help me
determine this?
Run time complexity: O(N+M) I think, where N is the amount of statements and M the amount of implications already proven.
Hint about an algorithm required to know:
Quote
There's Tarjan's algorithm to detect strongly connected components, which has runtime O(N+M), where N is the amount of nodes and M the amount of edges.
Post by: ccexplore on July 30, 2011, 01:44:27 AM
6. As black sheep absorb more sunlight than white sheep, they naturally gain more energy from the sunlight, thus requiring them to gain less enery from eating grass.
Hmm, photosynthetic sheep? What farm are you on again?
Quote
Simon doesn't want to post the infinite hats problem yet (and instead posted the boring 5^3 puzzle), so I'm gonna post 3 hard but elegant algorithmic puzzles here (sorry, but here you really need at least a bit of knowledge about complexity theory)
Yeah, I thought about posting a (relatively simple) computer science one yesterday (it's the one about linked list and loop detection, some of you probably heard of it anyhow), but just find that it's actually quite hard to rephrase the problem without making use of any computer science terminologies, and still be precise enough to disallow completely unintended answers breaking down the expected model of computation, time, and memory. Yours are even more technical to state. (Actually, C2 seems more like a number theory problem.)
I'm definitely going to take a break on this thread and play around with the SMS custom levels stuff happening in that other thread. I think most of these problems are probably beyond me (or at least I'd need to go back to my old algorithm textbook to refresh memory on stuff).
Post by: ccexplore on August 01, 2011, 07:29:17 PM
#C1: You got a mobile that is essentially arranged like a binary tree, i.e. each node has either two children nodes (in the mobile, this would be like a bar with submobile on each of its ends), or is itself a leaf with a positive integer weight. Now the mobile is not in equilibrium however, that is there is some submobile (subtree), where the weights of the left and the right submobile differ. The task is to design an algorithm that finds out how many of the weights you have to change at minimum (to an arbitrary, possibly non-integer weight) so that the mobile gets into equlibrium. Run time complexity: O(N log N), where N is e.g. the number of leaves.
I haven't really bothered working on any of the problems, but I do have a Clam-style solution to C1:
You don't need to change any weights, since balance is determined by torque not weight. You can just adjust the fulcrum at each bar to balance the torques.
Post by: geoo on August 04, 2011, 07:44:59 AM
I haven't really bothered working on any of the problems, but I do have a Clam-style solution to C1:That bears the (easier) question: how many of these do you have to change?
You don't need to change any weights, since balance is determined by torque not weight. You can just adjust the fulcrum at each bar to balance the torques.
Quote
I'm definitely going to take a break on this thread and play around with the SMS custom levels stuff happening in that other thread. I think most of these problems are probably beyond me (or at least I'd need to go back to my old algorithm textbook to refresh memory on stuff).Apart from the algorithm for strongly connected components, you don't need any too advanced algorithms, actually. I guess you're familiar with things like the euclidean algorithm, sorting and breadth-first search.
The solutions are simple if you can find the idea, each algorithm can be described in 1-2 sentences.
EDIT: For those interested, there is a detailled solution of problem #5: http://www.cs.rug.nl/~grl/ds05/sumproduct.pdf
A proof to the light bulb problem hasn't been posted yet either, but it's rather easy.
Post by: Simon on October 01, 2011, 01:54:54 AM
General notes. These are hat riddles. A hat riddle involves a team of contestants who have to work together, and must decide on a strategy for the quest at hand. They will know the protocol in advance. After agreeing on a strategy, they may not communicate from that point onwards, and everybody will receive a hat in some color determined at random. While each contestant may look at other people's hats, they may not see their own color. Their quest is to name their own hat color. The puzzle itself is to formulate a protocol for the team that ensures a given number of correct guesses.
Hat puzzle 0. Three contestants get either a red or blue hat each. Everybody may see both other persons' hats. Everybody receives a piece of paper and a pen. Simultaneously, i.e. without seeing what everybody else writes down, they must write "red", "blue", or nothing at all. They win if nobody guesses incorrectly, and at least one person has guessed correctly. Find a strategy that ensures a chance of winning greater than 1/2.
Hat puzzle 1. There are countably many contestants, each numbered with a unique natural number. Each gets either a red or blue hat. Everybody may examine the hat color of only one other contestant. He can choose freely which one to examine, and the examined doens't gain any information by this. Simultaneously, everybody must then guess his own color. Find a protocol that ensures infinitely many correct guesses.
Hat puzzle 2. Again, we have countably namy contestants indexed with the natural numbers, and everybody has a red or blue hat, but now every contestant may see all hats of the contestants who have a greater number than himself. Guessing is simultaneous. Find a protocol that ensures only finitely many wrong guesses. Hint: Use the axiom of choice. ;-)
-- Simon
Post by: chaos_defrost on November 06, 2011, 04:06:48 AM
This has a 3/4 chance of a win and a 1/4 chance of everyone being wrong
I'll think about 1 and 2 later
Post by: chaos_defrost on September 01, 2012, 02:28:24 AM
There are six numbers, which can be expressed as the products of two numbers ab, ac, ad, bc, bd, and cd. Five of these products are, in no particular order, 2, 3, 4, 5, and 6. What is the sixth?
Post by: ccexplore on September 01, 2012, 05:39:26 AM
Quote from: answer
12/5 (or 2.4)
Quote from: what I haven't proved logically
I can narrow it down to 5 possible answers only one of which is rational, so that's the one I pick as the answer. I haven't yet worked out why logically the irrational ones are not actually possible. (Oh, and talk about unintentional bad puns.).
Post by: chaos_defrost on September 01, 2012, 05:47:05 AM
Post by: ccexplore on September 01, 2012, 06:13:50 AM
Quote from: complete answer
Without loss of generality we'll say that the 4 numbers are A B C and D, and that the missing product not given is C*D. Then notice that (A*C)/(B*C) = A/B = (A*D)/(B*D). So of the 5 given numbers, the ratio of one pair of them is equal to the ratio of another pair of them, and then the remaining number must be A*B. This allows us to quickly narrow it to A*B=5, as 4/2=6/3. Now notice that (A*C)*(B*C)*(A*D)*(B*D) = (A*B)*(A*B)*(C*D)*(C*D). So the product of the other 4 numbers, 2*3*4*6, is 5*5*(square of the number we're looking for), and now we can solve the equation to find the number.
Post by: chaos_defrost on September 01, 2012, 06:33:50 AM
Quote from: answer
We know that ab*cd = ac*bd = ad*bc. Of the five given numbers, the only two pairs of two numbers that give the same result if multiplied is 3*4 and 2*6. In order to make the last product the same, we need the number that when multiplied by 5 equals 12, or 12/5.
Post by: ccexplore on September 01, 2012, 07:18:14 AM
I knew it should be something more direct like that for a logic puzzle, but just drew a blank myself and went a more brute-force way.
Post by: Proxima on September 01, 2012, 12:01:29 PM
Quote
Contestant #1 examines #2, #2 examines #3, #3 examines #1, and all three guess they have the same colour as what they see. At least one must be right. Repeat with every trio of numbers (3n+1 3n+2 3n+3) and you get infinitely many correct guesses
Post by: Simon on September 01, 2012, 01:18:57 PM
I will simply reveal the solution of #2, because it needs a rigorous set theory argument, and even then it's counterintuitive.
Quote
Consider the space of functions N -> {red, blue}, called F. The contestants define an equivalence relation ~ on F as follows. Two hat distributions f, g: N -> {red, blue} are equivalent iff there exists a natural number n with f(k) = g(k) for all n >= k. (I.e. the hat distributions differ only on finitely many elements smaller than some n.)
Take the quotient set F/~, i.e. the set of all equivalence classes. By axiom of choice, the contestants agree on a choice function c: F/~ -> F, such that for any class B of equivalent hat distributions, c(B) is a certain distribution in B.
During the actual contest, each contestant determines the equivalence class B of the hat distribution at hand. Ignoring/changing a finite number of hats cannot change the equivalence class of any hat distribution, so each contestant, no matter how far up in the sequence, is able to determine B. Each contestant n now guesses c(B)(n). By definition of ~, only finitely many candidates get it wrong. (The probability of each candidate being right is still 1/2, so you can't turn this into a measure space.)
Product puzzle is nice with a straightforward short solution. I didn't get it in the 10 minutes and got lost in details.
-- Simon
Post by: Simon on September 01, 2012, 11:42:38 PM
A steam train is travelling between Chicago and New York City. Its staff consists of an engine driver, a stoker, and a conductor. Their names are Miller, Jones, and Babbitt, in no particular order. Three academics are travelling with the train, Dr. Miller, Dr. Jones, and Dr. Babbitt. (I.e. there are six people in total.) We have the following clues:
a) Dr. Babbitt lives in Chicago.
b) Dr. Jones earns exactly $2,500.00 per month.
c) The conductor lives in a town halfway between Chicago and New York City.
d) The conductor's neighbor is one of the passengers and earns exactly 3 times as much per month as the conductor.
e) The academic who shares the conductor's last name lives in New York City.
f) Miller has recently beaten the stoker at chess.
What is the name of the engine driver?
-- Simon
Post by: mobius on September 02, 2012, 12:49:02 AM
Quote
Miller
-Miller can't be the stoker (f).
-Jones is the conductor. Because; Dr. Jones lives in NYC. (e)
-Dr Miller is the neighbor of the conductor:
-(Dr Jones's earning: ($2,500) isn't exactly divisible by 3= can't be neighbor.
-Dr. Babbit lives in Chicago; not -between there and NY.= can't be neighbor
-If Dr. Miller is the neighbor then he can't live in NY, we already know Babbit lives in Chicago so Jones is the one living in NYC. (c, e)
I usually figure these puzzles out by making a list and drawing lines. It helps me a lot but then when I go to explain my answer; fail.
Post by: Simon on September 02, 2012, 01:21:37 AM
-- Simon
Post by: Proxima on September 02, 2012, 02:00:51 AM
The suspects are close friends, and all of them know who the guilty party is. Furthermore, they may or may not have switched clothes, so you can't tell which of them is which -- let's just refer to the three as A, B and C in the order they're standing, from left to right.
Your task is to find the guilty party (that is, which of A, B, C is guilty, not which tribe) in the fewest number of questions possible. All questions must have "yes" or "no" as the correct answer. Each question must be directed at a particular one of the three; if you ask two (or all three) of them the same question, that counts as two (or three) towards your total.
So, what is the smallest number of questions to do this?
Post by: ccexplore on September 02, 2012, 05:12:16 AM
Quote from: progress so far
I can do it in 5 questions.
Start by asking each of them the same question, something like "is 1+1=2?" whose answer is "yes" if answered truthfully. Classic and Shadow must answer differently, and with 3 lemmings and only 2 possible answers (yes/no), 2 of the lemmings must answer the same way and other lemming different. Highland cannot be the one who gave the different answer, since that would've meant Classic and Shadow gave the same answer. So this means the lemming who gave the different answer cannot be Highland, and then based on the answer given, you can determine whether he's Classic (always truthful) or Shadow (always lying).
Now you're just two questions ("is A guilty?", "is B guilty?", both directed at the different-answer lemming from above) away from the guilty party.
Post by: chaos_defrost on September 02, 2012, 06:02:06 AM
Quote from: progress so far
There are 18 possible states of nature: the 6 orders of the three Lemmings and which Lemming, in line, did it.
Determining who the Highland Lemming is is essential to us (so we can avoid asking him questions about who did it), so we need to ask a question that is integral to this. Ask the center Lemming if the Lemming on the left's tribe name is earlier alphabetically than the one to the right.
If he answers "yes": If he is the Classic Lemming, then Left is Highland and Right is Shadow. If he is Highland Lemming is this one, then we'd be OK asking either of the others about the thief. If he's the Shadow Lemming, then Left is also Highland and right is Classic. So, we direct future questions to the right Lemming.
If "no", the opposite situation happens, and no matter who's in the middle, the left Lemming is safe to ask. We've also narrowed the possible number of states of nature to 12.
getting to it with 3 more questions is easy: ask a factual question and then ask about 2 of the Lemmings if they did it, but I think 3 questions might be possible. Give me a second.
EDIT: Got it down once again
Quote from: more progress
Ask the definite not Highland: "If I asked the other Lemming that is either Classic or Shadow if you are guilty, will they say "yes"?"
If yes, not guilty
If no, guilty
Now ask the definite not Highland: "Can the other two Lemmings possibly both answer "yes" to the question 'is the center Lemming guilty?'"
CHgS - no
CHSg - yes
CSgH - no
CSHg - yes
SCgH - no
SCHg - yes
SHgC - no
SHCg - yes
so if you get a "yes" the right Lemming is guilty, and if you get a "no" the center one is. If you got a "no" on question 2, the left is guilty.
I think I did this right, I think?
Post by: Proxima on September 02, 2012, 11:49:40 AM
Post by: Simon on September 02, 2012, 01:29:55 PM
Quote
Does the final answer use 3 questions? Does it identify either Classic or Shadow as an intermediate goal? If so, how many questions to this goal and how many afterwards?
-- Simon
Post by: mobius on September 02, 2012, 05:18:25 PM
refer to the picture attached
You can only make the machine move by turning cog A. In its current state; it won’t move. Ignoring torque problems;
-Without removing any cogs, reposition 3 cogs to make a working circuit where all the cogs turn by turning A clockwise. (they all must be touching at least 1 other cog).
(you can either describe it or edit the picture if you're feeling creative)
There were at quite a few other questions on the same problem but I can't remember them right now I have to find the book. (like; which direction will k turn...)
Post by: Proxima on September 02, 2012, 09:23:34 PM
Re Simon's questions about my problem:
Quote
3 is correct. Your second question is a little ambiguous, but if you meant "do you have to identify one lemming as being certainly non-Highland?" then yes. And there are three possibilities for the guilty party, so you can't distinguish them with a single yes/no question, so you must have two left.
Post by: GuyPerfect on September 03, 2012, 03:55:58 AM
Quote
It's impossible to identify the Highland Lemming with just one question, so at least two questions need to be asked.
Let's say that the following exchange takes place:
Speaking to Lemming A:
Q: Are you the guilty Classic Lemming?
A: Yes
Q: Is True the same as False?
A: No
The only possible circumstances that could produce this outcome would be if Lemming A is the Classic Lemming and is guilty.
Post by: ccexplore on September 03, 2012, 06:58:17 AM
Post by: Proxima on September 03, 2012, 12:47:41 PM
Insane Steve's solution already has the least possible for all three values (and yes, the minimum is 2). Your solution doesn't work for the reason ccexplore stated. (In case it wasn't clear, the Highland lemming can choose whether to lie or tell the truth for each answer separately).
Post by: GuyPerfect on September 03, 2012, 06:23:41 PM
(In case it wasn't clear, the Highland lemming can choose whether to lie or tell the truth for each answer separately).
You're right. It wasn't clear. It looks to me like you said the exact opposite:
(but, if asked a yes/no question, they will always respond one way or the other).
The way that looks to me is this: in response to yes/no questions, a Highland Lemming will either always answer yes or always answer no.
Post by: chaos_defrost on September 03, 2012, 07:41:07 PM
I am thinking of an integer between 1-9 inclusive. You are allowed to ask me any two yes or no questions to figure out my number, which I will truthfully answer yes or no to. I will also not say anything if you ask a question I can't actually answer truthfully.
Give a system that finds my number every time.
Post by: chaos_defrost on September 03, 2012, 08:22:44 PM
http://puzzle.cisra.com.au/ -- here's a site that runs a puzzle contest every year, and this year's contest looks like it's going to start any day now: though most of the questions look like they are going to be presented the week of the 1st of October.
I'd definitely be up for making a team if there's three other people here interested in these kinds of puzzles. Given that we aren't Australian students we wouldn't be eligible for prizes but it might still be fun.
Post by: Simon on September 03, 2012, 10:02:45 PM
Quote
Need to gain a trit (ternary information) with each question, so we must use possible silence in return to the questions. Generate random information somehow, and keep it hidden; e.g. flip a coin secretly.
First question is "Is the number in {1, 2, 3}, or is it in {4, 5, 6} and did I flip heads?", with "and" binding stronger than "or". Use a similar second question to weed out the number from the appropriate group of three.
-- Simon
Post by: chaos_defrost on September 03, 2012, 10:15:54 PM
My solution was a bit different but similar in idea:Quote
Ask as the first question "I am also thinking of a number; it is either 3.5 or 6.5. Is your number larger than mine?" If the number is in {1,2,3} you'd get a no, if it is in {7,8,9} you get a yes, and if it is in {4,5,6} you get no response. Ask a similar 2nd question to distinguish between the three in the proper set.
Post by: Simon on September 07, 2012, 05:40:14 AM
12 balls, one is either lighter or heavier than all others.
Use a scale three times to determine which ball has what exact quality.
We call a ball "normal" if it is certainly not the single odd ball.
We call a ball "red" if it is either normal or heavier than the normal balls.
We call a ball "blue" if it is either normal or lighter than the normal balls.
Weighing I:
Put 4 balls on each side.
Case I a: Both sides are equal.
We now have 8 normal balls and 4 unknown ones.
Weighing I a II:
Put 3 unknown balls on one side, and 3 normal balls on the other.
Case I a II a: Both sides are equal.
We now have 11 normal balls and 1 unknown one. Weigh the unknown ball
against any single normal one for the end result.
Case I a II b: The 3 unknown balls are heavier than the 3 normal ones.
Weigh one of the red balls against another red ball to see which of
the 3 red balls is heavy.
Case I a II c: The 3 unknown balls are lighter than the 3 normal ones.
Weigh one of the blue balls against another blue ball to see which of
the 3 blue balls is light.
Case I b: One set of 4 balls is heavier than the other.
We now have 4 red balls, 4 blue ones, and know for sure that the unweighed
4 balls are normal.
Weighing I b II:
Left side: 2 red, 2 blue
Right side: 1 blue, 3 normal
Case I b II a: Both sides are equal.
All balls from weighing II must now be normal.
We have 2 red balls and 1 blue ball remaining from weighing I which
were not part of weighing II. Weigh the 2 red balls against each other.
If one is heavier, it's the odd ball, otherwise the blue ball is light.
Case I b II b: The left side is heavier.
The red balls from the left side stay red, all other red balls become
known as normal. Weigh the 2 red balls against each other. If one is
heavier, it's the odd ball. If they are equal, then the single blue
ball from the right side of weighing II must be light.
Case I b II c: The left side is lighter.
Weigh the two blue balls from the left side against each other to see
which is the light ball.
New weighing puzzle:
You have 2 black balls, 2 grey balls, 2 white balls. Among each color, one ball is heavier than the second. The three light balls are all of the exact same weight, as are the three heavy balls.
Your task to label each ball as heavy or light. You may use an ordinary balance scale (telling which side is heavier, if any) a total of two times.
-- Simon
Post by: chaos_defrost on September 07, 2012, 07:26:18 AM
Quote
Weigh one black ball and one grey ball on one side, and the other black ball and one white ball on the other.
If it balances, We have BL = WR = GO, and GL = BR = WO. (L is left balance, R is right, O is off the scale). Weigh any pair to determine which is the heavy trio and which is the light ones.
If it fails to balance, then we KNOW the heavy side has the heavy black ball, and the light side has the light black ball: There's no way for the side with the light black ball to be any "lower" on the scale than balancing. We also know that the other ball on the heavy side is at least as heavy as the other ball on the light side, as if it weren't the scale would balance instead. So we know the weights of the black balls, and that one of the grey/white balls is at least as heavy as one of the other color. I will call this ball that we know is at least as heavy as one other ball "heavyish."
Take the two white/grey balls you weighed and place them on one side, and the two you didn't and place them on the other. If the side with the "heavyish" ball is lighter, then you weighed the two light grey/white balls in weighing one. If it's heavier, then you have the heavy white/grey balls on that side. If they balance, you have one of each, but remember that the "heavyish" ball is on a known side, and MUST be paired with the lighter ball of the other color. No matter what, you know which grey and which white ball is light, and which is heavy.
Good puzzle. I'd not seen it and it took me almost an hour to actually get to the answer.
Post by: chaos_defrost on September 07, 2012, 07:43:27 AM
I am thinking of an integer between 1 and n inclusive (assume you know n when you are asking). You can ask me any three yes or no questions this time, but the following things are changed:
1) Instead of answering yes or no, I will instead respond by raising my left or right hand. One means yes and one means no, but you don't know which is which to start.
2) If you ask a question I cannot answer truthfully, instead of remaining silent, I will either answer the yes or no question with either the choice with the larger probability of being true, or that with the smaller probability. I will answer all ambiguous questions consistently also; that is, I will ALWAYS give either the larger or smaller probability answer, but you again do not know which to start. If you ask a question with a 50/50 chance of being yes or no, I'll answer randomly.
What is the largest n for which there exists a definite system to always guess my number correctly? n = 4 is pretty trivial (ask factual question, do binary search), but is it possible for n>4? I get this feeling it isn't, but I mean
Post by: Proxima on September 07, 2012, 01:22:55 PM
Here it is anyway. It's very similar to Steve's.Quote
Weigh one black, one grey against one black, one white.
If they balance, the heavy black is on the same pan as a light ball and vice versa, so simply weighing the blacks against each other will give the full result.
If one side goes down, it contains the heavy black. In addition, the grey and white you used are either both heavy or both light, or the one on the side that went down is heavy. These possibilities can be distinguished by weighing the same grey and white together against both blacks.
Insane Steve's number puzzle:
Quote
"Is it the case that your number is greater than 4 if and only if raising your right hand means yes?"
Regardless of which hand means yes, you will raise the right hand if the number is greater than 4, the left if it isn't. It's similar to the classic truth-teller / liar puzzle: by asking "If I were to ask you which road leads to the village, would you say yes?" his truth-teller / liar status is made irrelevant by being called on twice, so that if he lies, his lies cancel each other out. Here, calling the detail of which hand means yes twice makes it cancel out, so it becomes equivalent to the situation where the right hand always means yes. Therefore, by binary search we can distinguish the numbers 1 to n where n is at most 8.
Post by: chaos_defrost on September 07, 2012, 08:37:29 PM
Post by: chaos_defrost on September 08, 2012, 10:06:45 PM
Also double post for something else I found:
http://puzzle.cisra.com.au/ -- here's a site that runs a puzzle contest every year, and this year's contest looks like it's going to start any day now: though most of the questions look like they are going to be presented the week of the 1st of October.
I'd definitely be up for making a team if there's three other people here interested in these kinds of puzzles. Given that we aren't Australian students we wouldn't be eligible for prizes but it might still be fun.
Also, this contest is now open for registration. So far geoo and I have expressed interest and we can add two more people to the team, so if anyone else wants to do this, let us know.
Post by: Proxima on September 08, 2012, 11:54:18 PM
Post by: Simon on September 09, 2012, 03:01:44 AM
The puzzles seem to be shower puzzles (you might get an idea while showering just as well as while pondering about them full power), so time shouldn't be an issue.
Steve's and Proxima's solutions to the 6-ball weighing puzzle were correct!
-- Simon
Post by: chaos_defrost on September 09, 2012, 06:11:27 AM
We do have four interested now, but we'd need a team name before we can register. It also asks for each person's name and an e-mail for each team member but since we wouldn't be going for prizes I don't see a problem using pseudonyms if you aren't wanting to give your real name.
Post by: chaos_defrost on September 20, 2012, 03:44:32 AM
May not be the best idea to post an answer publicly since it is from a currently-being-scored test and there's really very few actually decent tests like this, but I have an answer that I'm pretty sure is right (EDIT: On second glance I've made a mistake and I've not got a neat way to do it yet. One moment please).
Suppose you build a tetrahedral pyramid out of spheres, such that the first row has one sphere, the second 3 in a triangle, the third 6, and so forth. Without using a calculator or any sort of program, how many spheres are there in a one million (American million, so one thousand thousand) row high tetrahedral pyramid?
Post by: ccexplore on September 20, 2012, 05:58:57 AM
I've included the correct answer as calculated by computer program below (which means I too don't have a way to do it yet that satisfies the puzzle's rule of no rote machine computation). The idea is so that when you think you have the answer, you can check it against the number below to see if you have it right or not.
Quote from: the computer is always right ;-)
166667166667000000
Post by: Simon on September 20, 2012, 06:18:07 AM
Quote
166,668,666,667,000,000
I sent the method to Steve via PM, the multiplications are broken into hand-computed steps, so maybe he'll find an error later.
Edit: Yeah, found the mutliplication error myself, so cc's number is verified. As I already wrote in the PM: The deem careful bookkeeping a major part of intelligence as they don't allow computers, but require everything computed by hand.
-- Simon
Post by: chaos_defrost on September 20, 2012, 07:58:44 AM
My other favorites, as a probability type person:
An ant is placed on every vertex of each of the following solids. At the same time, and at the same speed, they randomly pick an adjacent vertex with equal probability and try to move there along the edge of the solid connecting them. Calculate the probability that, after the move, all ants end up on different vertices and no ants ever cross paths if they are placed on:
I) A regular tetrahedron
II) A cube
III) A regular octahedron
IV) A regular dodecahedron
V) A regular icosahedron
I've managed I-III (barring math errors) because I'm really bizarrely good at probability maps, but I get the feeling I'm going to need to find some kind of relation to get IV and especially V. Seriously, V is apparently so lol it's not even on the Power test, it was a later addition to another test and is supposed to be one of the most difficult problems.
Post by: Simon on September 20, 2012, 09:21:40 AM
-- Simon
Post by: Proxima on September 20, 2012, 01:35:55 PM
Quote
The triangular numbers (I assume I'm allowed to take this as known) are governed by the quadratic formula n^2/2 + n/2. Therefore the tetrahedral numbers, being their sums, must be governed by a cubic formula.
The first five tetrahedral numbers are 1, 4, 10, 20, 35. Take the difference of each pair of terms: 3, 6, 10, 15. (Yes, we knew this already, but it's part of the method.) Do the same again: 3, 4, 5. And again: 1, 1.
If we start with the cubes (1, 8, 27, 64, 125) and take differences three times, we get a sequence of 6s. Therefore the tetrahedral sequence has a cubic term of n^3/6.
Multiply the tetrahedral numbers by 6 and subtract n^3 from each: 5, 16, 33, 56, 85. Take differences of this sequence and we get 11, 17, 23, 29 and then 6, 6, 6. The squares have second differences of 2, so this is a quadratic sequence with quadratic term 3n^2.
Subtract 3n^2 from each term and we get 2, 4, 6, 8, 10 which is obviously 2n.
This gives the full formula for the tetrahedral numbers: (n^3 + 3n^2 + 2n) / 6.
Thus T(1000000) = 10^18 / 6 + 10^12 / 2 + 10^6 / 3 = 16666... + 50000... + 33333 = 16666716666700000.
Post by: Proxima on September 20, 2012, 05:10:20 PM
An ant is placed on every vertex of each of the following solids. At the same time, and at the same speed, they randomly pick an adjacent vertex with equal probability and try to move there along the edge of the solid connecting them. Calculate the probability that, after the move, all ants end up on different vertices and no ants ever cross paths if they are placed on:
I) A regular tetrahedron
II) A cube
III) A regular octahedron
IV) A regular dodecahedron
V) A regular icosahedron
My answers to I-III:
Quote
I. 2/27
II. 8 / 3^7
III. 15 / 2^10
Post by: chaos_defrost on September 21, 2012, 01:38:13 AM
- the octahedron is a special case as each vertex has four paths) but it's proving a bit tricky: Especially since a theoretical f(6) can have a couple of different probabilities depending on how the space is mapped.A couple more ant probability problems, these of my design (at least I haven't seen them elsewhere).
I) You place two ants on opposite corners of a square. Each ant randomly moves to an adjacent corner along a side at the same time. If the ants hit the same corner or cross paths they explode, if not they will again move to an adjacent corner along a side at the same time, again exploding if they cross. What is the probability the ants will eventually switch places from their original positions without exploding?
II) Same scenario as I, only now the ants start on opposite angles of a hexagon.
III) Same scenario as I and II, only now the ants start on opposite vertices of a regular octahedron.
I admittedly have not obtained a "100% sure" answer to 3, but am working on it.
Post by: Simon on September 21, 2012, 08:03:26 AM
-- Simon
Post by: chaos_defrost on September 21, 2012, 06:15:24 PM
If you decide you can rotate or mirror the octahedron, and re-label which ant is ant A and which is ant B, there's really only six states of nature: both ants on starting vertices, both ants on center square, one edge apart, both ants on center square on opposite corners, one ant on starting vertex one in center, one ant on opposite starting vertex one in center, and both ants on opposite starting vertices (the desired state). The reason I don't quite have an answer is that some of the possible loops are a bit tricky to close up, which I wasn't quite expecting when I posited the question.
EDIT: Alright I have a "close approximate" answer, I'm not sure how feasible an exact answer is but I have it within, say, .01%
EDIT2: I should elaborate, in my problems use of a calculator is ok
Post by: Proxima on September 21, 2012, 06:28:46 PM
Quote
First, assume that after an explosion, the ants keep moving, so that after n moves there will always be 4^n equally probable move sequences.
The probability of success after 2 moves is 1/8 (2 out of 16 sequences -- they could move either way round the square).
The probability of success in exactly 4 moves is 1/64 (4 out of 256 -- the first ant must backtrack on move 2, so there are two choices for which way it moves first, two choices for which way it goes round on moves 3 and 4. The second ant never has any choice, as it must always avoid the first ant.)
Similarly, the probability of success in exactly 6 moves is 1/512, and in 2n moves is 1/8^n, so the overall probability of success is the sum of the powers of 1/8, which is of course 1/7.
Post by: chaos_defrost on September 21, 2012, 07:08:42 PM
Hexagon is deceptively tricky:
There's a few too many different states of nature to run a Markov chain unless you just want to compute it with a program, but note that most of the states aren't ever reachable from the current state.
I do have an exact fractional answer for the hexagon, since there's a way to do it without explicitly using Markov chains (sort of)
Post by: Simon on September 27, 2012, 02:35:31 AM
Rules: You are the white box, and in each step, you can switch places with a neighboring piece (use cursor keys). Purple pieces may only be entered/switched vertically, and the green pieces, horizontally. The object is to move the labelled green piece to the left column.
-- Simon
Post by: chaos_defrost on September 27, 2012, 05:59:11 AM
Answers for the harder shapes in the exploding ant problem:
Hexagon:
Quote
There are two important things to this one:
1) Vertically mirrored positions on the hexagon, if you align it so the starting corners are on top and bottom, are probabilistically equivalent.
2) After any move, the ants are ever only on opposite corners, or they are on corners connected by an edge. I will call a situation where the ants are on opposite corners "open" and on where they are on connecting corners "closed".
The ants start in an open position, and are both three corners from their goal. I will refer to this position as "open-3", or O3. If we consider mirrored states to be equal to each other in terms of how far the ants are from the goal state, there are three other open positions, "open-2," "open-1," and "open 0," which I will call O2, O1, and O0. O0 is our goal state.
From any open state, the ants have a 50% chance of moving to a new open state, and a 50% chance of moving to a closed state. If the ants move to an open state, they will be a different number of spaces away from the goal, with a 50/50 chance of moving in either direction. So, if the ants are in state O3, they can only move to O2, but if they are in O2 or O1, they have can move to a closer or farther open state with equal probability.
If the ants are in a closed state, the next move there is a 25% chance they will explode, a 50% chance they will move to a new closed state, and a 25% chance they will move to an open state. Since the ants can only move to one possible open state, and the desired state is open, I will denote each closed state with the number of the open state the ants will be in if they move to it. Thus, we have "closed-3," "closed-2," "closed-1," and "closed-0," or C3, C2, C1, and CO. A move where the ants move from an open state to a closed state will keep the number of the state the same. If they move to a new closed state, it will, like the open states, shift in either direction with equal probability. So, if the ants are in C3 and move to a new closed state, it can only be C2, if they are in C0, they can only move to C1, and either of the others can shift either way with equal probability.
The odds that an ants eventually reaches the desired state O0 before an explosion is equal to the sum of the probabilities of reaching it from the states it can go to times the probabilities of going to those states. The ants can only ever reach the goal state from O1 or C0, but it is possible to set up a system of 7 equations in 7 variables (a simplified Markov Chain, if you will) to show the possible movements. In these equations, the variables are the probabilities of reaching O0 before exploding from each state:
C0 = 1/4 + 1/2C1
C1 = 1/4O1 + 1/4C0 + 1/4C2
C2 = 1/4O2 + 1/4C1 + 1/4C3
C3 = 1/4O3 + 1/2C2
O1 = 1/4 + 1/2C1 + 1/4O2
O2 = 1/4O1 + 1/2C2 + 1/4O3
O3 = 1/2O2 + 1/2C3
It can be done by hand (although it's kind of tedious, I used a system of equations solver), but if you solve for O3 you get 183/1126.
For the octahedron:
Quote
I'd just go with a Markov chain here. The trick is noticing that, while there's a LOT of orientations of the ants, there's really only seven different states of nature possible if you describe them in general terms:
1) Explosion
2) Ants on opposite vertices (desired state)
3) Ants on starting vertices
4) Ants on adjacent corners of the center square of the octahedron (align it so the starting vertices are on the top and bottom)
5) Ants on opposite corners of the starting square
6) One ant on starting vertex, the other on a center vertex
7) One ant on opposite vertex, the other on a center vertex
This can be best modeled with a Markov chain, and is a special kind where all paths eventually reach either of state one or two. The state matrix is:
[1 0 0 0 0 0 0]
[0 1 0 0 0 0 0]
[1/4 0 0 1/2 1/4 0 0]
[3/16 1/16/ 1/16 3/16 0 1/4 1/4]
[1/4 1/16 1/16 0 1/8 1/4 1/4]
[3/16 0 0 1/4 1/8 1/4 3/16]
[3/16 0 0 1/4 1/8 3/16 1/4]
I won't go into the computations too much, but the probability of ending in state 2 starting in state 3 is about 10.37%
Post by: Minim on September 27, 2012, 07:03:16 PM
That kind of puzzle reminds me of Rush Hour, where the cars and trucks had to be moved in a certain way and you had to get the red car off the board.
Post by: Simon on October 22, 2012, 03:39:33 PM
The task is to answer the following five questions correctly. Each comes with one correct and three false possible answers.
Q1. What is the lowest-numbered question with B as correct answer? A) Q1, B) Q4, C) Q3, or D) Q2.
Q2. What is the answer to question Q4? A) answer D, B) answer A, C) answer B, or D) answer C.
Q3. What is the answer to question Q1? A) answer D, B) answer C, C) answer B, or D) answer A.
Q4. How many questions have D as their correct answer? A) three, B) two, C) one, or D) none.
Q5. How many questions have B as their correct answer? A) none, B) two, C) three, or D) one.
The same site regularly runs quizzes with psychological contests, e.g. "From the numbers 1 through 100, choose a number. You win if you choose the lowest number which no other participant has chosen." Others call for most popular answers similar to Family Feud, e.g., name a dinosaur which as many other participants as possible will also name. I feel inclined to run a couple of such questions on the Lemmings Forums, getting answers via PM, and revealing the results after 3-6 days. Are people interested in such things? (Name a useless L2 skill other than Diver *grin*)
-- Simon
Post by: ccexplore on October 23, 2012, 01:21:04 AM
The same site regularly runs quizzes with psychological contests, e.g. "From the numbers 1 through 100, choose a number. You win if you choose the lowest number which no other participant has chosen." Others call for most popular answers similar to Family Feud, e.g., name a dinosaur which as many other participants as possible will also name. I feel inclined to run a couple of such questions on the Lemmings Forums, getting answers via PM, and revealing the results after 3-6 days. Are people interested in such things? (Name a useless L2 skill other than Diver *grin*)
Sounds fun, I'm interested.
Post by: Proxima on October 23, 2012, 12:38:59 PM
The task is to answer the following five questions correctly. Each comes with one correct and three false possible answers.
Q1. What is the lowest-numbered question with B as correct answer? A) Q1, B) Q4, C) Q3, or D) Q2.
Q2. What is the answer to question Q4? A) answer D, B) answer A, C) answer B, or D) answer C.
Q3. What is the answer to question Q1? A) answer D, B) answer C, C) answer B, or D) answer A.
Q4. How many questions have D as their correct answer? A) three, B) two, C) one, or D) none.
Q5. How many questions have B as their correct answer? A) none, B) two, C) three, or D) one.
Quote
First, neither A nor B can be the correct answer to Q1 without an obvious absurdity.
If D is the answer, then B is the answer to Q2, so A is the answer to Q4. That means D must be the answer to Q1, Q3 and Q5, but D being the answer to Q3 contradicts D being the answer to Q1.
Therefore, C is the answer to Q1, B is the answer to Q3, and the answer to Q2 is not B, so the answer to Q4 is not A. If it's B then we have a similar problem: D must be the answer to Q2 and Q5, but D being the answer to Q2 contradicts C being the answer to Q4.
Therefore, C is the answer to Q4 (it obviously cannot be D), which makes D the answer to Q2. This means no other question can have D as correct answer. Just one question so far has B as correct answer, so the answer to Q5 must be B or D, but it cannot be B.
This gives us the full solution: Q1 - C; Q2 - D; Q3 - B; Q4 - C; Q5 - B.
Post by: Simon on October 23, 2012, 12:55:40 PM
-- Simon
Post by: chaos_defrost on October 29, 2012, 10:05:59 PM
(If you don't have access to the puzzle group boards on that site let me know and I'll give it to you; you need this access to view the thread with the puzzles.)
Post by: Proxima on November 04, 2012, 11:12:58 PM
I have found this variant of the 15-puzzle: http://homepages.cwi.nl/~tromp/oriscript4.html and you need to enable Javascript.
Rules: You are the white box, and in each step, you can switch places with a neighboring piece (use cursor keys). Purple pieces may only be entered/switched vertically, and the green pieces, horizontally. The object is to move the labelled green piece to the left column.
Got it in 40. I think this is the best that can be done.
Post by: chaos_defrost on March 04, 2013, 02:13:52 AM
1) You work an incredibly exciting job doing quality control work for a factory that produces board games. There is one rule to the cards that are created for the game:
"If a card has a circle on the front, it MUST have a yellow back."
You have the following four cards in front of you, all of which have a shape of some sort on one side and a color on the other. What card(s) must you flip over in order to make sure the rule is followed? Also, only flip the card(s) you have to flip. Inefficiency will not be tolerated.
2) So you get board checking cards for the bored game and take a new job as a bartender. This bar also has one rule, which you may be pretty familiar with:
"If a person orders an alcoholic drink, they MUST be at least 21 years of age."
It's a bit slow at your bar and there's currently only four people there. They are represented below with cards. One one side is the drink that the person has ordered, and on the other side is the person's age. What "card(s)" must you "flip" in order to make absolutely sure that the rule is followed? Again, only flip the card(s) you have to.
Got that? Let's see how you did.
Quote
On the shape/color question, I'm pretty sure you flipped the card with a circle on it. Yea, that's one of them: You need to know if that circle card has a yellow back or not. You may have flipped the yellow card, also. That.... was a mistake. You actually have to flip the red card, and not the yellow one.
In layterms, the reason you have to flip the red card is to make sure that it doesn't have a circle on it. As for the other two cards, obviously the rule doesn't apply to cards with squares, so you can ignore that card. The rule also does not say that cards with yellow backs have to have circles on them. A square card with a yellow back does not break the rule.
In logical terms, flipping a card tests one of the four variations of the conditional statement of the rule. The circle card tests the original conditional, the square card tests its inverse (if not p, than not q), the yellow card tests its converse (if q, then p), and the red cards tests its contrapositive (if not q, then not p). In order to test whether the statement is true in all cases, you have to test the original statement and its contrapositive. You cannot deduce anything about the truth of a statement's converse or inverse from the original statement, except that either both are true or both are false.
If you missed that, don't worry. Less than 1/4th the population gets this question right.
As for the drinking question, you have to check the beer drinker to see if he's at least 21, and the 18 year old to see if he's not drinking an alcoholic drink. Here's what interests me about this problem:
1) Almost 60% of the population gets this problem correct, but
2) These two questions ask EXACTLY the same thing, just with different wordings.
As a species, humans are apparently really bad at tasks like this. However, for some reason when we apply rules like this to social settings (such as needing to be 21 to buy liquor), our minds re-wire themselves somehow to be able to do this task. More people will get the first problem wrong and the second right than will get both right, and they are the same question.
I get the feeling this forum will have a much higher than average success rate, but I'm curious.
Post by: Clam on March 04, 2013, 09:08:02 AM
Quote from: spoiler just in case this spoils it
Make it a serious crime to serve circles to red cards and ask again (:
The social setting is quite strong here, because of the legal implications. So while it is a question of logic, people will simply memorise each case in the bar situation for fear of the consequences. The cards are unimportant, unless you actually have the job in (1) and could get fired for screwing up. So while logically-minded people like us on LF will (should?) get this, sadly most people either can't apply the logic or just don't care enough to think it through.
Post by: chaos_defrost on April 13, 2013, 05:37:41 AM
I flip a coin 100 times. All 100 times, the coin comes up heads. On the 101st flip, is the probability of heads coming up:
1) more than 50%
2) exactly 50%
3) less than 50%
Lemmings forum you people are very good at problems like this, make me proud
Post by: ccexplore on April 13, 2013, 07:08:14 AM
Yes, I know what the "real" answer is, but don't say you didn't see this coming. ;p
Post by: chaos_defrost on April 13, 2013, 07:29:42 AM
Quote from: spoiler just in case this spoils it
Yep, exactly correct. One of those things that bothers me way too much as a statistician is the perfect of the populous who picks 3) because "tails is due OBVIOUSLY DUUUUH"
Post by: GuyPerfect on April 13, 2013, 01:54:13 PM
The game Earthbound (aka Mother 2) has a few rare items that have a 1/128 chance to drop after defeating particular enemies. Heck, it has some common items that are also that likely to drop from certain enemies. But the most notorious of these items is the Sword of Kings, the only weapon Poo can equip that won't lower his stats.
The Sword of Kings can be found only by defeating an enemy called Starman Super, and at a 1/128 rate at that. Starman Super only appears in one dungeon in the game, and they're gone forever after you complete that dungeon. So, unsurprisingly, people spend a lot of time in that dungeon to get that sword.
Last time I played the game, I counted how many Starman Supers I defeated. I went through exactly 256 of them and did NOT get my Sword of Kings. What is the likelihood, as a percentage, of that happening?
Post by: chaos_defrost on April 13, 2013, 06:45:59 PM
Post by: GuyPerfect on April 13, 2013, 08:24:27 PM
Let's say that I wanted to have a less than 1% chance of leaving that dungeon empty-handed. How many Starman Supers would that take?
Post by: Proxima on April 13, 2013, 09:10:54 PM
This equals .01 when n = ln .01 / ln (127/128) = 587.156. Since you can only try an integer number of times, take the next higher integer, 588.
Post by: GuyPerfect on April 15, 2013, 02:42:11 PM
Here's one I came up with last night, and this one I don't already know the answer to, so surprise me!
I'm currently working on hacking the GBA Pokémon games and a brief statistical curiosity comes to mind. Within the data structure for individual Pokémon is an encrypted 48-byte section comprised of four 12-byte chunks. The order of the chunks is determined by examining another value in the data structure, which is entirely random.
Let's call the four data chunks A, B, C and D. They can appear in any order, such as ABCD, ABDC, ACBD, ACDB, ADBC, etc. There are 24 such combinations. The order is determined by taking that randomly-generated field from elsewhere in the data structure, and taking the remainder of its division by 24. Or "modulus 24", despite that actually being the wrong word for the operation. (-: Since the value that determines the chunk order is entirely random and generated when a Pokémon is encountered in the wild, there's effectively a 1/24 chance of a Pokémon having any particular chunk order. (This isn't entirely true, because the randomized value is 32 bits and 4294967296 doesn't divide evenly by 24, but let's just pretend that it does)
As part of my practical testing, I'm going to go into the game and keep catching Pokémon until I have at least one with every one of those 24 chunk orderings. The problem in its simplest form is that I have a 1-in-X chance of getting something, and I want to get X of them. Pretending I could start out with 0 Pokémon and begin catching from there, about how many would I have to encounter to get all 24 orders? Let's use a 99% likelihood as the target.
Post by: Proxima on April 15, 2013, 04:59:10 PM
I don't know of a simple way to calculate the exact answer, so I'll be lazy and use the first approximation.
1 - 24 x (23/24)^ n = .01 =>
n = ln .0004 / ln (23/24) = 183.837
Let's check the accuracy of this approximation. Let n = 183, then:
24 x (23/24)^183 = 0.00994828
24C2 x (22/24)^183 = 0.00003354
24C3 x (21/24)^183 = 0.00000005
The terms become small very quickly, so it looks like the total will still be under 0.01.
Post by: Simon on July 16, 2013, 11:43:19 AM
Thue-Morse Sequence
Construct a sequence (an) for n natural, an taking values only in the two distinct symbols A and B, in the following way. Begin with a0 = A. Repeat the following forever: Take the already constructed initial word, duplicate it, and append that to the end of itself. Flip all values of the inserted block, i.e., all A become B, all B become A.
The construction process thus starts with A, AB, ABBA, ABBABAAB, ABBABAABBAABABBA, ...
Prove that the entire sequence (an) is triplet-free. A triplet is a substring anywhere in the sequence together with two repetitions of itself immediately following it. So, ABABAB is a triplet, but BBAB is not.
-- Simon
Post by: chaos_defrost on August 18, 2014, 03:13:28 AM
I am thinking of an integer > 10, which I will call x.
Let a be the conversion of x expressed as a number in base 10 to hexadecimal.
Let b be the conversion of x expressed as a number in hexadecimal back to base 10.
x is the geometric mean of a (expressed as a string of digits in base 10) and b.
Solve for x. There should be 2 solutions (thanks, Simon!).
To clarify, if, for example, you thought x = 24:
a = the representation of 24 in base 16, which is 0x18 (or 18).
b = the representation of 24, as a number in base 16, as a number in base 10, which is 36.
We want x to equal the geometric mean of 18 and 36, both expressed in base 10. Since 24 is not the geometric mean of 18 and 36, this is not the answer.
EDIT: @Simon's last puzzle, this is definitely not a rigorous solution but strikes me as the major block here:
The conjecture is true iff every step ends with a string of two different letters. The string starts with AB, so no appending will add two of the same letter to the end of the previous block. The string appended will always end with the pattern AB, BA, AB, BA, AB, BA, etc. satisfying the first statement.
Rigor can bite me
Post by: mobius on September 13, 2014, 04:23:46 PM
which of the following does not belong?
a - large green square
b - large red circle
c - large green circle
d - small green circle
Post by: Simon on September 13, 2014, 04:50:33 PM
This of course has no logical solution and we can only guess what the problem author wants.
-- Simon
Post by: mobius on September 13, 2014, 04:56:55 PM
You don't consider this a logical puzzle? Strictly speaking; C can only be correct as all the others 'do belong' since they share things. But I guess it's more of a lateral puzzle
Post by: chaos_defrost on September 13, 2014, 05:00:24 PM
A. It is the only square.
B: It is the only red shape.
C: (see previous statements)
D: It is the only "small" shape.
My answer is A. "Large" and "small" are subjective terms. To a red-green colorblind person, all of B-D can possibly be described as a "brown-ish circle" when weighed independently.
True or false: This is a true statement.
Post by: Zaphod77 on October 03, 2014, 05:19:17 AM
True or false: This is a true statement.
yes.
the statement is true or false. whichever it is, there is no contradiction. without more knowledge, we can't tell.
as for the previous, the question implies that among any possible grouping of three and one, only one of the groupings has a shared characteristic between three that is not shared with the fourth. following from this, the only such characteristic is presence or lack of a unique characteristic. c is the one that lacks a unique characteristic.
and i got the color card problem right first try.
Post by: Proxima on October 03, 2014, 01:57:43 PM
Post by: chaos_defrost on October 20, 2014, 03:06:56 AM
Imagine an equilateral triangle inscribed in a circle. Randomly and independently generate two points on the circle, so all points on the circle are equally likely. What is the probability that the chord connecting the points is longer than a side of the triangle?
A) 1/2
B) 1/3
c) 1/4
This was an hour lecture about how "any of these can possibly be correct, it's a matter of perspective blah blah corpospeak syergisticising" ... I remember thinking how "no, only one of those can possibly follow the assumptions of independence and uniform distribution about the circle."
Re-thinking about it, I am almost certain that one of these answers is right. Which means this flawed logic is vastly preferred in the corporate world to my abilities.
Please vindicate my life
Post by: Clam on October 20, 2014, 06:56:48 AM
- The longer the arc length between two points, the longer the chord, i.e. they are equivalent in terms of ordering. [The formula is c = 2r sin(θ/2) which is increasing for θ between 0° and 180°.]
- The arc length between points on the triangle is 120°
- The arc length between the two random points is uniform between 0° and 180°
- The probability that this length is between 120° and 180° is (180-120)/180 = 1/3.
Post by: Simon on October 20, 2014, 09:29:31 AM
In 1/3 of the cases, when you rotate the triangle to match its corner to either point, the other point falls in between the two opposing corners. Then use Clam's argument for arc length ordering == chord length ordering.
I'm somewhat interested in irrational conviction systems. Can you elaborate on the corporate rigmarole?
-- Simon
Post by: chaos_defrost on October 20, 2014, 11:08:39 PM
I can't remember the other arguments. I think the 1/4 one had to do with the locus of possible chord midpoints to make the longer chord (which is I think a circle of half the radius, correct me if I'm wrong but you do get 1/4 if this is the case), which is flawed because the distribution of midpoints is not uniform.
I think the goal of this presentation was to show "there's different correct ways to look at a problem" -- by using flawed probability. Did I mention the interns this was for were studying to be ACTUARIES? You know, where the "easiest" test is entirely about probability? Company proceeded to lose 90% of its stock that year probably because of thinking like this. *shrug*
Post by: Proxima on October 20, 2014, 11:30:19 PM
By wording the question so as to eliminate this ambiguity, they undermined the whole point of asking the question in the first place
Post by: geoo on October 03, 2015, 03:57:30 PM
Imagine an arbitrary minesweeper board A, and its inverse B that has a mine in a cell iff it doesn't have a mine in the corresponding cell in A. Now imagine both boards are completely solved with the according numbers in the non-mine cells. Then the sum of all the numbers in A equals the sum of all the numbers in B.
Example:
Code: [Select]
111 ***
1*1 *8*
111 *** 8x1 = 1x8Code: [Select]
**100 24***
34321 *****
*2**1 3*44* 3x1 + 2x2 + 2x3 + 4 = 17 = 2 + 3 + 3x4
Prove this theorem. The proof is a nice and intuitive counting argument.
Here's another one, which is a lot harder (haven't solved it) and is apparently inspired by the dwarfs with hats problem that needs the axiom of choice:
There is a countably infinite number of boxes in a room, each containing a real number.
There are 100 prisoners who can discuss a strategy beforehand, but once the game has started they cannot share any information.
In some order (not sure if the prisoners know the order beforehand, let's assume yes) they are lead into the box room, one by one. In there they can open as many boxes as they want (countably many is allowed, but not all), and then they have to pick one unopened box and predict the number in that box.
After a prisoner leaves the box room, all boxes are closed again and then the next one enters.
If 99 of the prisoners predict correctly, they are released. Find a successful strategy.
<SimonN> and the prediction must be the exact real, no margin of error or anything
<geoo> yes
<SimonN> geoo: is it legal for two boxes to have the same real?
<geoo> not sure, let's assume no to ensure it's solvable
<SimonN> hmm, and countably many == countably infitiely many, or (finitely many or countably infinitely many)? Are the boxes labelled?
<geoo> the boxes are ordered and will not be rearranged at any point in the game
<geoo> countable can mean both finite and countably infinite
Post by: Proxima on October 03, 2015, 04:06:16 PM
Prove this theorem. The proof is a nice and intuitive counting argument.
Spoiler (click to show/hide)
Post by: Simon on December 26, 2015, 02:41:03 AM
A "block" is a largest-possible contiguous set of equally-colored cards in the deck. For example, if the red/black cards come up (red, red, black, black, black, red, black, red, red, ...), we have a block of 2 red cards, then a block of 3 black cards, then a block of 1 red card, and so on.
1. You could determine the number of blocks by looking at each card in sequence, comparing it against the previous card. Can you design an algorithm to determine number of blocks such that, at least with high likelyhood, the algorithm need not examine every card?
2. Now we're only interested in whether the number of blocks is even or odd. What's the most efficient algorithm?
Both were solved by Proxima in IRC, but I found it interesting enough to give everyone a try. :-)
-- Simon
Post by: NaOH on December 26, 2015, 07:08:00 PM
We have 30 chocolate-chip cookies in 5 cookie boxes. The cookies have different numbers of chocolate chips on them (not necessarily unique). This is the distribution:
A: 0, 10, 10, 10, 10, 10
B: 2, 2, 12, 12, 12, 12
C: 4, 4, 4, 14, 14, 14
D: 6, 6, 6, 6, 16, 16
E: 8, 8, 8, 8, 8, 18
This distribution has the curious property that if you pick a cookie from A and from B, odds are that the cookie from B has more chocolate chips. This is true for B and C, D and E, E and A as well. (https://en.wikipedia.org/wiki/Nontransitive_dice)
How many cookies can we eat and preserve this property?
Edit: I can eat 19 (so long as they're vegetarian). Can you eat more?
Post by: mobius on December 26, 2015, 10:25:38 PM
These questions are about a shuffled deck of finitely-many playing cards. Each card in the deck is either red or black. We don't necessarily assume that there are equally many reds as there are blacks. The physical order of cards inside the shuffled deck is linear.
A "block" is a largest-possible contiguous set of equally-colored cards in the deck. For example, if the red/black cards come up (red, red, black, black, black, red, black, red, red, ...), we have a block of 2 red cards, then a block of 3 black cards, then a block of 1 red card, and so on.
1. You could determine the number of blocks by looking at each card in sequence, comparing it against the previous card. Can you design an algorithm to determine number of blocks such that, at least with high likelyhood, the algorithm need not examine every card?
2. Now we're only interested in whether the number of blocks is even or odd. What's the most efficient algorithm?
Both were solved by Proxima in IRC, but I found it interesting enough to give everyone a try. :-)
-- Simon
did you mean to say "a 'block' is ANY set of equally colored contiguous cards in the deck, including each "single" [e.g. 1 red card in between two blacks]"
The "largest possible contiguous set" means in you're example you would only count 1 block; the 3 blacks in a row.
1. Isn't there a large lack of information? Otherwise it's a huge gamble. There are a huge number of possibilies ranging from all cards being 1 color, to an equal amount of each and each color evenly shuffled [red,black,red etc..] or 2 blocks; all colors to each side. Even if you look at 50% of the cards I don't see the liklihood being very high that you get it right.
I guess I need a clue. I read part of Proxima's answer to one of these but it didn't make any sense to me.
Post by: Simon on December 27, 2015, 05:03:44 PM
did you mean to say "a 'block' is ANY set of equally colored contiguous cards in the deck, including each "single" [e.g. 1 red card in between two blacks]"
A block needn't be the overall-largest equally-colored contiguous set. The set is a block if you can't enlarge it: There is no strict superset (equally-colored, contiguous) of the set. As a result, each card belongs to exactly one block.
A single red card sandwiched between two blacks is a block of length 1.
Quote
1. Isn't there a large lack of information? Otherwise it's a huge gamble.
Your algorithm can do different things, based on what cards it has already examined. We're trying to minimize the need to look at cards. We aren't minimizing computational complexity.
Quote
There are a huge number of possibilies ranging from all cards being 1 color, to an equal amount of each and each color evenly shuffled [red,black,red etc..] or 2 blocks; all colors to each side. Even if you look at 50% of the cards I don't see the liklihood being very high that you get it right.
Look at more than 50 % of the cards. Yes, there are distributions in which you would have to look at every card. The idea is that the ratio of such distributions becomes close to 0 for large number of cards.
-- Simon
Post by: bsmith on December 28, 2015, 06:19:09 PM
10 Start by looking at the first card, noting its color: card position = 1, block count = 1
20 Jump ahead to the second card after the current card and note its color: increment card position by 2
30 If these two cards are different, add 1 to the block count: increment block count by 1, goto 20
40 Go back one card (the one that was skipped) and note its color: decrement card postion by 1
50 If this card is different from the other two: increment block count by 2
60 Increment card position by 1 (already looked at it), goto 20
Post by: Simon on December 28, 2015, 07:52:44 PM
Love how you give the basic idea. :-)
-- Simon
Post by: geoo on December 28, 2015, 11:25:05 PM
I first found a solution eating 20 cookies. NaOH improved upon that by finding a solution with 21 cookies. I believe that this is optimal, below is the solution and my reasons/proof sketch for why I think it's optimal:
Spoiler (click to show/hide)
Post by: Simon on December 28, 2015, 11:38:11 PM
<SimonN> we could be a wise guy and eat all 30 cookies. Then, whenever we take 1 from box A and 1 from box B, they satisfy anything
<geoo> yes, very good
<geoo> and we get way more cookies
<SimonN> I don't know if the cultural value of this is higher than NaOH's solution
<SimonN> math doesn't segfault, that's very nice
<SimonN> there is the empty truth and that's it. At best, symbol isn't defined
-- Simon
Post by: Simon on January 15, 2019, 04:53:53 AM
4 boxes, 4 men
There are four boxes. One contains 3 black balls, the next contains 2 black, 1 white, the next contains 1 black, 2 white, and the final one contains 3 white balls. There are four labels describing the contents, BBB, BBW, BWW, WWW, with each box bearing one of these labels. None of the boxes are correctly labelled.
The boxes are randomly distributed among four men, A, B, C, and D. These men know the setup as described in the above paragraph, but they may only read the label of their own box, and it is not possible to examine balls without taking them out of the boxes.
Now, in alphabetical order, each man is ordered to read their box label (without announcing the label aloud), then take out and examine two balls from their own box, and make a truthful statement.
A says: "I drew two black balls, and I know the color of my third."
B says: "I drew a black and a white, and I too know the color of my third."
C says: "I drew two white balls, but I can't deduce the color of my third from only these two balls and my label." (= C doesn't take any statements by A or B into account.)
D is a blind man, unable to check ball colors or read labels. Thinking hard for a while, he says: "I know the colors of all three balls in my box, and I can tell the color of A's, B's, and C's third balls."
How does he know?
-- Simon
Post by: Ramon on January 15, 2019, 10:37:06 AM
Spoiler (click to show/hide)
Post by: Simon on January 15, 2019, 05:16:32 PM
Forestidia and I solved it together today, and we stumbled on the same ambiguity in the original puzzle. There are two possible solutions. To fix the ambiguity and force one of the solutions, I've changed in the puzzle:
C: "I drew two white balls." to
Thus, Ramon's answer remains correct, it is now the only correct one.
-- Simon
Post by: Simon on January 21, 2019, 11:32:15 PM
Reason for the change: The puzzle must be solvable from the blind man D's hearing of A's, B's, and C's statements. But if D can deduce everything here, then C must have been able to deduce everything already because C can't learn anything new after making his own statement. It would be inconsistent to let C have all knowledge that D has, yet let only D be able to deduce C's third ball.
Ramon's answer remains the only correct answer.
-- Simon
Post by: Simon on June 08, 2021, 06:58:53 AM
Train circle
There is a natural number n > 0 of train cars. The cars form a single big circle: Each car is attached to exactly two other cars, one at the front and one at the back. In each car, the light is either on or off, initially at random.
You're in one of the cars. You can walk back and forth in the circle. In each car that you visit, you can switch the light on or off as you like. Find an algorithm that determines the number n of cars in the circle, in finite time.
-- Simon
Post by: Dominator_101 on June 08, 2021, 02:23:51 PM
Spoiler (click to show/hide)
Okay, here's some real thoughts on the puzzle (not a solution really, but I'll spoiler just in case. It's mostly just kind of brainstorming an issue):
Spoiler (click to show/hide)
Post by: geoo on June 08, 2021, 03:06:09 PM
Spoiler (click to show/hide)
Post by: Simon on June 08, 2021, 03:41:59 PM
geoo posted 2 algorithms in his spoiler tag, his first matches what I found during lunch break. geoo's second one improves the run time over what I found, I didn't think of that. Nice!
Spoiler (click to show/hide)
-- Simon
Post by: Dominator_101 on June 08, 2021, 04:10:40 PM
Spoiler (click to show/hide)
For the current puzzle, going off Simon's post:
Spoiler (click to show/hide)
Post by: Dominator_101 on June 14, 2021, 06:04:23 PM
Spoiler (click to show/hide)
Post by: Simon on June 18, 2021, 05:18:37 AM
Re: Train circle (click to show/hide)
-- Simon
Post by: Armani on June 18, 2021, 01:57:15 PM
https://artofproblemsolving.com/community/c6t304885f6h62190_the_lamp_invariant_game
Post by: Simon on April 02, 2022, 11:12:25 AM
More cute graph theory.
Let G be an undirected graph with n ≥ 2 nodes, with only simple edges, i.e., no multiple edges. Prove the following statement or construct a counterexample: There exist two nodes in G that have exactly the same number of
Example: In the picture, both A and B have two edges each.
Example: if G contains only n = 2 nodes, they're either connected (and both have 1 edge) or not (and both have 0 edges); in either case, G contains two nodes with the same number of edges. Thus, the statement is true at least for two-node graphs.
-- Simon
Post by: Armani on April 02, 2022, 11:46:38 AM
Then the number of edges of every nods = {0,1,2, ... , n-1}
but this is impossible
contradiction!
Post by: Simon on April 02, 2022, 02:12:08 PM
Your proof was the first that I found, too. Here is a second proof that I found today:
Spoiler (click to show/hide)
-- Simon
Post by: Armani on April 02, 2022, 02:22:52 PM
Quote
Yep! For completeness, elaborate why exactly it's impossible to have excatly the edge counts 0, 1, ..., n − 1.
0 means there's a nod which is connected to no other nods
n-1 means there's a nod which is connected to all other nods
They can't both be true simultaneously 8-)
Post by: geoo on April 04, 2022, 10:20:13 AM
You're building a N-player level where each player has M hatches.
The hatches are arranged into a grid of M rows and N columns. But the player order is wrong!
You need that in each column, all hatches belong to the same player, and in each row, the hatches spawn lixes at the same time.
You don't want to move the hatches around (error-prone), but you can fix this by changing the priority of a few of them.
How many hatches do you have to click to be guaranteed to be able to sort this out, regardless of the initial arrangement?
About priorities: If my hatches are ordered 1, 2, 3, 4, 5, and I decrease the priority of #4 down to 2, the priority of #2 and #3 gets increased by 1 each, giving 1, 3, 4, 2, 5.
If the players are A, B, C and the hatches per player are A1, A2, A3, then the hatches are ordered
A1, B1, C1, A2, B2, C2, A3, B3, C3
1 2 3 4 5 6 7 8 9
Example: N=2, M=2.
A2 B1 3 2
B2 A1 or 4 1
If I increase the priority of A1 to A2, I get
B1 A1 2 1
B2 A2 or 4 3
So clicking one hatch is sufficient. Is one hatch sufficient for every starting configuration for N=2, M=2?
Remark: This is from a real example where I was trying to build a level, and clicking hatches was expensive as they were buried under eraser terrain, which had to be removed first to access the hatch.
Post by: Dominator_101 on April 05, 2022, 05:20:56 PM
For Geoo's issue, I'm not sure if I 100% understand the priority orders you laid out. I think I figured out your initial example and was just conceptualizing it differently. I'm still unclear on the second example. You first say that the hatches would go A1, B1, A2, C2 as 1,2,3,4 respectively, but in the side by side examples it looks like A1 is 1 and B2 is 2? I also don't really follow how the rearrangement happens there. Not sure if I'm just missing something.
Here's some thoughts, based on my assumption of how the ordering works:
Spoiler (click to show/hide)
Post by: Simon on June 14, 2022, 08:19:30 AM
What is the minimum number of knights to put on an 8x8 chessboard such that the knights attack every vacant square?
Example with 16 knights (click to show/hide)
Can you do better than this? I don't even have intuition whether optimal solutions will be symmetrical or asymmetrical.
Downsides with this kind of puzzle: It's not pure logic, it's optimization, thus borderline off-topic for the thread of pure logic puzzles. And I don't know the solution; I believe that optimiality is hard to prove. Although -- we did a good job on the lights in the wagons: We proved that O(n) is optimal, even though that wasn't part of the initial puzzle.
Thus, feel free to just skip the knights and post another puzzle. :8():
-- Simon
Post by: Armani on June 14, 2022, 09:15:56 AM
Every coloured square can only be covered by unique different knights which means you can't cover the whole board with less than 12knights.
And it's possible to cover the whole chessboard with 12knights. Here's an example:
(https://i.imgur.com/d2WTLav.jpg)
So the answer is 12.
Post by: Simon on June 14, 2022, 07:26:21 PM
-- Simon
Post by: DireKrow on June 18, 2022, 07:49:15 PM
Rules
- Draw a single non-intersecting loop through the centers of all cells. The loop may only move horizontally or vertically and may only make 90-degree turns.
- Clues outside the grid represent the lengths of the blocks of consecutive turns that the loop makes in the corresponding row or column, in order.
E.g. "2" means the loop turns in two consecutive cells in that column, while "1 1" means the loop turns in one cell and then another non-consecutively.
Example (click to show/hide)
Puzzles
Nonoloop 1 (click to show/hide)
Nonoloop 2 (click to show/hide)
Nonoloop 3 (click to show/hide)
Nonoloop 4 (click to show/hide)
And attached is a single pdf with the rules and all puzzles, if that's preferred
Post by: Simon on June 20, 2022, 10:47:26 PM
I knew Nonogram, but didn't know Simple Loop. I discovered several emergent patterns that the Nonoloop solutions must satisfy, and in hindsight, they should apply to Simple Loop, too. Nonetheless -- congrats on designing something with such emergence from only a few given rules! Formalizing the patterns in my mind helped with the later puzzles.
Rule clarifications that I took for granted: When a row contains clues, not only these clues denote the lengths of the blocks of consecutive turns, in order, but also:
- Any two blocks of the row are separated by one or more straight-loop squares.
- The clues cover all the blocks of the row, i.e., there are no more turns in that row other than those denoted by the clues.
Post by: mobius on May 03, 2023, 11:03:10 PM
https://www.lemmingsforums.net/index.php?topic=1389.msg39003#msg39003
It gave the correct answer; its description of the process was pretty thorough as well; more detailed than mine and used two tables. Of course this was a while ago and I can't remember exactly how I solved it myself except what I wrote there, but my description was much shorter than chat GTP's.
Next I gave it this puzzle;
https://www.lemmingsforums.net/index.php?topic=1389.msg96371#msg96371
This was the answer:
Quote
The minimum number of knights required to put on an 8x8 chessboard such that they attack every vacant square is 32. Here's one possible arrangement that achieves this:
mathematica
N . N . N . N
. N . N . N .
N . N . N . N
. N . N . N .
N . N . N . N
. N . N . N .
N . N . N . N
. N . N . N .
In this arrangement, the knights are placed on every other square of the board, such that they attack all the remaining squares. It's important to note that the knights only attack squares that are not occupied by other knights, so we can't simply place 64 knights on the board to cover every square.
Also, this is the minimum number of knights required to cover all the vacant squares on the board, but it doesn't necessarily mean that it's the only solution. There may be other valid arrangements that achieve the same result.
I then asked if it could do it with "all knights themselves are attacked by other knights" and the answer was; no none can be placed and then I realized why it got it wrong but I don't know how to word this correctly.
I was confused at first as well until I realized the question is... well as I said I don't know how to phrase the question correctly, but it is missing a bit of information imo, in the statement of the problem. Chat GPT is solving it as if each square can only be taken in one 'instance'.
also an oddity: why it "forgot" the last column on the chessboard? I'll ask it that later.
I've been getting into Nikoli-style logic puzzles recently, solving a few when I have the time, but I also went ahead and created some of my own puzzles. They're nothing too fancy, but I'm pretty happy with them for a first attempt. They use a ruleset which combines Simple Loops (https://www.fancade.com/wiki/Games/Simple%20Loop.md/c0ac7fb487e9f030f34f126602828d655379fa56) with Nonograms (https://en.wikipedia.org/wiki/Nonogram). I dub it, the Nonoloop.Next I might try the loop puzzles and nonograms and other puzzles but idk if drawing and images is possible with this version I'm using.
Btw; those puzzles are fun but tough! I started trying one myself at work today :D
Post by: mobius on May 04, 2023, 10:57:34 PM
It then answered with "If we allow the theoretical attacks of the knights to overlap, then the minimum number of knights needed to cover every square on an 8x8 chessboard reduces to 14."
but the diagram it gave was identical to the first; trying again different yielded the same diagram. So it got closer to the minimal answer (pretty close) but seem to fail at drawing this for some reason. As such I can't be certain if it's really still understanding the problem correctly.
In any case I just realized I'm using Chat GPT 3 not 4, which is supposedly shockingly better than 3. 4 must be paid for it looks like. 3 is still pretty impressive for what it can do and how it does it.
Post by: chaos_defrost on May 07, 2023, 08:20:40 PM
https://ig.logicpuzzle.app
It's.... as the name suggests, there's 100 puzzles, I think I got about 30 or so on my own but I believe the dev intended to have them solved as teams.