From Air Canada’s inflight magazine:
And since I’m sure someone will ask, here is, apparently, the only solution they could think of:
(This puzzle brought to you by the same thoughtful folks who bring you Air Canada’s customer service.)
They managed to get four left hand turns in there — when not even one was required. Absolutely stunning.
A more fun one I heard abit ago.
There are 13 coins of interger weight. They have the property that if I remove any one of the 13 coins the remaining 12 coins can be partitioned into 2 groups (A and B) of 6 coins in a way that the 2 groups of size 6 have equal total weight. Of course A and B depend on which coin I remove.
Claim: This forces all 13 coins to have the same weight.
Proof or counterexample.
Bonus: Let the coins have real valued weights.
That is indeed the worst puzzle ever. A simple idea that could make it acceptable: What is the *longest* route (assuming you can only be at each location once, except at )?
@Jonathan, not an answer, but some thoughts:
1. If the sum of all thirteen weights is odd, then a solution must have all odd weights. Otherwise, we could select an even weight, and this would prevent balancing.
2. If the sum of all thirteen weights is even, then a solution must have all even weights. Otherwise, we could take out an odd weight, leaving an imbalance.
3. A solution with all even weights must be reducable to all odd weights, because dividing each weight by a common power of two would require that the result be all odd weights or else would be one of the unsolvable #1 or #2 solutions.
Thus, any solution would have to have all odd weights.
I should add that a solution would either be all odd weights, or reduceable to all odd weights.
Clearly whoever designed this doesn’t know what a puzzle is.
All the weights are the same. Proof: By the Bad Puzzle Theorem. It’s a bad puzzle unless the weights are all the same, because the solution with that many weights would look arbitrary, and JK posted it as a good puzzle.
My gut says that that the proof is going to show that a solution must satisfy two condiditions that are mutually contradictory except when all weights are the same.
Did you know that you get the same answer by going around the perimeter?
@Al V: My gut tells me 13 equations in 13 unknowns. But there must be some degeneracy since all multiples of the ‘reduced’ all odd solution must also work. So 13 in 13 won’t prove uniqueness. If we look at the case n = 3 it is easy to see the number must all be the same. Beyond that I appeal to the Good Puzzle Theorem :>
I have a solution to your puzzle (though it took me a while!). I’m hesitant to post it, since others seem to be having fun with it. I’ll therefore send you email.
@Steve: That works :-). The bonus (real valued weights) is also fun.
I’ll post the solution to that one tomorrow unless it gets posted before.
I think I have a proof. All numbers must be equal.
If we have a solution, 13 integers, then we have a solution where we replace x by x-1 for all x in the set. Hence for any solution we can produce another solution with 0 in the set. Thus the problem reduces to solving it with n = 12. Again we reduce etc until we reach n =3. For n = 3 all the numbers must be equal.
This suffices because you can select which 3 numbers in the first solution you want to “keep” as you reduce.
Seems to work for reals too.
Ignoring the fact that #3 is missing, does “in succession” not mean that you are supposed to go to the three destinations in numerical order? Which their “solution” does not do.
@Jonatan, There’s a pretty simple route that requires driving 36 blocks and passes through every intersection exactly once. Even that is a pretty lame puzzle, although admittedly better than the original.
I love how the solution to your original puzzle uses a different type of path between each pickup point. I have to assume some Eureka! moment happened there, but the puzzle went to publication anyway.
I thought the number on the right was a “5″, but I guess it is just a “3″ in an excessively ornate font. Never mind my previous comment.
Why is the following sentence true:
Thus the problem reduces to solving it with n = 12.
I see the integers. Just take a lexicographic minimal example.
You see, that you can make it smaller.
@JK’s puzzle :
Let V be a vector space over Q, spanned by the weights of the coins. Let B be a basis for V. Solving the original puzzle is equivalent to solving the puzzle for the projection of the weights onto each of the basis vectors. Hence, solving the puzzle for coins with real or complex weights is equivalent to solving the puzzle for coins with rational weights.
Let all the coins have rational weight. Multiplying the weights of all the coins by a common multiple of the denominators of the weights gives an equivalent puzzle, with integer weights. Hence, solving the puzzle for coins with integer weights is equivalent to solving the puzzle for coins with real or complex weights, or weights that are rational functions or elements of any vector space over Q
Let w be the smallest weight. Subtracting w from each weight leads to an equivalent puzzle, so solving the puzzle for coins integral weights, the lightest of which is weightless, is equivalent to solving the original puzzle, or solving the puzzle for coins whose weights are real, or twice-differentiable functions, or elements of any vector space over Q.
@AlV has already shown that if any coin has odd weight, all coins do, and that if any coin has weight divisible by 2^n, all do. Since 0 is divisible by 2^n for all n, all the coins must have weights that are divisible by 2^n for all n. Therefore, all weights are 0.
For this original puzzle, it means all coins have the same weight. For the extension, it means all coins are the same linear combination over Q of the elements of B.
QED. Thanks for the puzzle! I had to sleep on it and see AlV’s thinking to crack it ;-)
@Mike H: Yup that was the solution I had in mind.
@ Al V: You didn’t have to think for a while to convince yourself that this was indeed the longest route? I did anyway.
Could you elaborate a bit more on your answer?
First you say, that all the possible solutions form a vectorspace, which you call V. ok. Why do you think it has a basis, with rational coefficients?
So for instance consider the vectorspace formed by al the vectors, which are orthogonal to (1, sqrt(2)). It does not have a rational base.
Maybe i misunderstand something.
@Jonatan, I don’t have a proof that 36 blocks is the longest possible route. It was just the longest I could come up with, and it’s hard to envision a longer one. Perhaps that’s another problem to be solved.
“Imagine you’re driving a taxicab in Gridlock City. Your cab is called to visit three places in succession, and then return to the garage. What is the length of the longest route that accomplishes this, without passing through any intersection more than once, except for 1?”
The problem is almost the same as yours, except that it doesn’t ask for the actual solution. I can come up with 3 different routes of length 36, so there are probably more. I wonder how many? Certainly less than the original Air Canada problem, which must have hundreds of solutions.
Possible answers to Worst Puzzle Ever:
1. “Can you find the shortest route that will accomplish this task?” There are various answers, but none of them shorter than all others. With this understanding of the puzzle, the unique, correct answer is “no.”
2. Don’t be a chump. Sure, the puzzle refers to “Gridlock City,” but it never specifies that you have to move along a grid line. (Read the French text; it doesn’t even refer to “Gridlock City.”) So the shortest route would be to drive a straight line from Point 2 to Point 3 to Point 4 to Point 1. (For what it’s worth, the puzzle also does not specify that you start at Post 1).
3. Stop being so Euclidian! The shortest route would depend upon an earthquake/sinkhole at the center square, having the effect of drawing the four blue dots together. This arrangement would tend to depress receipts for the cab driver; it wouldn’t be any treat for the rest of the city, either.
If this puzzle is the worst thing that you experienced in your flight, Landsburg, you’re a lucky man indeed. Welcome back.
In my opinion there is no need for this change. The answer is just as simple as the answer to mine anyway. (Eg drawing a route vs writing the number 36.) If it should be changed, I guess it could say “Prove (or convince me) that you cannot find a longer route”, but I would assume this is implied.
Powered by WordPress3.3.2 and K21.0-RC7
Entries Feed and Comments Feed
43 queries. 0.9140 seconds.