I'm not sure what u mean by the 'corner case'
@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).
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.
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?
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?
(Not sure how "logic puzzles" came to mean physics problems, but anyway... )
(Not sure how "logic puzzles" came to mean physics problems, but anyway... )they can nevertheless be pretty thought-provoking, simply because our human intuition about physics is not very good, and at the same time, accurate applications of the various principles, laws and equations of physics can be subtle sometimes.
@CCE The newly editted way you describe the problem is basically identical to the way I described it.
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've edited my scenario description hopefully to better capture the setup...maybe. I need to think more about it.I really like your new scenario description, as it still poses the same core problem but avoids all the definition issues and physical impossibilities usually accompanying this "riddle".
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?
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?
Hint: Is the aircraft exerting a force (aka pushing) on the conveyor belt to move forward?
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
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.
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.
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.
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.
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.
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).
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!
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.
With n rectangles you can cover at most n/(n+1) of the triangle's area, by making all rectangles have the same height.[edit: correct a mistake in wording near the end]
n=1: if the original rectangle has base B and altitude H, and the rectangle's width is b', then simple geometry shows its height will be H (1 - b'/B). So the ratio of rectangle's area to whole triangle is 2 * (b'/B) * (1 - b'/B). You can then use calculus techniques (find where derivative of function is zero) to show that the maximum occurs at b'/B = 1/2, resulting in a rect/triangle ratio of 1/2 also. So f(1)=1/2.
n from n-1: Similarly, consider that the bottommost rectangle's width is b'. You get a smaller triangle with base being the top edge of the rectangle, where you should fit the remaining n-1 rectangles in optimal manner. With a bit of geometry, math and calculus similar to what we did for n=1 (which I'll gloss over because it's just literally doing the math), you wind up with this relation for f(n) the area ratio of recntangles to triangle: f(n) = 1 / (2 - f(n-1)).
Calculating the first few values by hand (starting from f(1)=1/2) readily shows that f(n) = n/(n+1), and then formally using mathematical induction and the recurrence equation above you can formally proved that f(n) = n/(n+1). Also as you do the math for the recurrence relation for f(n), you'll find that the value of b'/B ratio for optimal f(n)chop is itself always equals f(n), which gives you the construction method to realize f(n).
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?
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?
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:
____
/| |\
/ | | \
/ | | \
----------
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.
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.)
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.
Bonus question (still simple): Now you may stack pieces and then break them all in one go. What's the optimal solution then?
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.
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 ). 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.
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:
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.
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?
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.
Give the cupcake and the basket to the fifth person, so the person can receive the cupcake while the cupcake remains inside the basket
Read the first sentence (up to but not including the word "and") carefully again.
Since I didn't laugh nor groan, somehow I think the actual intended answer is something else.
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.
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.
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?
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.
If you are indeed unable to actually see what the waiter did with the coffee, then any method you rely on to support your hypothesis that the coffee remained the same, can in principle also be explained by the waiter doing whatever it takes to make the second cup of coffee as identical as possible to the first coffee, including what you did with it before it was returned. For example, if you based it on temperature, or maybe something as crazy as you drop some specific chemical marker in the coffee before it was returned, it is conceivable (however unlikely) that the waiter could've done a bunch of stuff behind the scenes to mimic all the effects on the original coffee between the time you received it and the time it was returned, so that it really is a new cup of coffee that just happens to appear like the original cup under the set of tests you devise.
So given any situation in which you can't actually see what the waiter did, but you strongly suspect that he gave you back the same coffee, there is an alternative hypothesis in which the coffee is not the original. The probability of such alternative hypotheses may be astronomically small, but it's still non-zero.
So what I'm saying is that any solution in which you can't observe what the waiter actually did with your coffee, your certainty that the coffee was unchanged is less than the certainty when you can observe. Therefore the solution that you can observe what the waiter did is the superior answer.
======================
It wouldn't surprise me if the "real" solution is probably one that takes advantage of language ambiguity and other things, and ends up describing a situation that is not quite how you normally picture/interpret things based on the given statements (and thus making my proposed solutions all not applicable). However, while I've briefly considered that sort of reasoning, I've yet to find a good "alternative interpretation" that works well across all the given statements of the problem. But we'll see I guess......
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
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
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.)
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.
(Re. #1) It seems there's really only one good answer to this:
You mention a "chemical marker"...
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.
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 ) 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.
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.
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
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...
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.
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:
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.
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.
Have I told you how the mollusc tried to trick me?They're all Clams.
You're in a DIY store looking to purchase some items for the house. If 1 costs $0.50, 12 costs $1.00 and 144 costs $1.50 .....You're buying sticks of constant length with the aim lay out iterations of some kind of Koch curve to decorate your room, and thus have to break the sticks into bits, and you're counting the substicks you get. But thinking of it, 144 should cost $2.00 then. Hmm...
What is it you are buying?
You're buying digits.
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.
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.
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)
#C1: You got a mobile that is essentially arranged like a binary tree, i.e. each node has either two children nodes (in the mobile, this would be like a bar with submobile on each of its ends), or is itself a leaf with a positive integer weight. Now the mobile is not in equilibrium however, that is there is some submobile (subtree), where the weights of the left and the right submobile differ. The task is to design an algorithm that finds out how many of the weights you have to change at minimum (to an arbitrary, possibly non-integer weight) so that the mobile gets into equlibrium. Run time complexity: O(N log N), where N is e.g. the number of leaves.
I haven't really bothered working on any of the problems, but I do have a Clam-style solution to C1:That bears the (easier) question: how many of these do you have to change?
You don't need to change any weights, since balance is determined by torque not weight. You can just adjust the fulcrum at each bar to balance the torques.
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.
12/5 (or 2.4)
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.).
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.
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.
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
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.)
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.
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.
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.
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.
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?
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.
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.
(In case it wasn't clear, the Highland lemming can choose whether to lie or tell the truth for each answer separately).
(but, if asked a yes/no question, they will always respond one way or the other).
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.
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.
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.
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.
"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.
Also double post for something else I found:
http://puzzle.cisra.com.au/ -- here's a site that runs a puzzle contest every year, and this year's contest looks like it's going to start any day now: though most of the questions look like they are going to be presented the week of the 1st of October.
I'd definitely be up for making a team if there's three other people here interested in these kinds of puzzles. Given that we aren't Australian students we wouldn't be eligible for prizes but it might still be fun.
166667166667000000
166,668,666,667,000,000
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.
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. 2/27
II. 8 / 3^7
III. 15 / 2^10
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%
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.
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.
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.
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%
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*)
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.
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.
I have found this variant of the 15-puzzle: http://homepages.cwi.nl/~tromp/oriscript4.html and you need to enable Javascript.
Rules: You are the white box, and in each step, you can switch places with a neighboring piece (use cursor keys). Purple pieces may only be entered/switched vertically, and the green pieces, horizontally. The object is to move the labelled green piece to the left column.
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.
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.
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"
True or false: This is a true statement.
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.
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]"
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.
Yep! For completeness, elaborate why exactly it's impossible to have excatly the edge counts 0, 1, ..., n − 1.
The minimum number of knights required to put on an 8x8 chessboard such that they attack every vacant square is 32. Here's one possible arrangement that achieves this:
mathematica
N . N . N . N
. N . N . N .
N . N . N . N
. N . N . N .
N . N . N . N
. N . N . N .
N . N . N . N
. N . N . N .
In this arrangement, the knights are placed on every other square of the board, such that they attack all the remaining squares. It's important to note that the knights only attack squares that are not occupied by other knights, so we can't simply place 64 knights on the board to cover every square.
Also, this is the minimum number of knights required to cover all the vacant squares on the board, but it doesn't necessarily mean that it's the only solution. There may be other valid arrangements that achieve the same result.
I've been getting into Nikoli-style logic puzzles recently, solving a few when I have the time, but I also went ahead and created some of my own puzzles. They're nothing too fancy, but I'm pretty happy with them for a first attempt. They use a ruleset which combines Simple Loops (https://www.fancade.com/wiki/Games/Simple%20Loop.md/c0ac7fb487e9f030f34f126602828d655379fa56) with Nonograms (https://en.wikipedia.org/wiki/Nonogram). I dub it, the Nonoloop.Next I might try the loop puzzles and nonograms and other puzzles but idk if drawing and images is possible with this version I'm using.