Prime

Poor Questioners. They cannot speak anything but questions and then only those for which they already know the answers. How do they exchange any information at all?

Nice economical notation. For the sake of completness, the following is the enumeration for the 2nd weighing:

I have enjoyed this problem. It looks like something original in the old family of weighting problems. The solution I found seems to be the only solution. I am curious as to how this problem was constructed.

Interesting point, actual present knowledge as opposed to infallible prediction of which one of the indefinite choices the future actually holds. The latter gives rise to a whole different universe, where knights and knaves receive some feedback from future allowing them to avoid statements, which are against their nature. For the sake of simplicity, I say, knights and knaves base their statements on that present personal knowledge, which is 100% correct. Spies can say anything. So Bob cannot base his statements on what we know Eric have said later. Same for Alec and Dave. Eric, on the other hand, spoke last and heard what others said about him. He is too proud to point fingers, but he cries in righteous indignation: "The spy has already lied twice!" (So true.) And then, as he is being put in shackles and hauled away, in desperation: "I am not a spy, but neither is Alec." Even at the time of personal trouble noble albeit simpleminded Eric defends his knave friend, who betrayed him. In my opinion, quite simply, if p then q means there is a correlation between p and q, which necessarily makes q true if p is. There is no discernable correlation in any of the "if-then" statements presented in the problem, so they are all false statements. Mind, all accused knew each others' identities and did not have to listen to others' statements to deduce who is who. Even the "if-then" statement made by David, assuming he was making an observation on the utterances presented thus far, falls short of identifying any valid deducible underlying correlation. Knaves are limited in what they can say, but that does not mean they are unintelligent. In this case the liars and a spy knew of this court's rule of treating every if-then construct as a material conditional. And they took full advantage of this limitation and cleverly constructed their statements in a way to implicate Eric, the only knight amongst them. I am aware of the convention of using material conditional in truth teller-liar puzzles. However, I don't see any sufficient justification for that. Is it because conventional if-then construct could be undeterminable? Whereas, making undeterminable statements is against knight/knave nature. On the other hand, adopting material conditional rule opens the door for all kind of nonsensical statements, which now must be deemed true. For example, "If wind is clever, then beer is loud." Or, would that be undeterminable even for material conditional? I guess, my point is, one cannot eliminate undeterminable statements (as Gödel had proved.) So what's the point of adopting strange counterintuitive rules for interpreting statements? Why replace conventional meaning of if-then construct with something that deems true many a kind of meaningless and useless utterances? Change the rule, and another Universe opens up, where it is clear that Eric is a knight and where it is equally possible to deduce who really is a spy. The Defense rests.

Fascinating notion. Placing David at a metalevel from where he controls us all. Be as it may, we must stay within the confines defined for us. Otherwise, problems become unsolvable.

I still prefer my original solution: And I think it's telling that Eric, the only honest person surrounded by knaves and spies, was wrongfully convicted of spying and dragged off to toil in the uranium mines.

Another deduction taking full advantage of the wonderful statements that Carl made.

Not at all. By that logic, given that y=2 does not mean that x=4 is true (or not true.) I have not confused anything. I merely suggested using conventional language "if-then" construct, rather than material conditional. However, if you have it on some authority that we must use material conditional for this sort of problems and will not consider the shortcomings of this method, or the alternatives; we still should note that the problem in the OP has not been solved here. Saying that this one is a spy and those are knights and those are knaves because "it makes everything consistent" is not a solution. By the same logic, if you brought just one man to the court and he said "I'm not a spy," this panel of judges would convict that man because his statement is consistent with what a spy could tell. The OP allows for 80 possible arrangements of knight-knave-spy among 5 people. Having found one that is consistent we must show that there are no other consistent arrangements among the remaining 79.

So if I say "If Tuesday then election day" is that a good (true) condition? It happens sometimes. Conversely, if it is not Tuesday how does that make it a "true" condition (implication)? I see "if p then q" as "p implies q." If p is true and q is true, but it did not have to be that way, just so happened, then p implies q is still false. We have convicted the wrong man.

Actually, what I derived for the question (2) was a short recursive form of that series where each next member is derived from its two predecessors. As for the problem with a full deck of cards, it seems out of grasp for the time being.

Thanks, witzar. So Montmort and Bernoulli had beat me to it by 300 years! Although the reasoning given in the Wikipedia "Counting derangements" paragraph in the point (2) is not all that clear. I can see what they meant, but I would expand on that explanation. Note the formula has a Fibonacci-like quality.

I did solve question (2) a little while ago, and I didn't see the problem as all that trivial. I got a short function S(N) for the number of arrangements of N objects so that each of them is not in its original position. Then the probability would be S(N)/N! naturally. My question is: is it a known problem? Has a solution been published before? The problem is so simply stated: "How many arrangements of an ordered set of N objects, so that none is in its original spot are there?" My way of solving it took a little bit of lateral thinking in addition to strightforward algebra.

I stand by my calculations. I said the second hand catches up to the hour hand at the rate of 3595 steps per hour. That already takes into the account the movement of the hour hand. The second hand moves at the speed of 3600 steps (minute divisions) per hour, the hour hand moves at the speed of 5 steps per hour. 3600-5=3595 is their relative speed. So if the second and the hour hands are 60//11 steps apart, it would take exactly 60/11/3595 hours for the second hand to catch up. I also used relative speed of the minute to the hour hand when calculating how far the minute hand would run away in that time.

The method for calculating the number of possibilities is straightforward. 1. Arrange the positions to be filled in any order you like. For example: President, Treasurer, Secretary. 2. For each position see in how many ways you can fill it with the remaining people. 3. Multiply all the numbers thus obtained.

That looks like the right answer, one of them, anyway. (They come in pairs because of the symmetry.) Although the actual calculations are still a bit off. For the sake of completeness here is the entire solution.

Technically, if we adhere strictly to the statement of the problem -- the answer is 1. But that's the first answer that comes to mind. Typically, a puzzle of the type takes into account the additional rotation of one circle around another.

12 o’clock is the only time when all three hands on the clock coincide exactly. (As already has been established by similar problem(s) on the BrainDen.) I estimate, in a 12-hour period, any two hands on a clock coincide approximately 1438 times. (Did I get that right?) Other than 12 o’clock, at what time(s) does the smallest angle between one of the clock’s hands and the other two that have coincided occur? Assume the clock hands motion is continuous, smooth and even.

There is two coin puzzle here, which seems very similar. To find a puzzle, which has not been posted here yet is a puzzle in itself.

The 12 balls puzzle has been there all along. And we gave this puzzle quite a work over in my Ultimate weighing problem. The power of 3 rule does not work on the first weighing when one of the balls has unknown fault. (Try 4 balls, one with unknown fault in 2 weighings, for a simple case.) Balance beam can potentially cut the number of variations to 1/3, provided we can arrange the balls so. With known fault we just toss 1/3 of all balls into one pan, 1/3 -- into another, and leave 1/3 on the side. Where we have unknown fault, for x balls we have 2x variations. On the first weighing we must use equal number of unknown balls in each pan of the balance. So if we use w balls in each pan and leave s on the side (2w+s=total balls; 4w+2s=total variations), the two distinct outcomes are: 1) The 2w balls on the balance weigh different. Then we have excluded 2w + 2s variations, leaving 4w+2s-2w-2s=2w variations. 2) The 2w balls balance. Then we have excluded 4w variations, leaving 4w+2s-4w=2s variations. In the case of 13 balls, the largest number of balls we could put on the balance is 8. (10 could leave 10 variations for the remaining 2 weighings.) That would leave 5 balls of unknown fault on the side with possibility of leaving 10 variations for the remaining 2 weighings. On consecutive weighings, the constraint of having even number of unknown balls on the balance is removed. That is because at that point we have some "good" reference balls, which we could throw on the balance to even number of balls in two pans.

This riddle has already been given a full treatment here. You can find one different ball out of 13 in 3 weighings. But I don't see how you can always determine whether it is heavier or lighter. Here is the variation, which does not allow that:

Having googled the “Nim game theory”, I came across a paper that proves the XOR formula. For our version of the game, you need to read just the first 12 pages. The actual proof is presented on pages 10 - 11, which one cannot understand, unless they paid due attention to the preceding definitions and lemmas. (It is especially important to understand the concept of equivalency.) So it takes a bit of effort to get through. But the proof by induction looks solid. Still it kind of pulls the powers of 2 out of the sleeve. There are some things in that paper that I can translate into non-mathematical terms, and which may be helpful for deriving the XOR strategy for this game without going into all that formal math.

Thanks, Bonanova. I knew, there must have been a description/mathematical treatment of that game somewhere. However, I don’t see a proof in the article in the Wikipedia you referred to, let alone the derivation of the formula. The article simply states, “The theorem follows by induction on the length of the game from these two lemmata.” Then it shows two lemmas, similar to those in EH’s proof. Basically, they boil down to: 1. You cannot obtain one losing position from another with a single move. 2. You can always create a losing position (for your opponent) with a single move from a non-losing position. We have evidence that some losing positions conform to zero-XOR formula. But, where is that induction showing that all losing positions must? It is like saying: 1. The winning strategy must have those two properties: A and B. 2. XOR formula conforms to those two A and B properties. 3. We know of some positions that conform to XOR formula. 4. Therefore, XOR must be it. I disagree with the conclusion (4). The only conclusion that we can draw here is: XOR could be it. But that’s not a proof. Furthermore, the article (inadvertently) gives an example that the purported proof is not really a proof. That example is the misere variation of the game (the same one I gave in the OP, where whoever takes the last coin -- loses). In that variation, the winning strategy conforms to the XOR formula to a certain point in the game, then it stops conforming to that formula and switches to another formula altogether. That would break the induction, wouldn’t it? I say, it is a commonplace occurrence with those types of proofs where you put the carriage before the horse. First, let’s introduce the winning formula out of nowhere, then let’s prove that it is. The derivation of the formula is not shown in the article, and, therefore, the understanding of it is missing. I, suppose, if I check the references further (now that I know the proper name of that game), I may find a real proof/derivation I am looking for. From my own derivation of the formula twenty some years ago, I vaguely recall tables filled with numbers, some kind of rotational symmetry in those tables, and interrelations between numbers of rows and numbers of coins in them.

See any flaws/holes? The lemmas are fine. But where is the proof that the losing positions must be those that XOR to zero? I recall, back when I found the winning strategy for a general case, I described it in terms of powers of 2 somehow. Then I took a second look and noticed, it was XOR.