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.
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.
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:
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.
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:
You're buying digits.
On to Clam's 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?
You ask the waiter to take it away, but nowhere is it said that he actually does. So it is possible that the coffee remains on the table, and the waiter brings just another cup, and 'it' in the last sentence refers to the coffee on the table. Then it obviously is the same.
4. can also be solved if there happens to be a cupcake baking device in the basket.
5. The forest is a subset of the sphere. For each point in the forest, take the supremum of the radii of balls around that point that are still completely in the set. Now take the supremum S over the radii. For any epsilon > 0, you can walk S - epsilon into the forest.
6. As black sheep absorb more sunlight than white sheep, they naturally gain more energy from the sunlight, thus requiring them to gain less enery from eating grass.
Simon doesn't want to post the infinite hats problem yet (and instead posted the boring 5^3 puzzle), so I'm gonna post 3 hard but elegant algorithmic puzzles here (sorry, but here you really need at least a bit of knowledge about complexity theory), so Simon can get a clear conscience that he's not posting too many puzzles while solving too few himself.
#C1: You got a
mobile that is essentially arranged like a binary tree, i.e. each node has either two children nodes (in the mobile, this would be like a bar with submobile on each of its ends), or is itself a leaf with a positive integer weight. Now the mobile is not in equilibrium however, that is there is some submobile (subtree), where the weights of the left and the right submobile differ. The task is to design an algorithm that finds out
how many of the weights you have to change at minimum (to an arbitrary, possibly non-integer weight) so that the mobile gets into equlibrium. Run time complexity: O(N log N), where N is e.g. the number of leaves.
#C2: You're given a subset of the decimal digits {0, 1, ..., 9} and a positive integer N, and you're to find out whether there is a positive multiple of N that only consist of these digits when written in decimal, and if there is, the smallest of these multiples. Run time complexity: O(N)
#C3: (This is more of an algebra problem) You're give a polynom of degree N with coefficients being integers (integers isn't really necessary here, but for computational purposes their are convenient). Your task is to find out whether it has root of degree greater than 1 in the complex numbers, i.e. a linear factor that appears at least twice. Run time complexity: O(N^2) I think
EDIT: Decided to add #C4:
Consider the following exercise, found in a generic linear algebra textbook.
Let A be an n × n matrix. Prove that the following statements are equivalent:
- (a) A is invertible.
- (b) Ax = b has exactly one solution for every n × 1 matrix b.
- (c) Ax = b is consistent for every n × 1 matrix b.
- (d) Ax = 0 has only the trivial solution x = 0.
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:
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.