Logic Puzzles

Started by alfonz1986, July 16, 2011, 03:34:55 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

alfonz1986

Ok, so theres two lemmings sitting in a boat in a lake. One of the lemmings manages to resist the urge of jumping out of the boat, but the other lemming isn't so lucky and walks over the edge into the water and drowns  http://www.lemmingsforums.com/Smileys/lemmings/sick.gif" alt=":sick:" title="Sick" class="smiley" /> 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  http://www.lemmingsforums.com/Smileys/lemmings/cool.gif" alt="8)" title="Cool" class="smiley" />



Simon

Hmm, I might answer it as nobody else wants to, despite knowing it beforehand; it's a popular physics puzzle.

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

alfonz1986

I'm not sure what u mean by the 'corner case'

chaos_defrost

http://www.lemmingsforums.com/index.php?topic=533.msg11005#msg11005">Quote from: alfonz1986 on 2011-07-17 08:38:45
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.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

alfonz1986

Thats not the case, if the lemmings density was equal to the waters, the lemming would be 'neutrally buoyant' and would neither sink or float. Remember gravity is acting on the lemmings and the water.

finlay

But he's just either walked or jumped into the lake, and that force isn't gonna go nowhere, so he'll continue falling through the same-density water until he receives a different force from somewhere.

ccexplore

Finlay and Simon is right I think.  Neutrally buoyant just means the force of gravity cancels the force of buoyancy, but to stop the falling you still need a net upward force to slow down the downward velocity you've already gained from gravity alone before you hit the water.  As Simon said, this is inertia from falling.

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 http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />, 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.]

alfonz1986

@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). If he is denser than the water (like in the problem) then he continues sinking due to his downward weight being greater than the upward buoyancy force. His entry velocity from falling in off the boat has nothing to do with it unless the lake was very shallow.

ccexplore

http://www.lemmingsforums.com/index.php?topic=533.msg11010#msg11010">Quote from: alfonz1986 on 2011-07-17 18:40:20
@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.]

alfonz1986

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. 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. So the question remains ccexplore:

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 http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" /> 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.

ccexplore

http://www.lemmingsforums.com/index.php?topic=533.msg11012#msg11012">Quote from: alfonz1986 on 2011-07-17 18:54:33
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.

http://www.lemmingsforums.com/index.php?topic=533.msg11012#msg11012">Quote from: alfonz1986 on 2011-07-17 18:54:33
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 http://en.wikipedia.org/wiki/MythBusters_(2005_season)#Episode_34_.E2.80.93_.22Bulletproof_Water.22" class="bbc_link" target="_blank">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? http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

=========

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.

Simon

http://blogs.1077theend.com/files/2010/07/Beavis_and_Butthead_horror.png" alt="" class="bbc_img" />

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

alfonz1986

The answer is a Flea. He has an odd number of fleas and no way of getting rid of the final flea since the only way he can discard fleas is two at a time.

[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

Simon

Yep, it's perfect. The important observations are that each iteration lowers the critters remaining by 1, and that the fleas may only go in pairs.

Post another one or declare open floor. :-)

-- Simon

alfonz1986

hehe, but u already knew the answer to my puzzle. did u manage to get it urself first go?

if u know the answer to this next one already - let the others ponder it a bit longer http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

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?

finlay

I'm going to hazard a guess at yes, but only because my instinct says no and that's how these questions normally work. http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />

Simon

No/Unsure. The airplane lifting force comes from interaction of wings and their surrounding air, and the wheels/conveyor belt are not part of this separate system. Conversely, the plane would lift with still wheels if there was a large fan blowing air towards it.

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

Johannes

Someone's a Mythbusters fan http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />

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?

alfonz1986

hehe, Ive seen mythbusters, but this puzzle far outdates that show. I guess if you saw that episode you know the answer, so dont tell the others yet http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

ccexplore

Hey alfonz1986, based on people's question and response, I think part of your phrasing of the question caused some confusion.  Having seen the Mythbuster episode (well I've seen all of them from the beginning, and yeah, most of what they feature have to start off as a relatively well-known myth first, so the myth pretty much always outdates the corresponding TV episode), let me rephrase your puzzle to precisely describe the situation demonstrated on that episode (unless you purposely intended for your puzzle to differ from the myth as presented on TV):

[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?

Johannes

http://www.lemmingsforums.com/index.php?topic=533.msg11027#msg11027">Quote from: ccexplore on 2011-07-18 19:30:51
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?

ccexplore

http://www.lemmingsforums.com/index.php?topic=533.msg11030#msg11030">Quote from: Johannes on 2011-07-19 02:28:48
http://www.lemmingsforums.com/index.php?topic=533.msg11027#msg11027">Quote from: ccexplore on 2011-07-18 19:30:51
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. http://www.lemmingsforums.com/Smileys/lemmings/undecided.gif" alt=":-\" title="Undecided" class="smiley" />

Clam

(Not sure how "logic puzzles" came to mean physics problems, but anyway... http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />)

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 http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />)

ccexplore

http://www.lemmingsforums.com/index.php?topic=533.msg11032#msg11032">Quote from: Clam Spammer on 2011-07-19 03:41:57
(Not sure how "logic puzzles" came to mean physics problems, but anyway... http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />)

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. http://www.lemmingsforums.com/Smileys/lemmings/undecided.gif" alt=":-\" title="Undecided" class="smiley" />

Simon

http://www.lemmingsforums.com/index.php?topic=533.msg11033#msg11033">Quote from: ccexplore on 2011-07-19 03:50:41
http://www.lemmingsforums.com/index.php?topic=533.msg11032#msg11032">Quote from: Clam Spammer on 2011-07-19 03:41:57
(Not sure how "logic puzzles" came to mean physics problems, but anyway... http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />)
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

alfonz1986

@CCE The newly editted way you describe the problem is basically identical to the way I described it. I guess these are physics related problems but I don't believe you need to have studied much physics to solve it if you have strong logic.

@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  http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

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?

ccexplore

http://www.lemmingsforums.com/index.php?topic=533.msg11036#msg11036">Quote from: alfonz1986 on 2011-07-19 05:01:39
@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 http://www.lemmingsforums.com/Smileys/lemmings/undecided.gif" alt=":-\" title="Undecided" class="smiley" />) maybe it is a bad formulation, so then in my 2nd rephrasing, I decided to use 2 airplanes as a way around his objections.

http://www.lemmingsforums.com/index.php?topic=533.msg11036#msg11036">Quote from: alfonz1986 on 2011-07-19 05:01:39
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?)

Johannes

http://www.lemmingsforums.com/index.php?topic=533.msg11031#msg11031">Quote from: ccexplore on 2011-07-19 03:32:52
I've edited my scenario description hopefully to better capture the setup...maybe.  I need to think more about it. http://www.lemmingsforums.com/Smileys/lemmings/undecided.gif" alt=":-\" title="Undecided" class="smiley" />
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".  http://www.lemmingsforums.com/Smileys/lemmings/thumbsup.gif" alt=":thumbsup:" title="Thumbs Up" class="smiley" />

Clam

http://www.lemmingsforums.com/index.php?topic=533.msg11036#msg11036">Quote from: alfonz1986 on 2011-07-19 05:01:39
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 http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

Johannes

http://www.lemmingsforums.com/index.php?topic=533.msg11039#msg11039">Quote from: Clam Spammer on 2011-07-19 05:52:16
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?

alfonz1986

@ClamSpam  No, you're sort of on the right lines but doubling the normal takeoff velocity is not whats required here. Also in the swimming pool case, ignore the buoyancy effect, or water density. I could pose it as: imagine yourself standing on a flat treadmill which was spinning at a velocity of 100mph backwards relative to the ground. If you had a handrail next to you, and pulled yourself forward at 10mph. Would the treadmill be able to stop you from doing that? (assume the friction in the wheels is negligible)

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 http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

Johannes

Since we're getting close to solving the airplane puzzle, here's another involving Lemmings (credit goes to the amazing wu::riddles site).

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 http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

ccexplore

Cool, this is one puzzle I don't remember ever hearing a similar puzzle before, so it's really a new one for me.

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 http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />]
[edit2: minor clarifications]

Johannes

Spot-on. Must have been too easy http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

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.

ccexplore

Part of it is I think because it's easy guess at the right answer when you consider small number of lemmings (or equivalently, starting arrangements where most lemmings drown almost immediately, leaving only a few that actually stays around for a while).  And
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.

alfonz1986

Invis My gut instinct is 100m, so 100 minutes. I ran through a few possible scenarios in my head like 2 lemmings facing toward each other at x=0m and x=100m. They would meet at 50m and deflect, so time would be 100 minutes. 

EDIT: I didn't read your hints before coming to this conclusion http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" /> I will just read it now.

ccexplore

http://www.lemmingsforums.com/index.php?topic=533.msg11041#msg11041">Quote from: alfonz1986 on 2011-07-19 06:17:02
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 http://en.wikipedia.org/wiki/Monty_Hall_problem" class="bbc_link" target="_blank">Monty Hall problem.

alfonz1986

Funny you mention the monty hall problem, I was just going to post that as the next puzzle - moving from physics to maths!  http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />

Clam

Oh ok, I think I get the airplane puzzle now.

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.

alfonz1986

Good job  http://www.lemmingsforums.com/Smileys/lemmings/thumbsup.gif" alt=":thumbsup:" title="Thumbs Up" class="smiley" />

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.

Simon

Alright. Does each puzzle appear to be solved and acknowledged? (plane, and 100 meter stick)

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.
Thus, the sequence starts as follows: 0 1 0 0 1 1 0 1 0 0 1 0 0 1 ... The bold digits come from the third rule, there's nothing special to them. It's just to visualize the rule.

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). http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

-- Simon

finlay

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.

Simon

Yes, this is it! You've made all the necessary observations and linked them together properly.

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

finlay

It has been a while, yeah. I had a false start on a maths degree, which I didn't enjoy, so I mostly stay clear of it these days – but I still have a few of the basic techniques there. (I changed to a linguistics degree in 2007, and finished last year)

ccexplore

Yeah, I suspect those without a math background (or theoretical computer science, which is really just a branch of discrete math) will be at a slight disadvantage.  The structure of the sequence doesn't directly correspond to everyday experiences, even though it is quite elementary in terms of induction/recursion.

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).

geoo

Here's a few more puzzles. #1 is similar in spirit to Johannes' puzzle, #2-#4 are tricky but can still be solved pretty elementarily, and for #5 the general idea is interesting, whereas fully solving it is pretty tedious and should be avoided. http://www.lemmingsforums.com/Smileys/lemmings/wink.gif" alt=";)" title="Wink" class="smiley" />
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?

ccexplore

Am I the only one who finds #1 to be a complete joke?  I almost wonder if I'm misreading the puzzle statement somehow.

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.

geoo

Yep, #1 is totally trivial, yet most people seem to take a minute or two to realize it. I found it similar to Johannes' puzzle in that regard, though perhaps it's still a bit more obvious in the chocolate bar case.
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.

alfonz1986

Is #3  4*Pi*R^2 ? ie the surface area of one sphere.


Is #3.5  4^n, ie 1, 4, 16, 64, 256, 1024...

geoo

#3 is correct.

#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?

alfonz1986

Damn, I only solved it as far as 8 before I noticed the pattern. Turns out 9 is ON as well! So the formula is a little more complex than I first thought.

EDIT: Aha! Is it all squared integers? 1,4,9,16,25,36,49,64 , n^2 ?

geoo

Yep, that is correct. Now prove it. http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

btw, that wu::riddles site Johannes pointed to is really awesome!

Clam

Answer to #2:

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.

alfonz1986

#3 is actually very very easy since you didn't specify a number of planets, you only said planets, ie more than one. Therefore the rule must be identical assuming 2 or more planets up to any finite number. Solving the situation for just two planets its very easy to see that the non-exposed surface is equal to the surface area of one planet.

geoo

I could have put the number N for the amount of planets in the problem statement again.
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.

ccexplore

Hmm, I could get #4 with a lot of math (hopefully I did my math correctly too), but there's gotta be a much more elementary way to approach it if it's worthy to be a puzzle and not a mere exercise in math:

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.

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: correct a mistake in wording near the end]

[edit: move edit to correct post!]

ccexplore

Hmm okay, I think there's a slightly more insightful approach for #4.  But I still can't eliminate the 2 maximization problems that seem to need calculus to solve.

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:

   ____
  /|  |\
 / |  | \
/  |  |  \
----------


ccexplore

Okay, I finally have a simple, non-calculus, fully geometric way to approach the one base problem in #4 (maximize area of 1 rectangle in 1 triangle), which I can only show with a diagram (too hard to draw in ASCII art for me).  I'll attach it once the diagram is drawn.

[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.

geoo

Really interesting to see your process of breaking down your solution into increasingly elementary sub-problems, and finally solving the remaining base problem geometrically in a pretty nifty way. http://www.lemmingsforums.com/Smileys/lemmings/thumbsup.gif" alt=":thumbsup:" title="Thumbs Up" class="smiley" />
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.)

ccexplore

I've made good progress on the sphere problem, but there's a technical issue that I'm finding a little tricky to get around:

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.

ccexplore

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.

EricLang

This riddle is in one of the old Columbo series. I'll watch it tonight to get the exact details of the problem.

geoo

I think I heard about this puzzle or a variation thereof, but I can't remember anything about the solution, if I was even ever told about it.

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 http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />). There are 24 possible solutions (12 indices for the ball, and either 'too heavy' or 'too light'), and as it takes 3 trits to be able to represent all numbers from 0 to 23, we require at least 3 weighings to solve the problem.

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.

ccexplore

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! http://www.lemmingsforums.com/Smileys/lemmings/thumbsup.gif" alt=":thumbsup:" title="Thumbs Up" class="smiley" /> 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. http://www.lemmingsforums.com/Smileys/lemmings/XD.gif" alt=":XD:" title="XD" class="smiley" /> http://www.lemmingsforums.com/Smileys/lemmings/wink.gif" alt=";)" title="Wink" class="smiley" />

Clam

Most of the above puzzles are solved it seems, so I guess it's about time I posted some puzzles too. Since geoo suggests posting puzzles even if people may have heard of them, I decided I should hit you with something a little different. These are less maths/physics puzzles like most of the ones so far, and more groan-worthy thinking puzzles.


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?

ccexplore

http://www.lemmingsforums.com/index.php?topic=533.msg11104#msg11104">Quote from: Clam Spammer on 2011-07-25 19:52:07
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. http://www.lemmingsforums.com/Smileys/lemmings/undecided.gif" alt=":-\" title="Undecided" class="smiley" />

[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.

Clam

http://www.lemmingsforums.com/index.php?topic=533.msg11106#msg11106">Quote from: ccexplore on 2011-07-25 20:20:33
Since I didn't laugh nor groan, somehow I think the actual intended answer is something else. http://www.lemmingsforums.com/Smileys/lemmings/undecided.gif" alt=":-\" title="Undecided" class="smiley" />

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 http://www.lemmingsforums.com/Smileys/lemmings/laugh.gif" alt=":D" title="Laugh" class="smiley" /> (and yes, your second answer is the "right" one)

alfonz1986

#2 (invis) the letter e

#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


ccexplore

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.

ccexplore

http://www.lemmingsforums.com/index.php?topic=533.msg11104#msg11104">Quote from: Clam Spammer on 2011-07-25 19:52:07
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. http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

======================

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......

Simon

I will be silent in regard to the current puzzles, since I already know each of Clam's riddles. I also did a few of geoo's puzzles in IRC already. So there aren't any unsolved problems that seem interesting to me. <_<; Here's another one for the rodent fraction (= the critters from IRC, and cce because he's the busy beaver, but really anyone). Care should be taken not to eat the wooden blocks, even if they look tasty.



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

ccexplore

http://www.lemmingsforums.com/index.php?topic=533.msg11110#msg11110">Quote from: ccexplore on 2011-07-26 06:04:40
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

ccexplore

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. http://www.lemmingsforums.com/Smileys/lemmings/undecided.gif" alt=":-\" title="Undecided" class="smiley" /> 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.

Clam

http://www.lemmingsforums.com/index.php?topic=533.msg11111#msg11111">Quote from: ccexplore on 2011-07-26 06:26:28
(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 http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

ccexplore

http://www.lemmingsforums.com/index.php?topic=533.msg11118#msg11118">Quote from: Clam Spammer on 2011-07-27 04:54:55
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 http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />) possibility that the waiter extracted a sample of your DNA from the original coffee, filter any traces of the original coffee out, and add the sample back to the second coffee.  Again, highly implausible I agree, but not barred by the laws of physics.  As you pointed out, the vagueness of the puzzle opens up a lot of possibilities as to what happened.

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. http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

ccexplore

http://www.lemmingsforums.com/index.php?topic=533.msg11118#msg11118">Quote from: Clam Spammer on 2011-07-27 04:54:55
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 http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />).

And in theory, to a person coming from a culture unfamiliar with sheep (Inuit say?), #6 isn't necessarily general knowledge, but I digress.  http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

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.

ccexplore

Also, the reason I picked the 12-balls and scale puzzle is because I thought it's a nice logic puzzle that doesn't require specific knowledge or mathematical experiences.  A solid math background may lead you to the answer faster and more systematically (as geoo attested to), but at least it's quite possible to explain a working scheme to a layman and convince him/her that it works.

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. http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

alfonz1986

Wait! I got it! You're not actually in a coffee shop at all. You just have terrible dementia and you're 80 years old and in a nursing home.  http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />
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?
 

Simon

I know alfonz' puzzle already, so I'll pass and let someone else take a guess.

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

alfonz1986

I also solved the bear one, on my way walking to uni http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

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  http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

Simon

North pole is correct, yep. The reasoning has subtle humps though (file this away as smart-arse blah blah):
  • 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.
-- Simon

alfonz1986

Yeah I basically meant the principle is sound. Whether you start walking north or south makes no difference to the principle. Vice-a-versa

ccexplore

Good one for Simon's latest.  I think it's right there in terms of logic puzzles that are as unfettered by "outside knowledge" (math, physics, language, general knowledge, whatever) as you can get.

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]

Simon

Right on! A great systematic approach that rules out the existence of other solutions.

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

alfonz1986

#84
Spoiler........Damn these invisible quote boxes to hell!

Solution for mollusc puzzle

1. worm snail
2. clam
3. worm snail
4. worm snail
5. tusk shell

I initially noticed that #1 had to be the worm snail. If it wasn't, theres no way pupils A, B and F could have two answers correct, since there are 4 questions left and there are no matches between anyones answers. The next obvious choice was clam for #2 since there were 3 answers for that one. Playing about with a few more options like tusk shell #5 gave the final solution shown above.

Took a little while before I realised two or more could be the same mollusc.

Simon

Yep, also a correct solution and argumentation!

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

ccexplore

Here's to wrap up geoo's #4 (the sphere/planet problem) once and for all.  I decided to forget the diagrams since at this point interest in the problem is probably low anyway.  Instead I'll just present a proof sketch (so some details omitted for reader's exercise--and yet it's still kinda a long read http://www.lemmingsforums.com/Smileys/lemmings/undecided.gif" alt=":-\" title="Undecided" class="smiley" />), 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. http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />) [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.

geoo

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 .....
What is it you are buying?
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...
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 http://en.wikipedia.org/wiki/Mobile_(sculpture)" class="bbc_link" target="_blank">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.
The typical way to solve such an exercise is to show a series of implications. For instance,
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.

ccexplore

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? http://www.lemmingsforums.com/Smileys/lemmings/laugh.gif" alt=":D" title="Laugh" class="smiley" /> http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

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).

ccexplore

#C1: You got a http://en.wikipedia.org/wiki/Mobile_(sculpture)" class="bbc_link" target="_blank">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. http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

geoo

http://www.lemmingsforums.com/index.php?topic=533.msg11205#msg11205">Quote from: ccexplore on 2011-08-01 13:29:17
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. http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />
That bears the (easier) question: how many of these do you have to change? http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />

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" class="bbc_link" target="_blank">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.

Simon

No progress on the open puzzles? Here's three more that geoo already knows.

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

chaos_defrost

#0: Easy game: Have each player declare the hat color opposite of what they see iff they see two hats of the same color.

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
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

chaos_defrost

A logic puzzle I got as part of a timed IQ test on another forum. I think I got it but I'm not 100% sure.

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?
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

ccexplore

About 30 minutes after seeing this on the forum, I worked out the answer, but by making a leap in logic I haven't yet been able to close.

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.).

chaos_defrost

Ok, that's what I got too, good.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

ccexplore

Okay, finally nail down the one and only answer by a slightly different approach, can't believe it took that long. http://www.lemmingsforums.com/Smileys/lemmings/XD.gif" alt=":XD:" title="XD" class="smiley" />

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.

chaos_defrost

When I got that problem I only had 10 minutes to solve it and three admittedly slightly easier questions: My solution wasn't exactly what you'd call rigorous, but

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.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

ccexplore

Actually I'd say the logic is perfectly tight and complete as a solution. http://www.lemmingsforums.com/Smileys/lemmings/thumbsup.gif" alt=":thumbsup:" title="Thumbs Up" class="smiley" /> 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.

Proxima

Solution to Simon's hat puzzle #1:

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

Simon

Steve and Proxima are correct with hat puzzles #0 and #1.

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

Simon

This is a nice one from an older book of mine.

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

mobius

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.  http://www.lemmingsforums.com/Smileys/lemmings/XD.gif" alt=":XD:" title="XD" class="smiley" />
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain


Simon

Correct answer, and a good explanation!

-- Simon

Proxima

Oh no, geoo's Tame 13 video has been stolen! The suspects are a Classic lemming, a Highland lemming and a Shadow lemming, and one and only one of them is guilty. And as we all know, Classic lemmings always tell the truth, Shadow lemmings always lie, and you can't trust a Highland lemming, they can do either (but, if asked a yes/no question, they will always respond one way or the other).

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?

ccexplore

I don't know yet if it's smallest number of questions, but it will find the guilty party.

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.

chaos_defrost

I can definitely do it in one fewer but I don't quite think it's optimal yet:

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?
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Proxima

Full marks  http://www.lemmingsforums.com/Smileys/lemmings/thumbsup.gif" alt=":thumbsup:" title="Thumbs Up" class="smiley" />

Simon

I don't want to read the spoiler yet. Questions about it:
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

mobius

this one came out of a I.Q. Test book. I don't remember how much time you got for it though.

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...)
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain


Proxima

I'm not sure I understand what's being asked. The problem with the machine is that it has a cycle (BCDEGIH) of odd length. Adjacent cogs turn opposite directions, so any cycle must be of even length. Seems to me like all you need do is move I elsewhere so G and H can touch.

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.

GuyPerfect

It's possible to identify the guilty Lemming in 2 questions. It's not guaranteed, but the question in Proxima's post asks how few it can be done in, and the answer is 2:

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.

ccexplore

Um, if I understand correctly the Highland lemming can answer however way he wants, so how does your exchange above rule him out?

Proxima

Yes, my question was ambiguous. In problems like this, it's generally assumed (unless stated otherwise) that you're allowed to give a strategy in which subsequent questions vary depending on earlier answers; so the number of questions asked may vary. That makes it unclear whether you're trying to minimise the maximum, the minimum or the expected value (assuming the 18 possibilities for arrangement and guilt are equally probable).

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).

GuyPerfect

(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.

chaos_defrost

Somewhat easier yes/no puzzle I found somewhere:

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.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

chaos_defrost

Also double post for something else I found:

http://puzzle.cisra.com.au/" class="bbc_link" target="_blank">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.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Simon

Solution to Steve's yes-no puzzle:
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

chaos_defrost

That works, yes.  http://www.lemmingsforums.com/Smileys/lemmings/laugh.gif" alt=":D" title="Laugh" class="smiley" /> 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.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Simon

I've known "12 balls, weigh 3 times" since high school, but never went into it in detail since it seemed tedious, but also never read a solution since it's a beautiful puzzle. I've finally done it on my own today. No new information here, except that I'm doing a different second weighing in case I) a) than geoo.

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

chaos_defrost

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.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

chaos_defrost

And a follow-up to my "guess my number" riddle. I thought of it a while back but I am not actually sure of the answer.

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
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Proxima

I was all set to give my solution to Simon's puzzle, then I noticed there was a new page of the topic http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" /> 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.

chaos_defrost

Ha, for some reason I didn't think of it like this, but that certainly looks good, and it shouldn't be hard to show that's as good as you can do, also. Nice job  http://www.lemmingsforums.com/Smileys/lemmings/thumbsup.gif" alt=":thumbsup:" title="Thumbs Up" class="smiley" />
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

chaos_defrost

http://www.lemmingsforums.com/index.php?topic=533.msg14703#msg14703">Quote from: Insane Steve on 2012-09-03 14:22:44
Also double post for something else I found:

http://puzzle.cisra.com.au/" class="bbc_link" target="_blank">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.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Proxima

I'll join in, if you like. I've had a look through some of the previous puzzles, and they look interesting, but very difficult!

Simon

I shall offer myself as the 4th person. I cannot tell how much time I'll have available, and I'm probably also not the brightest at solving without instructions or making words from random things. If someone would like to join, he can certainly do so instead of me.

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

chaos_defrost

This contest is entirely for fun, so if you don't have a ton of time it's all good.

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.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

chaos_defrost

New puzzle that I found on a website with an IQ test designed for people on the very extreme end of the IQ spectrum. It's called the "Hoeflin Power Test" if you want to try it. I've been messing around with the problems on it, probably not going to have it scored because it costs $50 lol but there's some very interesting challenges.

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?
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

ccexplore

Hmm, now I think I see why you made a mistake and have not found a neat way to do it.  At first I too thought this is just a 3D version of what Gauss allegedly did as a child with 1+2+...+n, but the shift to 3D does add some complications from the 2D version, and I haven't gotten the details straighten out myself. http://www.lemmingsforums.com/Smileys/lemmings/XD.gif" alt=":XD:" title="XD" class="smiley" />

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

Simon

Hmm, I had
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

chaos_defrost

Just as well, I'm not offhand sure I get the notation you're using. Which I'm fine with, since I want to try and get it without help  http://www.lemmingsforums.com/Smileys/lemmings/laugh.gif" alt=":D" title="Laugh" class="smiley" />

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.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Simon

The notation from the PM was merely binomial coefficients, with (n k) as shorthand for binom(n, k) = n! / ( k! * (n-k)! ). I still used brackets for grouping all over the place, so a space between two numbers was actually important. The usual notation in plaintext seems to be binom(n, k), which I will use in the future for clarity.

-- Simon

Proxima

Solution to Insane Steve's tetrahedron puzzle. (By the way, a million is the same everywhere, it's only numbers above that that vary.)

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.

Proxima

http://www.lemmingsforums.com/index.php?topic=533.msg14894#msg14894">Quote from: Insane Steve on 2012-09-20 01:58:44
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

chaos_defrost

Yea, those are what I also got. For the other two, I'm trying to map a function to the number of vertices (we know f(4) and f(http://www.lemmingsforums.com/Smileys/lemmings/cool.gif" alt="8)" title="Cool" class="smiley" /> - 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.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Simon

I'd do it with a Markoff chain, which is easy for the square, but gets large for the other shapes. Is there a trick that saves work? (Except just identifying equivalent states in the chain.)

-- Simon

chaos_defrost

http://www.lemmingsforums.com/index.php?topic=533.msg14913#msg14913">Quote from: Insane Steve on 2012-09-21 11:32:34
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
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Proxima

I have an answer for the square:

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.

chaos_defrost

Yea, square looks good.

Hexagon is deceptively tricky:

http://www.lemmingsforums.com/index.php?topic=533.msg14913#msg14913">Quote from: Insane Steve on 2012-09-21 11:32:34
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)
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Simon

I have found this variant of the 15-puzzle: http://homepages.cwi.nl/~tromp/oriscript4.html" class="bbc_link" target="_blank">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.

-- Simon

chaos_defrost

Neat puzzle. I took 62 moves the first time I solved it but that's probably not optimal. It could be really interesting if larger grids are used.

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%
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Minim

Interesting puzzle, and it's not too frustrating either. http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" /> 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.
Level Solving Contest creator. Anybody bored and looking for a different challenge? Try these levels!

Neolemmix: #1 #4 #5 #6
Lix: #2  #7
Both Engines: #3

Simon

Here's another cute logic puzzle. The site I got it from offers a solution, thus no link yet.

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

ccexplore

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.

Proxima

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.

Simon


chaos_defrost

So on the puzzle competition board http://thesuicidalrodents.proboards.com/index.cgi" class="bbc_link" target="_blank">here I posted a few puzzles from a competition I want to host on another site somewhere. There's one more with a question on it posted there. I'd be very appreciative if some people gave it a go.

(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.)
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Proxima

I have found this variant of the 15-puzzle: http://homepages.cwi.nl/~tromp/oriscript4.html" class="bbc_link" target="_blank">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.

chaos_defrost

I saw a site a little while ago which has one of my personal favorite "humans are wired really oddly" puzzles on it and want to share. There are two parts.

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.

http://img.photobucket.com/albums/v495/insanesteve/cards1_zps0b950860.png" alt="" class="bbc_img" />

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.

http://img.photobucket.com/albums/v495/insanesteve/cards2_zpsd994227a.png" alt="" class="bbc_img" />

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.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Clam

Nice puzzle, and a curious bit of psychology http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

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.

chaos_defrost

Question that came up recently on Skype:

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  http://www.lemmingsforums.com/Smileys/lemmings/thumbsup.gif" alt=":thumbsup:" title="Thumbs Up" class="smiley" />
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

ccexplore

Technically you never said anything about the coin being fair.  Therefore as a betting man, given the information as provided here, I'd argue it is more likely than not that your coin is crocked and thus the 101st flip is more likely than not to also come up heads. http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

Yes, I know what the "real" answer is, but don't say you didn't see this coming. ;p

chaos_defrost

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"  http://www.lemmingsforums.com/Smileys/lemmings/sad.gif" alt=":(" title="Sad" class="smiley" />
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

GuyPerfect

Along those statistics lines...

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?

chaos_defrost

The number of Starman Supers required to get the Sword of Kings is geometrically distributed with P(X >= x) = 1 - (1-p)^x. given p = 1/128, the odds of requiring 256 or more Starman Supers is 13.43% or so. Geometric drop rates have no memory and can be very cruel sometimes  http://www.lemmingsforums.com/Smileys/lemmings/cry.gif" alt=":'(" title="Cry" class="smiley" />
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

GuyPerfect

Okay, Mr. Mathy Pants. (-:

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?

Proxima

The chance of not getting the sword after n attempts is (127/128)^n.

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.

GuyPerfect

Another correct answer! In case you're wondering why I'm using math questions, it's because there are many real-world situations that you'll need to know how to solve. Often times, this means math. It doesn't matter how clever you may be; sometimes the only way to know something is to calculate it.

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 http://bulbapedia.bulbagarden.net/wiki/Save_data_structure_in_Generation_III" class="bbc_link" target="_blank">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.

Proxima

That's a tough one. For each individual order, the chance of not catching it in n attempts is (23/24)^n, so as a first approximation, the chance of catching all 24 is 1 - 24 x (23/24)^n. But then you've double-counted all the scenarios in which you miss out on two orders, but if you subtract those, you're triple-counting all the scenarios in which you miss out on three orders, and so on.

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.

Simon

#160
I haven't done the following myself yet. I don't know how difficult this is, but it looks harder than the previous triplet-freeness problem.

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

chaos_defrost

bump for a simplish but kind of interesting maths puzzle

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  http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

mobius

Here's a quick one I found in my local newspaper:

which of the following does not belong?

a - large green square
b - large red circle
c - large green circle
d - small green circle
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain


Simon

I guess c (large green circle), for it shares each property with another item, unlike the other items.

This of course has no logical solution and we can only guess what the problem author wants.

-- Simon

mobius

correct!

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
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain


chaos_defrost

Wow, are you serious, hahahaha

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.  http://www.lemmingsforums.com/Smileys/lemmings/XD.gif" alt=":XD:" title="XD" class="smiley" />
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Zaphod77

http://www.lemmingsforums.com/index.php?topic=533.msg22368#msg22368">Quote from: Insane Steve on 2014-09-13 11:00:24
True or false: This is a true statement.  http://www.lemmingsforums.com/Smileys/lemmings/XD.gif" alt=":XD:" title="XD" class="smiley" />

yes. http://www.lemmingsforums.com/Smileys/lemmings/smiley.gif" alt=":)" title="Smiley" class="smiley" />

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.

Proxima

I disagree -- the statement is neither true nor false. Raymond Smullyan explained that in order for a statement to be true or false, we must understand what it would mean for it to be true, i.e. what the statement is claiming. "Apples grow on trees" is true because we know what apples are, what trees are and what "to grow" means, and putting these together makes a true claim about the world. We cannot understand what it would mean for "This statement is true" to be true because we would first have to know what it means for "This statement is true" to be true.

chaos_defrost

While pondering what went wrong with my life to this point, I remembered a corporate presentation given the day before my failed actuarial internship started:

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  http://www.lemmingsforums.com/Smileys/lemmings/sad.gif" alt=":(" title="Sad" class="smiley" />
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Clam

1/3.
  • 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.

Simon

1/3, yes.

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

chaos_defrost

Yea, that's what I got, using Simon's method. Place point A, without loss of generality align the triangle so a vertex is at the point, chord is longer iff the second point falls in the arc corresponding to the opposite side, which happens 1/3rd the time.

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*
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

Proxima

Wow, that's hilarious. I assume the intention was to ask "given a fixed circle, what is the probability that a randomly chosen chord is longer than the side of the inscribed equilateral triangle?" This is ambiguous because "a randomly chosen chord" is not rigorously defined. One method of random choice is to choose two points on the circumference and connect them. Another, as you mentioned, is to choose a single point in the interior (all points being equally likely) and generate the chord of which that point is the midpoint (this is always unique unless the interior point is the exact centre). Using this method, the probability is 1/4 because success occurs in exactly those cases when the point falls within a circle of the same centre and half the radius. Yet another method is to choose a bearing at random, then choose at random a line with that bearing that crosses the circle; with this method the probability is 1/2.

By wording the question so as to eliminate this ambiguity, they undermined the whole point of asking the question in the first place  http://www.lemmingsforums.com/Smileys/lemmings/tongue.gif" alt=":P" title="Tongue" class="smiley" />

geoo

#173
I just stumbled across this cute theorem:

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:

111 ***
1*1 *8*
111 ***    8x1 = 1x8



**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

Proxima

Quote from: geoo on October 03, 2015, 03:57:30 PMProve this theorem. The proof is a nice and intuitive counting argument.

Spoiler
A pair of touching boxes adds 1 to the total if and only if exactly one box of the pair is a mine. This is invariant under the switching operation.

Simon

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

NaOH

This was posed by a friend of mine this morning:

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?

mobius

Quote from: Simon on December 26, 2015, 02:41:03 AM
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.
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain


Simon

Quote from: möbius on December 26, 2015, 10:25:38 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.

Quote1. 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.

QuoteThere 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

bsmith

How about this algorithm. I don't have end-of deck behavior, just the basic idea of the main process.
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

Simon

Very good! This was also Proxima's idea on IRC: With substrings like (red, X, black), we can ignore X and score 1 block boundary here.

Love how you give the basic idea. :-)

-- Simon

geoo

NaOH and I discussed the cookie puzzle in IRC. For posterity, I'm summarizing the discussion here:

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
NaOH's solution:
10
12
4, 14, 14
6, 6, 16
8

Optimality sketch:
(1) It's pointless to have one box with all cookies of the same number of chocolate chips: leaving only one cookie of that kind would not affect the probabilities.
(2) A box with one cookie cannot be adjacent to a box with two cookies: imagine X has 1 cookie, Y has 2 cookies, Z an arbitrary number of cookies. Both cookies of Y each must have more chocolate chips than the cookie in X. Assume the cookies in Y have a and b chips, a <= b. Then changing b to a is still a valid solution because Z still trumps Y. But by (1) we can then remove one of the cookies, thus the solution wasn't optimal. The same argument works if Z has 1 cookie, Y 2 cookies, X arbitrarily many.
(3) A sequence of two (or more) consecutive boxes all containing only one cookie each can be collapsed into a single box: Removing (all but) one of the two (or more) boxes still leaves a cycle of non-transitive boxes.
(4) There are at least two boxes with more than 1 cookie: Otherwise, we have a sequence of number of cookies of 1, 1, 1, 1, n that can by (3) be collapsed into a sequence 1, n. However two dice/boxes cannot be non-transitive.
(5) So we must have at least 2 boxes with 2 or more cookies. If there are exactly two such boxes, then by (2) these two boxes must have at least 3 cookies, for a total of 9. With 3 or more such boxes we exceed the total of 9 cookies as the only valid sets of cookie numbers (partition of 9 into 5 parts) would be 1, 2, 2, 2, 2 or 1, 1, 2, 2, 3, neither of which works by (2) and (3).

Simon

Yes, very nice writeup with a proof.

<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

Simon

#183
3-5 years ago, I saved this puzzle to a file, intending to post it here here once the then-running puzzles were solved. Shockingly, I've never come around to post it. Here it is!

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

Ramon

Spoiler

A drew two black balls, so he must have the BBB or BBW box. Since he knows the color of the third ball, his box is labeled as one of those two possibilities and the third ball has the opposite color than what's on the label.

Similarly, B has the BBW or BWW box with one of the respective opposite labels. From the information so far, we can already rule out 2 of the 4 possibilities: (BBW,BBW) and (BBB,BWW), as the same label would otherwise have to be used for both.

C too drew two white balls, but makes no statement about his knowledge of the third ball. He must have the BWW or WWW box. In the following part I will assume that C not mentioning he knows the color of his third ball means he doesn't know it, else my solution would not be unambiguous.

If C had the BWW box, that leaves B with BBW and A with BBB. The corresponding labels would be A:(bbw), B:(bww), C:(www). However with the (www) label C would know the color of his third ball, so we rule it out.

Thus C has the WWW box, now let's look at the labels of boxes A and B, for which there are two possibilities (we previously ruled two of them out).

a) (BBW,BWW) labeled as (bbb,bbw). Thus C must be labeled (bww). In this case however C would know the color of his third ball, so we can rule it out yet again.
b) (BBB,BBW) labeled as (bbw,bww). Thus C must be labeled (bbb).

The last case fulfills all the assumptions made so far and is the conclusion I have come to:

A has (BBB) labeled (bbw)
B has (BBW) labeled (bww)
C has (WWW) labeled (bbb)

Therefore D can conclude without looking at his box or its label that he must have the BWW box with the www label.

Simon

#185
Correct answer by Ramon!

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
C: "I drew two white balls, but I don't know the color of my third." See next post.

Thus, Ramon's answer remains correct, it is now the only correct one.

-- Simon

Simon

Changed the 4-men-4-balls riddle again: Now, when C announces that he cannot deduce his own 3rd ball, C explicitly doesn't take into account the statements of A and B.

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

Simon

#187
I've found this one but haven't solved it yet. Feel free to post solutions in spoiler tags, but I won't look at any solutions until I've solved it.

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

Dominator_101

Spoiler
Leave your shoes in the first car, proceed through the cars sans-shoe, and when you get your shoe back that's how many cars
:P

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
So, one thing I'm not sure of here is how to actually CONFIRM you've gone around. Even if you did something like always turn all the lights to off, can you really be sure you've done a full loop? Maybe there just happens to be a run of x trains all with their lights off that happen to appear after the point you think you've looped, so even by doing what you think is a second loop maybe you didn't actually do a second loop.

The only thought I have to deal with this so far is you need to do another loop in the opposite direction where you change something and confirm that you are able to observe said change. This seems inefficient, though, although would still be linear time since it's just another cycle of n, but the question is then if you do an extra cycle to confirm the size, but find out that you're wrong, what does that do to the time complexity? Is there a way to keep going still in linear time?

geoo

#189
This is a nice one! Below my proposed solution.

Spoiler

For i from 1 to infinity:
- Remember the status of the wagon you start in
- Move ahead by i wagons, and flip the switch of the i-th wagon
- Go back i wagons so you're back at the start. If the light has changed, then you're done (n=i).

This takes O(n^2)

We can make this O(n log n) O(n) but O(n) space if instead we go to the 2^i-th wagon in each iteration, and we log the full sequence of lights we encounter, not just the starting one.
If on the way back something has changed, we know we've made a full loop and we can infer n from the position of the light that has changed.

I don't know if there's a linear time solution.

EDIT: After reading Simon's notes, I realized my math is wrong and this is in fact O(n) and not O(n log n) time: Sumi=1k 2^i = 2k+1-1, and k ~ log n.
Together with Simon's trick to turn off the lights along the way this makes for a linear time, constant space solution, which sounds optimal.

Simon

#190
Dominator has found exactly the problem that makes the task interesting. You're on good track.

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
You can remove the extra space complexity from the second algorithm: You don't have to log a sequence of lights in a separate list; instead, turn off all lights on the way forward. Turn on light i. Check which car on the way back has lights on.

I don't believe the task is solvable in linear time. geoo showed that walking 2k wagons is already linear time; this is the amortized linear time that std::vector<T>::push_back must strive for by specification, and it achieves that by reallocating every 2k times or, in other implementations, every 1.5k times.

Walking longer won't improve it

Edit: This section here, I wrote it when I assumed that geoo's second algorithm ran in O(n log(n)) time.

I believe the task is solvable in O(n log(log(log(...(log(n))...)) for any number of chained logs. Let f be a function N -> N that grows super fast with k < log(log(...(log(f(k))). Instead of going 2k wagons on the k-th iteration as geoo suggested, we instead go f(k) wagons on the k-th iteration. Otherwise, the algorithm is the same: Turn off the light on the way forward, turn on the light in car f(k), and see how many cars you have to go back to reach one with light on.

The downside of this theoretical improvement is that the algorithm becomes really slow for common numbers of n that you expect. You don't want to walk through 1,000,000 cars before you see on the way back that there are 19 cars in the loop.

The 2k-idea sounds like a very good choice, it's also when std::vector reallocates, but I don't know the theory behind this design.

-- Simon

Dominator_101

(unrelated, but I tried the 4 box puzzle that was the previous one for fun, here's my working out if anyone is interested)
Spoiler

(labels in caps, contents in lowercase)
Who can have what label:
A: bb
   BBB - Know third is w
   BBW - Know third is b
   BWW - can't know third because it's already wrong
   WWW - can't know third because it's already wrong

B: bw
   BBB - can't know third because it's already wrong
   BBW - Know third is w
   BWW - Know third is b
   WWW - can't know third because it's already wrong

C: ww
   BBB - Could be
   BBW - Could be
   BWW - Can't be because he would know the third
   WWW - Can't be because he would know the third

D: Label must be WWW because no one else's can be

B must be labeled BWW because he's the only one who can have that, so his third is b.

Because B has bbw contents, A must have bbb contents, so his label is BBW. This leaves label BBB for C

Labels:
A: BBW
B: BWW
C: BBB
D: WWW

Either C or D must have www as the contents, but D can't have that because that's his label. So C has www. This leaves bww for D's contents

Contents:
A: bbb
B: bbw
C: www
D: bww

For the current puzzle, going off Simon's post:
Spoiler
To avoid the 'walking a million cars to find out there's 19' problem, you could always say that if you hit a series of x cars with lights off that matches the number of cars you already walked through (or maybe bump it to 2x or something for safety, since if car 19 was already off you'd turn around after 18x2 instead of 19x2), you could just turn around at that point, though that doesn't exactly fall neatly into a time complexity.

I'm trying to decide if you did turn a light on and walk back to start, if you con't find a light on on the way back (meaning you didn't loop yet), if it would be helpful to proceed in the other direction or not. Probably not since you still wouldn't really know when you hit the light you turned on, so might as well continue the same direction you already were, knowing you can probably proceed to at the very least 2y cars (where y is the car you decided to turn around in the first time) before you would reach the point where you might've looped.

All in all, not sure if these are even helpful, just trying to throw some ideas out.

Dominator_101

#192
Okay, had some more thoughts on this yesterday while trying to sleep, here's my thoughts/findings:

Spoiler

So, I mused in my previous post about whether or not it would be more efficient to change directions every time you returned to the starting car, and after more thinking/exploration I determined that it is, it's actually MUCH more efficient to change directions every time you return to the starting room. Here's the basic idea (also, I'm generally going to use right and left to refer to the directions because it just made the most sense to me to think about it that way):

So if every time you re-traverse the train you always start going right, all those steps you take to get back to the last car you checked are all wasted. You already know the entire path to that train car, so you aren't gathering any new information. However, if you change from right to left every time you return to the first car you can actually gather some information on the trip back out. If I start going right, don't find the end, but then go left instead, I now get to see the two cars to the left of start, which is new information. Then, when I don't find it on the left and head back right, even while traversing back to the furthest car I'm still gathering information, as I might've actually changed a light on that side now.

I'm not sure if I explained that well enough :P but here's some data I gathered on the total amount of steps that it takes to confirm the car numbers to prove that it's actually a lot more efficient:
Spoiler
Only moving one way:
Only Right, Case 1 : 2 steps
Only Right, Case 2 : 6 steps
Only Right, Case 3 : 12 steps
Only Right, Case 4 : 20 steps
Only Right, Case 5 : 30 steps
Only Right, Case 6 : 42 steps
Only Right, Case 7 : 56 steps
Only Right, Case 8 : 72 steps
Only Right, Case 9 : 90 steps
Only Right, Case 10 : 110 steps
Only Right, Case 11 : 132 steps
Only Right, Case 12 : 156 steps
Only Right, Case 13 : 182 steps
Only Right, Case 14 : 210 steps
Only Right, Case 15 : 240 steps
Only Right, Case 16 : 272 steps
Only Right, Case 17 : 306 steps
Only Right, Case 18 : 342 steps
Only Right, Case 19 : 380 steps
Only Right, Case 20 : 420 steps

Switching directions:
Left/Right, Case 1 : 2 steps
Left/Right, Case 2 : 6 steps
Left/Right, Case 3 : 7 steps
Left/Right, Case 4 : 13 steps
Left/Right, Case 5 : 14 steps
Left/Right, Case 6 : 22 steps
Left/Right, Case 7 : 23 steps
Left/Right, Case 8 : 33 steps
Left/Right, Case 9 : 34 steps
Left/Right, Case 10 : 46 steps
Left/Right, Case 11 : 47 steps
Left/Right, Case 12 : 61 steps
Left/Right, Case 13 : 62 steps
Left/Right, Case 14 : 78 steps
Left/Right, Case 15 : 79 steps
Left/Right, Case 16 : 97 steps
Left/Right, Case 17 : 98 steps
Left/Right, Case 18 : 118 steps
Left/Right, Case 19 : 119 steps
Left/Right, Case 20 : 141 steps
Only moving one direction will always take Σ2n (0 to n) steps to 'solve', whereas changing directions takes...Okay, so, I'm not really sure to be honest. Maybe someone better at math can determine that. The nice thing, though, is that for odd number n the number of steps to 'solve' will always just be the number of steps to solve n-1, plus 1 (because as soon as you enter the next car you will have noticed it changed)

EDIT: Looked into the numbers a little bit, best approximation I can find for the number of steps for each is this (I think):
Σi (for i=1 to n/2) + (3n/2) + 1 (or +2 for odd numbers)
(n/2 is floored for odd numbers as well)
I don't really understand the pattern but...I think this should be accurate?

I also made a quick python script for testing this, for anyone curious. Feel free to check my work/modify the search functions/judge my coding:
Spoiler
#!/usr/bin/python
import random

######################
#  Search Functions  #
######################

# Traverse the train always starting to the right
def forwardSearch(train):
totalSteps = 0
stepsToTake = 0
startingLight = train[0]
# Break at 100 in case I'm bad at coding
while stepsToTake < 100:
stepsToTake += 1
# Move to the last car
totalSteps += stepsToTake
# Change the light
train[stepsToTake%len(train)] = not train[stepsToTake%len(train)]
# Walk back to starting car
totalSteps += stepsToTake
# Check the light
if train[0] != startingLight:
# We changed the first car, we know how many cars
return (stepsToTake, totalSteps)

# Traverse the train both left and right
def swingSearch(train):
totalSteps = 0
stepsToTake = 0
startingLight = train[0]
observedRight = []
observedLeft = []
polarity = -1
# Break at 100 in case I'm bad at coding
while stepsToTake < 100:
stepsToTake += 1
polarity *= -1
lights = observedRight if polarity > 0 else observedLeft
# Walk the car
for i in range(1, stepsToTake+1):
totalSteps += 1
curLight = train[polarity * i%len(train)] # Don't access imaginary cars
if i > len(lights):
lights.append(curLight)
elif curLight != lights[i-1]:
# Light changed, log
return (i + stepsToTake-1, totalSteps)
# Change the last light, as well as our observed version
lastCar = polarity * stepsToTake%len(train)
train[lastCar] = not train[lastCar]
lights[stepsToTake-1] = not lights[stepsToTake-1]
# Walk back to starting car
totalSteps += stepsToTake
# Check the light
if train[0] != startingLight:
# We changed the starting car, we know how many cars
return (stepsToTake, totalSteps)

################
#  Run Trials  #
################
def makeTrain(size):
train = []
for i in range(0, size):
train.append(random.randint(0,1) == 1)
return train

NUM_TIRALS = 20
for i in range(1, NUM_TIRALS+1):
# Make a train
train = makeTrain(i)
# One direction search
guess = forwardSearch(train)
if guess[0] == i:
print 'Only Right, Case', guess[0], ':', guess[1], 'steps'
else:
print '!!! BAD ANSWER !!!'
# Switch direction search
guess = swingSearch(train)
if guess[0] == i:
print 'Left/Right, Case', guess[0], ':', guess[1], 'steps'
else:
print '!!! BAD ANSWER !!!'
(EDIT: apologies, it doesn't seem to like my code in a spoiler tag)

I assume this same theory should work for the more complex ways of traversing the train as well, I just did the simple case because it was the easiest.

Simon

Dominator's proof of 4-boxes-3-balls is right, very nice.

Re: Train circle

Right, by alternating left and right, you're adding the chance (I believe a guarantee even?) that you run into the switched-on light of your previous iteration whenever that previous iteration made it further than halfway around the circle. Since we travel 2k wagons forward on the k-th iteration, cutting short the final iteration is a considerable save.

Good find! The complexity remains constant space, linear time, but the factor of the linear time improves.

-- Simon

Armani

My newest NeoLemmix level pack : Lemmings Halloween 2023 8-)

My NeoLemmix level packs(in chronological order):
  Lemmings Uncharted [Medium~Extreme]
  Xmas Lemmings 2021 [Easy~Very Hard]
  Lemmings Halloween 2023 [Easy-Very Hard]

Simon

#195


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 touching kittens edges.

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


Armani

Assume no two nodes have exactly the same number of edges.
Then the number of edges of every nods = {0,1,2, ... , n-1}
but this is impossible
contradiction!
My newest NeoLemmix level pack : Lemmings Halloween 2023 8-)

My NeoLemmix level packs(in chronological order):
  Lemmings Uncharted [Medium~Extreme]
  Xmas Lemmings 2021 [Easy~Very Hard]
  Lemmings Halloween 2023 [Easy-Very Hard]

Simon

Yep! For completeness, elaborate why exactly it's impossible to have excatly the edge counts 0, 1, ..., n − 1.

Your proof was the first that I found, too. Here is a second proof that I found today:
Spoiler

Induction base case n = 2: I've shown this as an example in the problem statement.

Induction hypothesis: All graphs with fewer than n nodes contain two nodes with identical edge counts.

Induction step: Let G have exactly n nodes. Consider a connected component X of G with the maximum possible number of nodes.

  • If X has exactly 1 node, then G contains no edges at all. Since n > 2, pick any two nodes; they'll have an identical edge count of 0.
  • If X has 1 < x < n nodes, then X, considered a graph by itself, contains two nodes with identical edge counts by the induction hypothesis.
  • If X has n nodes, the n nodes each have an edge count of 1, 2, ..., n − 1; none have an edge count of 0 because X is connected. The function that maps the n nodes of X into those n − 1 possible edge counts fails to be injective due to the pidgeonhole principle. Thus, there are two nodes in X with equal edge count.
All three cases satisfly the claim, thus the claim is true for n.

-- Simon

Armani

QuoteYep! 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-)
My newest NeoLemmix level pack : Lemmings Halloween 2023 8-)

My NeoLemmix level packs(in chronological order):
  Lemmings Uncharted [Medium~Extreme]
  Xmas Lemmings 2021 [Easy~Very Hard]
  Lemmings Halloween 2023 [Easy-Very Hard]

geoo

#199
Here's a Lix-related logic puzzle (which I haven't solved yet):

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.

Dominator_101

So I was thinking of a different approach to the graph problem, but I kept hitting snags in my logic so I might think that over longer.

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

Okay, so my initial read on this is it's simply doing a bubble sort, you can move one item at a time and bubble it up or down to change the priorities. If that's the case, our worst case complexity is the same as bubble sort, which would be n-1 moves, or (p*h)-1 where p = num players and h = num hatches.

However, there are a couple different interpretations here that still fulfill the criteria of the problem, and it has to do with how strict we want the ordering. There's two variables we can tweak that give us slightly different scenarios:

Strict player orders: Do we care that player A always comes before player B?
Strict hatch order: Do we care what order the hatches release as long as they are synced for all players?

For example, this arrangement fulfills the original reqs if we don't need strict ordering for either:
B2 A2
B3 A3
B1 A1

I'm assuming here that we probably want non-strict player order (player order doesn't really have meaning since player order is random on level start) but strict hatch ordering (we want the level to spawn from top-down). Given that, we have a bit more control over the bubble sort. The worst case is still an inverted list, like so:
B2, A2, B1, A1
However, since we don't care about player order, we don't actually need to reorder B2 and A2, so instead of a worst case of 3 our worst case is only 2, to move B1 and A1 to the front (or B2 and A2 to the back, if you'd prefer :P)

Best as I can tell, the worst case complexity for this scenario is equal to p(h-1). No matter the original sort order, we can always ignore one group of hatches and use their player order for the other hatches as we move them around.

Now, in the very non-strict case where we don't care about player order OR hatch order, our worst case changes yet again. Now an inverted case isn't strictly worst because we don't care about the hatch order, we just need to group the same hatches with the same player order, so I think worst case becomes hatches grouped by player (A1, A2, A3, B1, B2, B3). To me, this seems like the most complex to try and find the formula for. because it's weird to think of scenarios, but I think that it ends up being (p-1)(h-1).

That also makes me assume if you wanted to keep player strict but hatch non-strict, it would be (p-1)h, but I honestly haven't checked that at all and am just assuming based on the other formulas I came up with.

Hopefully my interpretation is correct here? I think that no matter how you slice it it should be reducible to a list so I assume it should be a valid line of reasoning.

You could make this even more complicated if you consider that it's easier to change the priority in the text file directly, which allows you to move adjacent hatches up/down at the same time with copy/paste. My gut says worst case would still be arranged in a way where you're moving single items at once, but I haven't thought much about it.

Simon

#201
geoo's hatch distribution is still open.




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

. . . . . . . .
. . . . . . . .
. N N . . N N .
. N N . . N N .
. N N . . N N .
. N N . . N N .
. . . . . . . .
. . . . . . . .

All vacant squares are attacked. In addition, all knights themselves are attacked by other knights, even though that isn't required by the problem statement.

The solution is a local minimum, in the sense that you can't remove any of the knights without redistributing the other 15.

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

Armani


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:



So the answer is 12.
My newest NeoLemmix level pack : Lemmings Halloween 2023 8-)

My NeoLemmix level packs(in chronological order):
  Lemmings Uncharted [Medium~Extreme]
  Xmas Lemmings 2021 [Easy~Very Hard]
  Lemmings Halloween 2023 [Easy-Very Hard]

Simon

Excellent solution with proof of minimality, nice!

-- Simon

DireKrow

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 with Nonograms. I dub it, the Nonoloop.


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


Puzzles

Nonoloop 1

Nonoloop 2

Nonoloop 3

Nonoloop 4


And attached is a single pdf with the rules and all puzzles, if that's preferred
LOTY 2020 Winner
My NeoLemmix Levels: The Krow Files (File A v1.2 released 21-Feb-2020)

Simon

#205
The four puzzles are of satisfying quality: solvable with sensible contemplation, but without far-fetched guesswork. Thanks! Attached are my solutions. I printed the PDF and solved with pen and paper.

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.
-- Simon

mobius

I started messing around with Chat GPT 4 recently. I gave it this puzzle:
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:

QuoteThe 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.

Quote from: DireKrow on June 18, 2022, 07:49:15 PM
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 with Nonograms. 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
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain


mobius

well this was interesting; I rephrased the question to "what if the theoretical attacks of the knights can overlap?"

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.
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain


chaos_defrost

If you like pencil and paper style puzzles, I highly recommend Instructionless Grid:
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.
"こんなげーむにまじになっちゃってどうするの"

~"Beat" Takeshi Kitano

mobius

from a discord server I joined recently (cracking the cryptic) I'm learning of tons of kinds of simple puzzle games like this one:

https://puzz.link/p?cocktail/10/10/qhl3aml66ccldaolhb0f7v1guf00uf1gvsu02g13223113930130g31001322

this involves shading a particular number of squares in regions. There's another called Kouchoku that's about drawing loops around nodes.
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain


MASTER-88

Im not favor much puzzle type RPG games. I´ll like more plan battle strategys etc... and im not also very math grade talented man. More visual and memorize talented. Its my strong point my IQ

I think this one Lufia 2 SNES: Called name : Most Difficult Trick. Even my 135 IQ its take me 3 & half hours recorded attempts total. This completion attempt take 30 minutes. I´ll very glad myself when i completed it without spoilers. Serisouly it was harder than any license lemmings games levels IMO.

https://www.youtube.com/watch?v=2bgyNO4uRx0

How ever its not mandatory puzzle. Completion voluntary if you like some high challenge puzzles to solved.
Video games player.
See my youtube: Several games videos includes lemmings
http://www.youtube.com/user/metroidmaster88?feature=mhum

My Huge Lemmings Projects

Lemmings Custom + Triology 394 Levels
Custom +1 (120 Levels)
https://www.lemmingsforums.net/index.php?topic=5840.0
Custom +2 (124 Levels)
https://www.lemmingsforums.net/index.php?topic=5993.0
Custom +3 (150 Levels)
https://www.lemmingsforums.net/index.php?topic=6014.0
Amiga Classic Special (30 Levels)
https://www.lemmingsforums.net/index.php?topic=6345.0

Lemmings World 150 Levels
https://www.lemmingsforums.net/index.php?topic=6751.msg102567#new

My SNES Lemmings MAX Points Project
https://www.lemmingsforums.net/index.php?topic=4539.0