Questions With Answers (cf. the "Universe Threads")

[Fjones]

You have a 100 story building. One of the floors has a radioactive chemical in it. But we can only determine which floor it is using the following (absurd but hypothetical) method --


We have two "magic" spheres. These spheres will pass through any and all floors of the building, including the roof, but will stop when they hit street level, because the base of the building is made out of a special material that stops the fall of these spheres.

If one of the spheres passes through the floor with the radioactive material, it gets marked by this material, and we would know that one of the floors it passed through had the material. But the sphere would still continue down to the base of the building. Also, that sphere would no longer be useful, because it is already marked. There would be no Indication at the actual floor that had the radioactive material in it.


Question -- What is the minimum number of drops needed to ensure that we discover the floor with the radioactive material, and what is the exact method that would do so?

To clarify --

You can drop the first ball from any floor. There are 100 possible floors that may have the radioactive material (the floor separating the street level from the 2nd floor would be the 1st, and the roof would be the 100th).

No matter what, the dropped ball will come to rest on the ground floor, and it will either have the marker, or not.

Once that ball is marked, you MUST use the second ball, and if that one gets marked without knowing EXACTLY which floor has the material, you lose.

To answer the question, you must state which floor you drop the first ball from, and explain how you will proceed from there.

 

[Akoto]

^Thinking out loud: binary search wont work (dropping the first ball from floor 50 to determine higher or lower) because the first ball will be marked and still have a maximum of 50 floors to guess between, and dropping the first ball from each floor 1 by 1 isn't a very efficient search at all...

My best guess is to drop ball 1 from floor 50, then use ball 2 dropped from either floor 51 or floor 1 depending on the result from ball 1. If ball 1 isn't marked from a drop from floor 50, then drop it from 75 and reduce the maximum number of drops needed for ball 2 by 50%.

Here's an easy one I got from 4chan:

 

[Binge Artist]

Answer: x=e^(1/e).
]

Good job! I've never actually been able to "derive" x myself.

 

[Binge Artist]

Here is an "FAIL" solution to RL's analysis problem.

The solution is informal because A it's been a long time since I studied analysis, and B I never was any good at it anyway. I basically bombed Columbia's watered down version of Harvard's Math 55.

NSFW:

I use < in place of < or = for convenience, and I use bold letters to indicate an integral.

Let A be the subset of [0,1] for which f(x) < 0 and let B be the subset of [0,1] for which f(x) > 0. Let a and 1-a be the measures of A and B respectively. Let M and N be the average values of f on B and |f| on A, respectively.

We solve the problem by showing that the assumption that both M and N are less than 4 yields a contradiction.

Here's the bit of handwaving. I say:

xf(x) on [0,1] = 1 < Mx on [a,1] - Nx on [0,a].

The rationale is pretty straight-forward. The integral of xf(x) can be made "bigger" by multiplying negative values of f by small values of x (ie, x in [0,a]) and by multiplying positive values of f by large values of x (ie, x in [a,1].

Anyway, grinding out the RHS of the inequality, we get

1 < M/2 - Ma^2/2 - Na^2/2 or,

2 < M - Ma^2 - Na^2.

Also, since f(x) over [0,1] = 0, we have

M(1-a) - Na = 0 (since integral of y = avg y times measure of set).

Hence,
Na = M - Ma, and
Na^2 = Ma - Ma^2.

Substituting this expression for Na^2 into our inequality yields

2 < M - Ma (also, since Na = M - Ma, we have Na > 2).

Since we are assuming M < 4, we get a < 1/2. But since Na > 2, we get N > 4, a contradiction!

FAIL

 

[Binge Artist]

Here's an easy one I got from 4chan:[/IMG]

I suspect that:

NSFW:

C would reason thusly: "If I were white, D would have known he was black, and called out "black"...But D never called out "black"... therefore I am black"

 

[Binge Artist]

You have a 100 story building. One of the floors has a radioactive chemical in it. But we can only determine which floor it is using the following (absurd but hypothetical) method --


We have two "magic" spheres. These spheres will pass through any and all floors of the building, including the roof, but will stop when they hit street level, because the base of the building is made out of a special material that stops the fall of these spheres.

If one of the spheres passes through the floor with the radioactive material, it gets marked by this material, and we would know that one of the floors it passed through had the material. But the sphere would still continue down to the base of the building. Also, that sphere would no longer be useful, because it is already marked. There would be no Indication at the actual floor that had the radioactive material in it.


Question -- What is the minimum number of drops needed to ensure that we discover the floor with the radioactive material, and what is the exact method that would do so?

To clarify --

You can drop the first ball from any floor. There are 100 possible floors that may have the radioactive material (the floor separating the street level from the 2nd floor would be the 1st, and the roof would be the 100th).

No matter what, the dropped ball will come to rest on the ground floor, and it will either have the marker, or not.

Once that ball is marked, you MUST use the second ball, and if that one gets marked without knowing EXACTLY which floor has the material, you lose.

To answer the question, you must state which floor you drop the first ball from, and explain how you will proceed from there.

NSFW:

Shortest way I see, is 14 drops. The floors are 14, 27, 39, 50, 60, 69, 77, 83, 88, 92, 95, 97, 99. For example, say the contamination is on the 53rd floor. You will need 8 drops, 14, 27, 39, 50, 60, then, 51, 52, and 53. And it's easy to show that 14 would be the max for any floor using this method. However, who knows if it's the best method!

 

[Binge Artist]

NSFW:

Actually, I think I can prove this is the best way. Let's suppose it were possible to do it in 13 drops. Then the first drop could be no higher than the 13th floor (if the ball got marked, you'd then have to drop from the 1st, 2nd...all the way up to the 12th). The next drop could be no higher than 12 floors up from the 13th, since you've already used up one drop. Following this pattern, you get 13, 25, 36, 46, 55, 63, 70, 76, 81, 85, 88, 90, 91, but after that, you've already passed 13 drops, and floors 92-100 are still unaccounted for.

 

[RedLeader]

Here is an "FAIL" solution to RL's analysis problem.

Keep trying, you're thinking along the right lines. It's not an easy problem (though the solution isn't that long).

 

[Binge Artist]

^just as a hint, does the solution involve anything "high techish" like some kind of dominated convergence theorem, or can it be solved by straight forward integral properties (ie minf dx < (or=) f(x) dx < (or =) maxf dx) ?

Knowing IF a problem has an elementary solution is often a massive hint.

 

[RedLeader]

^The question was taken from a sample PhD qualifying exam in analysis. But don't let that scare you, because the solution requires really nothing but cleaver calculus and a tiny bit of elementary analysis.

A hint would be to take the second integral and do integration by parts, and then use the first integral to simplify. Then think about what you could say about the anti-derivative of f. And yes, the proof is done via contradiction.

 

[Fjones]

^Thinking out loud: binary search wont work (dropping the first ball from floor 50 to determine higher or lower) because the first ball will be marked and still have a maximum of 50 floors to guess between, and dropping the first ball from each floor 1 by 1 isn't a very efficient search at all...

My best guess is to drop ball 1 from floor 50, then use ball 2 dropped from either floor 51 or floor 1 depending on the result from ball 1. If ball 1 isn't marked from a drop from floor 50, then drop it from 75 and reduce the maximum number of drops needed for ball 2 by 50%.

You are overlooking something. If you drop ball 1 from floor 50 and it gets marked, you are screwed. You now have only 1 ball left with 50 floors to rule out.

 

[dspade]

hmm i thought the example had to do with the quantum enigma but not sure. like just by you beleiving the choice is right makes it right until further perception changes the results. kind of like the electron circling the atom.

 

[Fjones]

Shortest way I see, is 14 drops. The floors are 14, 27, 39, 50, 60, 69, 77, 83, 88, 92, 95, 97, 99. For example, say the contamination is on the 53rd floor. You will need 8 drops, 14, 27, 39, 50, 60, then, 51, 52, and 53. And it's easy to show that 14 would be the max for any floor using this method. However, who knows if it's the best method!

ok, let's have some NSFW aroudn this so others can try it!

ALso there is a slight error in your work that isn't really relevant, but nevertheless shold be corrected.

 

[RedLeader]

Here's one:

A=(x,0) and B=(0,y) [with x<y] form a line segment, AB, in the plane that:
1. has length four
2. contains the point (1,1).

What is the value of y? And I'm looking for an EXACT answer; not something like "y=3.76...".

And assume you live in some time and space where a general solution to the quartic equation has yet to be discovered!

Additional FYI: Redleader's last problem involved the number 17. I'm a sucker for the number 17; I think it's totally radical!

So we're not allowed to rediscover the quadratic equation and then apply it in the solution!?!? Is that cheating?

 

[dspade]

i thought this was discussion on the shattering of the third dimension creating time. or the beginning of the universe if you prefer. but anyways im confused on the purpose of the ball story the only way to be absolute would be to go up story by story then look at the ball on the base level. but maybe im missing something unless you simply carry the ball around to each floor and observed when it changed.

 

[Fjones]

Actually, I think I can prove this is the best way. ............. .

NSFW:

Yes. 13 is impossible.

I have the drops as follows --

14 27 39 50 60 69 77 84 90 94 97 99.

I deviated from the pattern after 90, because doign so ensures that at that point, no more than 13 drops would be needed.

 

[RedLeader]

Consider two boys, "John" and "Michael" and their teacher. Each of the two boys writes down a positive integer on a piece of paper and hands it to the teacher, without being able to see the other's number. The teacher then writes down two distinct positive integers on the blackboard and states that one of the two numbers is the sum of the boys' integers. The teacher then turns to John and says "John, can you for sure tell me which one is the sum?" If John, says "no," then Michael is asked the same question. In turn, if Michael says "no," then the question is repeated for John.

Prove that if the boys are suitably intelligent, eventually one will answer with the correct sum (without guessing).

 

[dspade]

this question would be kinda like black jack right youre gauging the reaction of the otherand based on the card you have you make a statistical guess. or did i miss this one completely also.

 

[RedLeader]

dspade, would you mind using the quote function or giving specifics, as there are plenty of outstanding questions currently in this thread? If are commenting on the one I just proposed in #37, unlike blackjack, there's no statistical risk involved.

 

[Binge Artist]

So we're not allowed to rediscover the quadratic equation and then apply it in the solution!?!? Is that cheating?

Well, I guess the point is that it would be fairly easy to write a QUARTIC equation for y, whence one could use the quartic formula. But that would take the fun out of the puzzle.