Hyperboreans belong to three groups: Sororeans, Nororeans, and Midroreans. Of the three inhabitants who make the statements below, little is known as to their group or groups except that Outliers are not present.
B and I are both Midroreans.
C is a Nororean.
A and I belong to two different groups.
C and I belong to the same group.
I am not a Nororean.
A and I belong to the same group.
To what group or groups do A, B, and C belong?
(Source: Challenging False Logic Puzzles by Norman D. Willis)
To start with, at least, I like to take the first person at their first word in these sorts of puzzles. A has claimed to be a Midrorean. This means either that A1 is true and A2 false, or that A1 is false and A2 true. Consider the first possibility. It means that B is a Midrorean. B's only possibility as a Midrorean then is constrained to B1 being false and B2 being true, which means that C is also a Midrorean. If C is a Midrorean then his only possibility are is C1 being true and C2 being false. However C2 is not false under the other assumptions and so the other possibility for A to be a Midrorean has to be considered.
If A1 is false and A2 is true then B isn't a Midrorean, which isn't too helpful because two possibilities remains for him. What is more helpful is that this then entails that C is a Nororean. If C is a Nororean, then C1 is false, which checks out, and that C2 is false, which also checks out. So far, it looks like the belief that A is a Midrorean can be preserved with the implication that C is a Nororean.
But not so fast. This leaves B. B can't be a Sororean, because C2 is false under this assumption. Nor can he be a Nororean because C1 is true under this assumption. All that remains is for B to be a Midrorean. In such case, because B1 is false, B2 must be true. But it is in fact false with this assumption. This requires revision of the belief that C is a Nororean and, indeed, of the belief that led to it, that A is a Midrorean at all. Disappointing, but it doesn't leave us quite at square one, because that latter possibility is now ruled out entirely.
What other possibility remains for A? Sororean is not in the cards; a Sororean would not identify as anything other than a Sororean. All that leaves is Nororean, and now we can be certain, although there are unfortunately no unique implications from the falsity of A1 and A2.
That being said, A being a Nororean does mean, due to the falsity of A2, that C is either a Sororean or a Midrorean. Entertain the first option in the spirit of charity. C2 is false under this assumption. So much for charity. This then means that C is a Midrorean, with C1 as the true statement and C2 as the false one. We can now be certain that A is a Nororean and C is a Midrorean. These aren't defeasible inferences anymore.
That leaves B. Being a Sororean is still ruled out because of B2. What about being a Midrorean? B1 must then be true, and B2 false, but this is not the case. All that remains is for B to be a Nororean.
Final answer: A is a Nororean, B is a Nororean, and C is a Midrorean.
Now for something a little bit different than knights and knaves:
According to the ancient Greeks, Hyperborea was a land to the north of Mount Olympus, home of the gods. The inhabitants were favored by the gods; they lived for a thousand years in a land of perpetual springtime, and they were free from pestilence.
Little known were the Hyperboreans' unique standards of veracity. Those who lived in the southern region of the land were known as Sororeans and they always spoke truthfully; those who lived in the northern region were known as Nororeans and they always spoke falsely; those who lived in the middle region were known as Midroreans and they made statements that were alternately truthful and false, but in which order was unknown.
There were a few rebels, called Outliers, who disdained the normal conventions of Hyperborea and refused to adhere to the accepted standards of veracity. Their statement patterns as to truth and falsehood were anything that was different from other inhabitants (that is, if three or more statements were made, there were some true statements and some false statements, but not in an alternating pattern).
(Source: Challenging False Logic Puzzles by Norman D. Willis)
For clarification, Midroreans can produce patterns like false, true or true, false when saying two things, or alternatively false, true, false or true, false, true when saying three things etc. (This is of course of little use if the putative Midrorian said only one thing.)
Outliers are even more confounding. Outliers who say one or two things can have any assignment of truth values to their statements imaginable. Consequently, they should be the last choice possible for making conjectures about who is who when they come into play.
There are two puzzles in this appearance. I didn't get the first one, but the second came readily, almost as soon as Smullyan was done posing it.
Consider a convention with one hundred politicians. Of them, at least one is honest and at least one is crooked. Of any random sample of two of them, at least one is crooked. How many of them are honest, and how many crooked?
The answer is that one is honest and the remainder are all crooked. Any higher number of honest politicians at the convention would permit a random pair without a single crooked one. Any lower number would be ruled out by the criteria stated in the problem.
Hostile members of the Uti, Grundi and Yomi groups were travelling to a conference. There were two members from each group, one finned and one feathered. The finned Keplerian was much stronger, and had to protect her feathered friend. Never could a feathered Keplerian be left alone with a finned Keplerian of another group. The only time a feathered Keplerian was safe with the finned Keplerian of another group was when the feathered Keplerian of that enemy group was also present.
The trip was quiet until they came to a deep ravine. The only way to cross it was by swinging across on a rope. But the rope was only strong enough to hold two of them. And it wasn't heavy enough for them to swing it back over the ravine without someone to weigh it down. How did they all cross the ravine?
(Source: Fantastic Book of Logic Puzzles by Muriel Mandell, illustrated by Elise Chanowitz)
This one was actually quite easy and can be solved in a very methodical fashion. I don't know why it was made last of the group.
First bring both Uti over to the far side. Then come back with the finned Uti. The finned Uti will then return to the far side with the feathered Grundi. Once there ... they? ... can't antagonize the feathered Grundi because of the presence of the feathered Uti. Then come back with the Uti and bring the stronger finned Grundi over. Here the Grundi can't antagonize the feathered Uti because the feathered Grundi is there, so the finned Uti can leave for the near side once more. Then bring the feathered Yomi over to the far side with the finned Uti and return. Lastly bring the finned Yomi over with the finned Uti. That solves this puzzle.
Harassed during important experiments, three Earthlings were taking three law-breaking Grundi to the authorities. Suddenly they heard the thunderous roar of a rockfall, and they knew they were facing sure death unless they crossed to the other side of the canal. The portable watercraft they carried with them would hold only two passengers, regardless of weight. At no time could there be more Grundi on either side of the water than Earthlings or the Grundi would overpower the Earthlings. How could they all cross the water safely?
(Source: Fantastic Book of Logic Puzzles by Muriel Mandell, illustrated by Elise Chanowitz)
The secret to solving this one is the somewhat baffling condition that any number of Grundi can be on one side of the canal without chaperoning; they will not get away.
To begin with, sending only Grundi will not get anywhere and sending only Earthlings is not permissible. So send one Earthling and a Grundi to the far side. From there, the only way to make progress is sending one Earthling back. From there, send both Grundi on the near side over, but send one back. Then send both Earthlings to the far side, because there are two Grundi there and only one Earthling would get overpowered. Then send one Earthling and one Grundi to the near side. Lastly, send both Earthlings to the far side. This will result in two Grundis on the near side with one Grundi and all three Earthlings on the far side. Then send one Grundi back to the near side, and then bring two to the far side. Lastly, it is possible to send one Earthling over to the near side to bring the remaining Grundi over to the far side.
In keeping with the previous entry, the following has been edited for Kepler-186f and the likely gravity of the same has been factored in.
Two Keplerians and two Earthlings traveling together came to a canal. As a result of the gravity on Kepler, the Earthlings each weighed 200 pounds and the Keplerians 100 pounds. The watercraft would hold no more than 200 pounds. How did they all cross the canal?
(Source: Fantastic Book of Logic Puzzles by Muriel Mandell, illustrated by Elise Chanowitz)
This one requires more steps than the former but isn't too hard.
To begin with, sending over an Earthling is a non-starter because it will just mean coming back. So is sending just one Keplerian, for much the same reason. They both have to go over. In the next step, sending both Keplerians back is just ending up where you started, so send one back. The boat will then be able to carry an Earthling over to the far side. At this point, there is a Keplerian and an Earthling on either side of the canal. Sending an Earthling back will get nowhere, so send back a Keplerian. Now, both Keplerians and an Earthling are on the near side. Sending the Earthling back will not achieve anything, but it was useful for both Keplerians to be on the far side earlier, so send them to the far side once more. After the previous move, now only one Earthling is on the near side. Send back the boat with only one Keplerian, then let the Earthling cross. Finally, both Earthlings are on the far side. Send the far side Keplerian back to the near side and bring the both of them back over. This completes the crossing.
The following is a classic altered, then updated by me. The original mentioned multicellular "Martian" life. Since it is unlikely that there is much of anything beyond bacteria analogues on Mars, and maybe not even that, I have used the very possibly habitable Kepler-186f instead:
Jonathan Mark gathered three specimens of Keplerian plant and animal life to bring back to Earth: a garble, a farfel and a tsientsien. But Mark was worried. His vehicle for local travel was not big enough to hold more than himself and one specimen. Mark knew that garbles will eat farfels if given half a chance, and farfels will eat tsientsien. Garbles, however, don't eat tsientsien, and tsientsien don't eat. All the other astronauts were away from the ship. How could Mark transport the garble, the farfel and the tsientsien one at a time so that they would all be safe?
(Source: Fantastic Book of Logic Puzzles by Muriel Mandell, illustrated by Elise Chanowitz)
If this sounds familiar, maybe it should. My earliest memory of the same is one with a wolf, a goat and a cabbage. These things go back a long time. Here it looks like some oddly named secondary consumer will eat a primary consumer, if left alone with it, but not a primary producer. The primary consumer will however eat the primary producer if the two are left alone. (Remember, the latter likely has no voice. Or, maybe? It's the Kepler-186 system after all.) Anyway, how to get these creatures over the river?
The first step is to realize that there is only one first step: taking the farfel over to the far bank of the river, leaving behind a dangerous secondary consumer but with something he or she or whatever pronoun fits would not want to eat anyhow.
Now, with the farfel on one side of the river, returning to the other side, there are the garble and the tsientsien. Taking the garble over would result in the garble and the farfel on the other side of the river alone in the next step, which is impermissible. The only choice is then to take over the tsientsien.
What this results in is the farfel and the tsientsien on the same side of the river, which is bad. However, the key to solving this problem is backtracking: bringing what was once brought to the far side back to the near side. Because the tsientsien was just brought over, it seems like doing this will just undo progress. So take the farfel back.
Now the garble and the farfel are on the near side. Also not good. But now the garble can be taken to the far side, where ... it? ... will not eat the tsientsien. Lastly a trip back to the near side and back again will bring the farfel over, placing all organisms on the far side.
It should be well-known that the webcomic XKCD usually isn't actually funny. But occasionally it can at least make you think. Here's one example:
And indeed this is a form of the knapsack problem. From the Wikipedia article on the same:
The knapsack problem or rucksack problem is a problem in combinatorial optimization:
Given a set of items, each with a weight and a value, determine the
number of each item to include in a collection so that the total weight
is less than or equal to a given limit and the total value is as large
as possible. It derives its name from the problem faced by someone who
is constrained by a fixed-size knapsack and must fill it with the most valuable items.
This is the sort of problem for which exact answers cannot generally be found in a reasonable amount of time (although this may be possible for smaller instances). There are numerous inexact ways to solve such a problem. One of them is so-called genetic algorithms. Again, from the Wikipedia article:
In other words, one creates a cruel, merciless struggle for dominance in the digital world and culls solutions that can't compete effectively, while letting those that can thrive and multiply, a very pleasant way of doing things, no doubt. (A less brutal approach to evolving solutions to problems is particle swarm optimization, in which no one ever dies. However, I have not used it because, in its basic form, it is not as well-suited to combinatorial problems as are GAs.)
How did it do? Here are some solutions offered by the process:
3x mixed fruit, 1x French fries, 1x sampler plate; total price: $15.00
1x side salad, 2x sampler plate; total price: $14.95
1x mixed fruit, 2x hot wings, 1x sampler plate; total price: $15.05
3x French fries, 2x side salad; total price: $14.95
2x mixed fruit, 3x hot wings; total price: $14.95
All told, the outcomes were very good, falling within at worst 10¢ of the goal. Not bad at all for a process built on blind chance. One even managed to be perfect. But the caveat with any evolutionary process is that there is simply no guarantee an optimum will ever be attained, even despite very fierce competition. (This is something neoclassical economists should pay more attention to, in my opinion.)
But how about something a little more difficult? I don't know exactly how many appetizer orders under the limit of $15.05 are possible. There might be a way of doing this with dynamic programming or something that isn't immediately obvious to me. But given that, at most, six of the cheapest item can be bought, an easy upper bound for the number of possible orders is \(7^6\), that is to say, the possibility of ordering anywhere from zero to six inclusive of each appetizer, raised to six, the number of appetizers on the list. This number is about 118,000, and is also the same number that the genetic algorithm described above can, in principle, entertain—though it will quickly reject many of these possibilities. The number is "only" on the order of about 100,000. What about a bigger search space? One John Burkhardt, formerly of Florida State University, has uploaded a number of datasets fit for use in various computational problems, among them, a few for the binary knapsack problem, where it is not possible to include a number of each item limited only by the maximum spending limit. In this case, an item is either included or it is not. But due to the power of exponentiation, such problems can have very large search spaces. Since we're doing well today, let's consider the last item on the list, which has 24 items. The search space in this case contains \(2^{24}\), or well over 16 million possible candidates. The candidate solutions will have to be lists of Boolean values in this case, with operators appropriate to their kind. With that said, here's how it goes:
importjsonimportrandomimportnumpyasnpfromdeapimport algorithms
fromdeapimport base
fromdeapimport creator
fromdeapimport tools
classEvaluator(object):
def__init__(self, items, capacity):
self.items = items
self.capacity = capacity
def__call__(self, candidate):
total_weight =0
total_profit =0for i inxrange(len(candidate)):
if candidate[i]:
total_weight +=self.items[i]['weight']
total_profit +=self.items[i]['profit']
if total_weight >self.capacity:
overload = total_weight -self.capacity
else:
overload =0return (overload, total_profit)
withopen('items.json') as f:
items = json.load(f)
withopen('capacity.json') as f:
capacity = json.load(f)
evaluator = Evaluator(items, capacity)
# Objectives are decreasing overload and increasing total profit, in that order
creator.create('FitnessMulti', base.Fitness, weights=(-1, 1))
creator.create('Individual', list, fitness=creator.FitnessMulti)
toolbox = base.Toolbox()
toolbox.register('random_bit', lambda: random.choice([False, True]))
toolbox.register('individual',
tools.initRepeat,
creator.Individual,
toolbox.random_bit,
n =len(items))
toolbox.register('population', tools.initRepeat, list, toolbox.individual)
toolbox.register('evaluate', evaluator)
toolbox.register('mate', tools.cxTwoPoint)
toolbox.register('mutate', tools.mutFlipBit, indpb=0.05)
toolbox.register('select', tools.selNSGA2)
# random.seed(42)
NGEN =500
CXPB =0.5
MUTPB =0.2
pop = toolbox.population(n=100)
hof = tools.ParetoFront()
pop, log = algorithms.eaSimple(pop, toolbox,
CXPB,
MUTPB,
NGEN,
halloffame=hof,
verbose=True)
total_profit =0
total_weight =0
best_solution = hof[0]
print'Items selected:'for i inxrange(len(best_solution)):
if best_solution[i]:
print i +1
total_profit += items[i]['profit']
total_weight += items[i]['weight']
printprint'Total weight: %d'% total_weight
print'Capacity: %d'% capacity
print'Total profit: %d'% total_profit
Again, the source files, slightly different to reflect the terminology of the problem description:
Items selected: 1, 2, 4, 5, 7, 10, 11, 13, 16, 22, 23, 24; total weight: 6,392,842; total profit: 13,521,334
The FSU page which this problem came from says that the maximum capacity is 6,404,180. All candidate solutions fall under this limit. Additionally, it says that the total profit of the optimal solution is 13,549,094. This means that the best candidates found on these five runs are all at least ~99.36% of this optimum at the very worst. The best of them is nearly 99.82% optimal.
For some difficult computational problems, evolutionary approaches are clearly very capable. For your patience in getting through all of this, here is an even more vivid demonstration of what they can do:
If you have a piece of paper that is 0.1 mm thick, then how many times will you have to fold it in half in order for it to become tall enough to reach the moon?
Note: The distance from the Earth to the Moon is 384,400 km.
Imagine being able to put a perfect crease in that paper, which is assumed by this problem, although not feasible in practice. Once it is folded in half, it will be 0.2 mm thick. Then, when that piece of paper is folded in half, it will be 0.4 mm thick, and so it goes. Converting the distance in kilometers to millimeters, the question comes down to finding \(n\) in:
\[ 0.1 \times 2^n \ge 3.844 \times 10^{11} \]
In other words, to what power does two have to be raised in order to reach (at least) the Moon from Earth when multiplied by 0.1 mm? Solving:
The right-hand result is approximately 41.81. First integer solution above this is 42. Nice reference (or at least nice coincidence), but don't panic about forgetting your towel just yet, because, as said, real paper can't be used to make a space elevator like this. (Here's why.)
\begin{align*}
m \times a \times t &= \frac{1}{8} \\
m \times a \times h &= 32 \\
m \times t \times h &= \frac{1}{3} \\
a \times t \times h &= 162
\end{align*}
This is a good one. I first attempted to do it by taking the log of both sides of the equations then doing Gaussian elimination with the resulting additive terms, then convert back at the end. After realizing this was neither going to be "quick" nor result in an exact answer likely wanted by the input form, I threw in the towel and looked at the solution. It really is incredibly simple. Just multiply all the equations together:
During the rebuilding after World War II, we were short of tractors. The machine and tractor stations would lend each other equipment as needed.
Three machine and tractor stations were neighbors. The first lent the second and third as many tractors as they each already had. A few months later, the second lent the first and third as many as they each had. Still later, the third lent the first and second as many as they each already had. Each station now had 24 tractors.
How many tractors did each station originally have?
(Source: The Moscow Puzzles: 359 Mathematical Recreations by Boris A. Kordemsky, edited by Martin Gardner)
Initially, I was confused by the wording. But what it really means is that, at each time step, the lender station doubles the number of tractors that each of the two lending stations had, and subtracts the total number of lent tractors from its own stock. Like the very first puzzle I ever solved here, this can be solved backwards easily.
At the final time step, all stations had 24 tractors. In the previous time step, the third lent the first and second as many as they each already had. What this means is that in the previous time step, the first and second stations both had 12 tractors, and the third lent 24 total to the others. The three stations then respectively had 12, 12, and 48. Repeating this process again for the previous time step: 6, 42, and 24, and for the earliest time step, giving the final answer: 39, 21, and 12.
Smith drove at a steady clip along the highway, his wife beside him. "Have you noticed," he said, "that those annoying signs for Flatz beer seem to be regularly spaced along the road? I wonder how far apart they are."
Mrs. Smith glanced at her wrist watch, then counted the number of Flatz beer signs they passed in one minute.
"What an odd coincidence!" exclaimed Smith. "When you multiply that number by ten, it exactly equals the speed of our car in miles per hour."
Assuming that the car's speed is constant, that the signs are equally spaced and that Mrs. Smith's minute began and ended with the car midway between two signs, how far is it between one sign and the next?
(Source: My Best Mathematical and Logic Puzzles by Martin Gardner)
I solved this a little bit differently from how it's solved in the back of the book. Consider the equation:
\[ 10s = \frac{d}{t} \]
Where \(s\) is the number of signs encountered, \(d\) is the distance traveled (in miles), and \(t\) is the time elapsed (in hours). The right-hand side of the equation is simply derived from the old:
\[ d = rt \]
Or, distance equal rate times time, that one learned in middle school, solved for \(r\) and placed in the right-hand side of the first equation. All told, the first equation just says: the number of signs times ten is equal to the speed in miles per hour.
It's also known that one minute has passed, or one-sixtieth of an hour in the terms used here. With this fact, more can be figured out:
Conceptually, \(s\) can only have integer solutions, which constrains \(d\), and thus the speed of the car, but not uniquely. As stated by Gardner in the back of the book, the exact speed doesn't matter. But let's say the Smiths are going at a brisk clip of 60 mph for convenience. \(d\) is then one; \(s\), six. This means that the signs are spaced one-sixth of a mile apart. The same can be figured out from any rational value of \(d\) that leaves \(s\) an integer. (I understand this might also be constrained further by special relativity but there are still many possible solutions even then.)
"Well, here is your butter, eggs, and milk all back," said the King, "and I see you have your jam, flour, sugar, salt, baking pan, and cookbook—even your pepper. Now you can surely make me the tarts!"
Well, the Queen made a marvelous batch of tarts. "These are even better than last time," said the Queen to herself. "I'm sure the King will be delighted!"
The Queen went up to the Royal Chamber to announce to the King that the tarts were ready. Arm in arm they went down together to the kitchen, but when they got there, they found the table empty—the whole platter of tarts was clean gone!
"Now this has gone too far!" cried the King, paling with rage. "Who sneaks into my house like this? I've half a mind to really execute the culprit!"
Well, needless to say, the culprit did not really get executed, but he was caught, and the tarts were fully recovered. That ends my story.
"What do you mean, that ends your story?" asked (the real) Alice excitedly. "You haven't told us who stole the tarts, nor whether there was a trial, and if there was, what happened at the trial—you haven't told us anything!"
"Well, there was a trial," I added, "but it was a very complicated one, and for you to figure out who was guilty involves solving a complicated logic puzzle, so I think I'll wait a few years until you're all grown up, and then I'll tell you what happened."
"No, we want to know what happened!" said Tony.
"I'll let you know what happened," I replied, "but in a few more years when you're all grown up."
"No, no, we want to know now!" they all shouted.
"All right," I replied, "but you won't blame me if I give you a very complicated logic puzzle?"
"We won't blame you—really we won't. Only stop keeping us in suspense—tell us what happened!"
So I continued—
Well, as I said, the trial was quite a complicated one. The first suspect was the Knave of Hearts, but circumstantial evidence was brought forth which established beyond any reasonable doubt that the Knave of Hearts couldn't have stolen the tarts. The next suspect was the Dormouse. However, several reliable witnesses testified that the Dormouse was fast asleep at the time of the robbery, hence it couldn't have been the Dormouse. At this point the trial came to a dead standstill.
Suddenly the door of the courtroom burst open, and the White Rabbit proudly entered, bearing the tray of tarts. Behind him came the soldiers, dragging in the Gryphon and the Mock Turtle in chains.
"The tarts were found on the beach," explained the White Rabbit. "The Gryphon and the Mock Turtle were just about to eat them when the soldiers happened to come by and put them in custody."
"That proves their guilt without any question of doubt," shouted the Queen, "so off with their heads immediately!"
"Now, now," said the King, "we must give them a fair trial, you know!"
Well, events happened which proved that the Gryphon and the Mock Turtle were not both guilty—the questions that remained were whether either one was guilty, and if so which one; or whether someone else was guilty: Was it a mere coincidence that the tarts were found by the Gryphon and the Mock Turtle? No; evidence was soon produced that conclusively proved that either the Gryphon or the Mock Turtle was guilty (but not both), but the court could see no way to decide which one it was. It seemed that no further progress could be made, but quite suddenly a whole medley of witnesses came up, making various statements.
"The Gryphon never stole the tarts," said the Duchess.
"But he has stolen other things in the past," said the Cook.
"The Mock Turtle has stolen things in the past," said the Cheshire Cat.
"The Cheshire Cat has stolen things in the past," said the Caterpillar.
"The Cook and the Cheshire Cat are both right," said the March Hare.
"The Cook and the Caterpillar are both right," said the Dormouse.
"Either the Cheshire Cat or the Caterpillar is right—and maybe both," said the Hatter.
"Either the March Hare or the Dormouse is right—and maybe both," said Bill the Lizard.
"The Cook and the Hatter are both right," said the Knave of Hearts.
"Bill the Lizard is right and the Knave of Hearts is wrong," said the White Rabbit.
There was a dead silence.
"All this proves nothing!" roared the King. "Just words, words, words—all useless words!"
"Not so useless, your Majesty," said Alice, rising from the jury. "It so happens that the White Rabbit and the Duchess made statements which are either both true or both false."
All eyes turned eagerly to Alice. Now, everyone knew that Alice makes only true statements, and subsequent investigation showed that this statement was no exception. Moreover, this statement solved the entire mystery.
Who stole the tarts?
(Source: Alice in Puzzle Land: A Carrollian Tale for Children Under Eighty by Raymond Mullyan)
This is the final challenge and there is quite a lot to unpack here. However, what Alice said is enough to unravel the entire thing: the statements of the White Rabbit and the Duchess are either both true or both false and so the implications of only two alternatives need to be worked out.
Consider the first alternative: that the White Rabbit and the Duchess both told the truth. What did the Duchess say? She said that the Gryphon didn't steal the tarts. What did the White Rabbit say? He said that Bill the Lizard is right and the Knave of Hearts is wrong. (I am going to assume that the amended statement the White Rabbit made about the simultaneous guilt of the Gryphon and the Mock Turtle is to be left out of this.)
Now we've reached the bottom with the Duchess, but there is a sort of recursion that needs to be done with the White Rabbit's statement. What did Bill the Lizard say? He said that "either the March Hare or the Dormouse is right—and maybe both" (inclusive or, in other words). What did the Knave of Hearts say? He said that the Cook and the Hatter are both right.
Here again, there is another layer of recursion. What did the March Hare say? He said that the Cook and the Cheshire Cat are both right. What did the Dormouse say? He said that the Cook and the Caterpillar are both right. What did the Hatter say? He said that the Cheshire Cat or (in the inclusive sense) the Caterpillar is right.
With the statements of the Cook, the Cheshire Cat and the Caterpillar, we have finally reached bottom. The Cook said the Gryphon has stolen in the past; the Cheshire Cat said that the Mock Turtle has stolen in the past; and, lastly, the Caterpillar said that the Cheshire Cat has stolen in the past. Reviewing all previous puzzles, the Gryphon and Mock Turtle were both exculpated the only time they were accused. The Cheshire Cat was accused in part VII, part IX, part X, but exculpated in every instance. So the statements of the Cook, the Cheshire Cat and the Caterpillar are all false.
Now, working backwards, the statements of the March Hare, the Dormouse and the Hatter are all false. At the next level up, the statements of Bill the Lizard and the Knave of Hearts are also false. (Seems like a pattern is emerging here.) And at the highest level, the statement of the White Rabbit is false, because its truth is contingent on the falsity of the statement of the Knave of Hearts, which he has, but also on the truth of the statement of Bill the Lizard, which he does not have.
So the statement of the White Rabbit is false. Remember that the very first assumption was that the statements of both the Duchess and the White Rabbit were true. This assumption has now been demonstrated false. Remember also that it was either this, or both of their statements being false, which we must now discard. The only remaining option, though it disappoints us in the two, is that neither the Duchess nor the White Rabbit told the truth. Accordingly, both statements are false, including the one the Duchess made in which she said the Gryphon was innocent of the crime. But it's awful hard to behead someone with the body of a lion who can just fly away, isn't it?
"Well, here is your cookbook back again," said the King, "so you now have the recipe. So make me the tarts!"
"Without milk, butter, or eggs?"
"Oh, me!" cried the King. "This is too much!"
"And this time I know it was the March Hare, the Mad Hatter, and the Dormouse," shouted the Queen, stamping her feet in rage. "I actually saw them sneaking out of the window when I came into the kitchen. Each was carrying something, but I couldn't tell who was carrying what."
"We'll soon settle that!" roared the King.
Well, the ingredients were all found at the house of the March
Hare, Mad Hatter, and Dormouse. The three were tried and made the following statements at the trial:
MARCH HARE: The Hatter stole the butter.
HATTER: The Dormouse stole the eggs.
DORMOUSE: I stole the milk.
As it happens,the one who stole the butter told the truth and the one who stole the eggs lied. Who stole what?
(Source: Alice in Puzzle Land: A Carrollian Tale for Children Under Eighty by Raymond Smullyan)
Here, things get a little bit more complicated. Each of the three accused stole one item and there are \(3!\) (or six) ways to pair off the accused with those items. But these can also be narrowed down fairly quickly.
First, consider the issue of the butter theft. First, assume that the March Hare stole the butter. If he stole it, then he wouldn't have said the Hatter stole it, because the butter thief tells the truth. So that can be ruled out. The Hatter's statement is at least consistent with stealing the butter. And the suspicion that the Hatter stole the butter is confirmed by the impossibility of the Dormouse being the thief; he would not have said he stole the milk. So the Hatter stole the butter.
Now the issue of the theft of the eggs can be considered. Culpability has already been assigned to the Hatter. That leaves the March Hare and the Dormouse. It can be known now that the March Hare told the truth, as he said that the Hatter stole the butter. The only option remaining is the Dormouse. And, indeed, the Dormouse's statement is a lie, given this inference. Then the Dormouse stole the eggs.
So, all told, the Hatter stole the butter, the Dormouse stole the eggs, and the March Hare stole the only remaining item: the milk.
Shortly after the cookbook was returned to the Queen, it was stolen a second time—again by either the Duchess, the Cook, or the Cheshire Cat.
At the trial they made exactly the same statements as at the last trial. Only this time, the thief lied and the other two either both lied or both told the truth.
Who stole the cookbook this time?
(Source: Alice in Puzzle Land: A Carrollian Tale for Children Under Eighty by Raymond Smullyan)
Recall that these were the statements from the last trial:
"The Cheshire Cat stole it!" said the Duchess at the trial.
"Oh, yes, I stole it!" said the Cheshire Cat with a grin.
"I didn't steal it!" said the Cook.
The most straightforward way is to consider whether each individual in turn might be the thief.
If the Duchess stole the cookbook, then her statement that the Cheshire Cat stole it is false, which is good so far because it is required that the thief lied. Then the Cheshire Cat is also lying because he claimed to have stolen it. But the Cook is telling the truth when she says she didn't steal it, and it is required that the two non-thieves either both told the truth or both lied. So the Duchess is not the thief.
If the Cheshire Cat stole the cookbook, then the other two are both telling the truth, which is good. But because it is required that the thief lied, the Cheshire Cat would have had to say he did not steal the cookbook. The Cheshire Cat is now also exculpated.
The only remaining option is the Cook. But to verify, it checks out that she lied, because she said she didn't steal it. And everyone else here has also perjured themselves so the criterion that the others must either both lie or both tell the truth is also met.
"Here is the baking pan," said the King, "so now you can make me the tarts."
"Without a recipe?" inquired the Queen.
"Use your usual recipe," cried the King impatiently, "last time your tarts were delicious!"
"Can't," said the Queen. "The recipe is in my cookbook, and the cookbook has just been stolen!"
Well, the most likely suspect was the Duchess's Cook, and the cookbook was indeed found in the Duchess's kitchen. The only possible suspects were the Cook, the Duchess, and the Cheshire Cat.
"The Cheshire Cat stole it!" said the Duchess at the trial.
"Oh, yes, I stole it!" said the Cheshire Cat with a grin.
"I didn't steal it!" said the Cook.
As it turned out, the thief had lied and at least one of the others had told the truth.
Who stole the cookbook?
(Source: Alice in Puzzle Land: A Carrollian Tale for Children Under Eighty by Raymond Smullyan)
As in part VII, an initially larger number of possibilities is constrained by the content of the statements to only two possibilities:
Duchess is truthful; Cheshire Cat is truthful; Cook is lying
Duchess is lying; Cheshire Cat is lying; Cook is truthful
In the first possible world, the Duchess and Cheshire Cat jointly confirmed that the latter stole the cookbook. But the Cook is lying and therefore also stole the cookbook, resulting in a contradiction. (It seems to be implied here that there was only one thief, which makes sense.) The only other alternative is the latter: the Cook is truthful, and did not steal the cookbook, and both the Duchess and the Cheshire Cat are lying about the guilty party. The only remaining party to take the blame is the Duchess.
"Here is some more salt, so now you can make the tarts," said the King.
"Can't," said the Queen. "Somebody stole my baking pan."
"Baking pan!" shouted the King. "Well, of course we'll have to get that back!"
This time the search was narrowed down to the Frog-Footman, the Fish-Footman, and the Knave of Hearts. They made the following statements at the trial:
FROG-FOOTMAN: It was stolen by the Fish-Footman.
FISH-FOOTMAN: Your Majesty, I never stole it!
KNAVE OF HEARTS: I stole it!
"A fine help you are!" shouted the King to the Knave. "You usually lie through your teeth!"
Well, as it happened, at most one of them lied.
Who stole the baking pan?
(Source: Alice in Puzzle Land: A Carrollian Tale for Children Under Eighty by Raymond Smullyan)
There are four possibilities here: first, that all told the truth and, in addition, the three possibilities of each of the accused lying in turn. The first can be ruled out immediately because the Frog-Footman claimed that the Fish-Footman stole the baking pan while the Fish-Footman disavowed any responsibility.
But what if the Frog-Footman lied? Then the baking pan was not in fact stolen by the Fish-Footman. The Fish-Footman can claim, truthfully, that he did not steal the pan. And the Knave of Hearts can claim to have stolen it if he did. So it looks like an answer has already been attained!
To be sure, though, check the other possibilities. If the Fish-Footman lied, then he stole the baking pan. So the Knave of Hearts must also be lying when he said that he stole it, which is impermissible. If the Knave of Hearts was lying, then he didn't steal the baking pan, in which case the same contradiction arises as when all are assumed to have told the truth.
So the Knave's confession is genuine beyond any doubt.
"Well," said the King, "here is your sugar, so you can make me the tarts."
"Without salt?" asked the Queen.
So! The salt had also been stolen! Well, this time it was found that the culprit was either the Caterpillar, Bill the Lizard, or the Cheshire Cat. (One of them had come into the kitchen and eaten up all the salt; the container wasn't missing.) The three were tried and made the following statements in court:
CATERPILLAR: Bill the Lizard ate the salt.
BILL THE LIZARD: That is true!
CHESHIRE CAT: I never ate the salt!
As it happened, at least one of them lied and at least one told the truth.
Who stole the salt?
(Source: Alice in Puzzle Land: A Carrollian Tale for Children Under Eighty by Raymond Smullyan)
Initially, it seems like there could be a total of \(\dbinom{3}{1}\) ways that one truth-teller could be assigned to a group of two liars and, then, respectively, \( \dbinom{3}{2}\) ways two truth-tellers could be assigned to a liar, to create the all the groups with compositions acceptable by the last stipulation in the story. Both of these combinatorial expressions evaluate to three and so six possibilities all told would appear to need consideration.
But wait! Before I enumerate them all! Know that things are actually more closely constrained because of the agreement between the Caterpillar and Bill the Lizard. There are indeed only two possibilities, namely:
Caterpillar is truthful; Bill the Lizard is truthful; Cheshire Cat is lying
Caterpillar is lying; Bill the Lizard is lying; Cheshire Cat is truthful
In the first instance, Bill the Lizard ate the salt. But then it is the case that the Cheshire Cat is not lying. Only the second option is therefore tenable and, in this instance, the Caterpillar and Bill the Lizard are both lying and the Cheshire Cat is truthful. From this it can be inferred that neither the Cheshire Cat nor Bill the Lizard ate up all of the salt, and the only remaining option is that the Caterpillar did it.
N.b. another part intervened between what was solved in the last post and the current one but it did not concern logic as such, but an incongruity with one of the characters used in story. As such I have skipped over it:
"That certainly cost me a lot of work finding the pepper," said the King angrily, "and I doubt that the tarts will be all that much the better for it! Pepper indeed!" continued the King. "Why don't you use blotting paper while you're at it?" he added sarcastically.
"I do," replied the Queen, "but not much."
"Very funny!" said the King. "Anyway, now you have your pepper back, so will you please make me the tarts?"
"Without sugar?" said the Queen.
"What's the matter, isn't the jam sweet enough?" asked the King impatiently.
"I need sugar for the dough, and my sugar has been stolen!"
"Oh, not again!" said the King wearily. "These tarts will never get made!"
Well, recovering the sugar turned out to be a relatively simple affair. The sugar was found in the house of the Duchess, and as events proved, it was stolen by either the Duchess or the Cook, but not both. They made the following statements at the trial:
DUCHESS: The cook did not steal the sugar.
COOK: The Duchess stole the sugar.
The one who stole the sugar was lying. (It is not given whether the other one lied or told the truth.)
Which one stole the sugar? Also, was the other one lying or telling the truth?
(Source: Alice in Puzzle Land: A Carrollian Tale for Children Under Eighty by Raymond Smullyan)
The simplest way to tackle this is to consider the implications of guilt for both the Duchess and the Cook. If the Duchess stole the sugar, then it really is the case that the cook did not steal the sugar, but who stole the sugar has to be lying. The only alternative is that the Cook stole the sugar. And, of course, for the second part, anyone in Wonderland might be talking nonsense, even not to their own advantage: the Duchess was also lying.
Then who did steal the pepper? "My, my, this is really a difficult case!" said the King.
The next suspects, curiously enough, were the Gryphon, the Mock Turtle, and the Lobster. At the trial, the Gryphon said that the Mock Turtle was innocent and the Mock Turtle said that the Lobster was guilty.
Again, no innocent one lied and no guilty one told the truth.
Who stole the pepper?
(Source: Alice in Puzzle Land: A Carrollian Tale for Children Under Eighty by Raymond Smullyan)
As in the prior case, one individual is claiming the other is innocent and this instance is formally identical to that other one. This means that Gryphon and Mock Turtle are both innocent and truthful. Accordingly, the Lobster is guilty.
So, who stole the pepper? Well, the King's next suspects were the March Hare, the Mad Hatter, and the Dormouse. Soldiers were sent to their house, but no pepper was found. Still, they might be hiding it somewhere, so they were arrested on general principles.
At the trial the March Hare claimed that the Hatter was innocent and the Hatter claimed that the Dormouse was innocent. The Dormouse mumbled some statement in his sleep, but it was not recorded.
As it turned out, no innocent one made a false statement and (we recall) people who steal pepper never make true statements. Also, the pepper was stolen by only one creature. Which, if any of the three, is guilty?
(Source: Alice in Puzzle Land: A Carrollian Tale for Children Under Eighty by Raymond Smullyan)
There is a kind of transitivity to this problem. Consider the first statement, made by the March Hare, that the Mad Hatter is innocent. Suppose it false. If it is false, then the Mad Hatter was the one and only thief. But because the supposition is that the March Hare lied, then the March Hare is also the thief. But this is impossible because it was stipulated that there would be only one thief. It follows thereon that the March Hare is in fact honest and that the Mad Hatter is innocent and therefore truthful. Transitively, the Dormouse is also innocent and therefore truthful. This time, none of them are guilty.
"Well, here is your flour," said the King happily, "so now you can make the tarts."
"Make tarts without pepper?" asked the Queen.
"Pepper!" said the King incredulously. "You mean you use pepper in your tarts?"
"Not much," replied the Queen.
"And I suppose it was stolen!"
"Of course!" said the Queen. "Find the pepper, and when you have found out who stole it, then off with his—"
"Now, now!" said the King.
Well, the pepper had to be found, of course. Now, as you all know, people who steal pepper never tell the truth.
"What!" said Alice (not the Alice in Wonderland, but the Alice of this party). "I never heard that before!"
"You haven't?" I said in mock surprise.
"Of course not! What's more, I don't believe anybody else has either! Have any of you heard that before?"
The children all shook their heads negatively.
"Well," I said, "for purposes of this story, let's assume that people who steal pepper never tell the truth."
"All right," said Alice, a bit hesitantly.
So, to continue the story, the most obvious suspect was the Duchess's cook. At the trial she made but one statement: "I know who stole the pepper!"
Assuming that people who steal pepper always lie, is the cook guilty or
innocent?
(Source: Alice in Puzzle Land: A Carrollian Tale for Children Under Eighty by Raymond Smullyan)
This one is simple, if an assumption not explicitly included here is added. Suppose that the Duchess's cook is the thief. In addition, assume that the thief would necessarily have full knowledge of the commission of the crime. In this case, the cook would have said that she didn't know who the thief was, as pepper thieves always lie. With this assumption, we can then conclude that the cook was not lying. Of course, even outside of Wonderland, there are instances where an individual may have no memory of a heinous crime:
Taken from Phencyclidine Abuse and Crime: A Psychiatric Perspective (Bauman and Bauman)
...but including this assumption expressly might have made the answer too easy to figure out.
"Now we have the jam back," said the King, "so you can make us some tarts."
"How can I make tarts without flour?" asked the Queen.
"You mean the flour was stolen?" cried the King.
"Yes!" said the Queen. "Find the miscreant, and take his head off!"
"Now, now," said the King, "let's not be hasty!"
Still, the flour had to be found. Sure enough, it was found in the home of the March Hare, the Mad Hatter, and the Dormouse, so these three were promptly arrested and tried.
At the trial, the March Hare claimed that the Hatter stole it. The Hatter and the Dormouse also made statements, but for some reason the statements were not recorded, so I cannot tell you what they were. Anyhow, as it turned out, only one of the three had stolen the flour, and he was the only one of the three who told the truth.
Who stole the flour?
(Source: Alice in Puzzle Land: A Carrollian Tale for Children Under Eighty by Raymond Smullyan)
First, note that the March Hare has somehow managed to avoid the executioner since the last episode, despite the punitive obsessions of the Queen.
But more to the point, there is only a single statement from the accused to evaluate here. That statement is: "The March Hare claimed the Mad Hatter stole it." This is necessarily false though, as "only one of the three had stolen the flour, and he was the only one of the three who told the truth". The only possible true statement of this form in this case is one of the accused saying: "I stole the flour." Accordingly, the March Hare is lying, and has not stolen the flour. Because of the content of the lie, the Mad Hatter cannot have stolen the flour either. From this we know that his testimony was dishonest, although not what it was. Given that this is a Carrollian story, it could be any number of false claims. But we can know, since neither of these other two stole the flour, that the Dormouse did, and made a true statement. Again, as this is a Carrollian story, we cannot know what the statement was. It may well not have been "I stole the flour"; it may have been irrelevant to the case entirely. But what we can infer from the sole statement made by any of the accused is that March Hare and the Mad Hatter have perjured themselves and the Dormouse is a thief.
"How about making us some nice tarts?" the King of Hearts asked the Queen of Hearts one cool summer day.
"What's the sense of making tarts without jam?" said the Queen furiously. "The jam is the best part!"
"Then use jam," said the King.
"I can't!" shouted the Queen. "My jam has been stolen!"
"Really!" said the King. "This is quite serious! Who stole it?"
"How do you expect me to know who stole it? If I knew, I would have had it back long ago and the miscreant's head in the bargain!"
Well, the King had his soldiers scout around for the missing jam, and it was found in the house of the March Hare, the Mad Hatter, and the Dormouse. All three were promptly arrested and tried.
"Now, now!" exclaimed the King at the trial. "I want to get to the bottom of this! I don't like people coming into my kitchen and stealing my jam!"
"Why not?" asked one of the guinea pigs.
"Suppress that guinea pig!" shouted the Queen. The guinea pig was promptly suppressed. (Those who have read Alice's Adventures in Wonderland will recall the meaning of the word suppress: The officers of the court put the guinea pig into a canvas bag, which tied up at the mouth with strings, and sat upon it.)
"Now then," said the King, after the commotion of suppressing the guinea pig had died down, "I want to get to the bottom of this!"
"You've already said that," remarked a second guinea pig. (This guinea pig was also promptly suppressed.)
"Did you by any chance steal the jam?" the King asked the March Hare.
"I never stole the jam!" pleaded the March Hare. (At this point all the remaining guinea pigs cheered, and were all promptly suppressed.)
"What about you?" the King roared to the Hatter, who was trembling like a leaf. "Are you by any chance the culprit?"
The Hatter was unable to utter a word; he just stood there gasping and sipping his tea.
"If he has nothing to say, that only proves his guilt," said the Queen, "so off with his head immediately!"
"No, no!" pleaded the Hatter. "One of us stole it, but it wasn't me!"
"Make a note of that!" said the King to the jury. "This evidence might turn out to be quite important!"
"And what about you?" continued the King to the Dormouse.
"What do you have to say about all this? Did the March Hare and the Hatter both tell the truth?"
"And what about you?" continued the King to the Dormouse. "What do you have to say about all this? Did the March Hare and the Hatter both tell the truth?"
"At least one of them did," replied the Dormouse, who then fell asleep for the rest of the trial.
As subsequent investigation revealed, the March Hare and the Dormouse were not both speaking the truth. Who stole the jam?
(Source: Alice in Puzzle Land: A Carrollian Tale for Children Under Eighty by Raymond Smullyan)
The book had its own, slightly different way of solving this. But here is my own:
First, recall that it is not the case that the March Hare and the Dormouse are both speaking the truth. This restricts the number of possible assignments of truth values to their statements from four to three, namely:
March Hare is lying; Dormouse is lying
March Hare is lying; Dormouse is truthful
March Hare is truthful; Dormouse is lying
Now, entertain, for a moment, the possibility that the Dormouse is lying in isolation. If the Dormouse is lying, then it is the case that neither the March Hare nor the Mad Hatter is truthful. If so, it is true that the March Hare stole the jam, because the March Hare said he didn't. But this would make the statement of the Mad Hatter that someone other than him of the three stole the jam true rather than false, resulting in a contradiction.
As a consequence of this, it is necessarily the case that the Dormouse is truthful. And in only one of the three options listed prior is this possible: when the March Hare is lying but the Dormouse is telling the truth. It follows immediately that the March Hare stole the jam. (Off with his head!)
Pay for an employee work for a month (that is, thirty days) is 10 dinars and a dress.
The employee worked three days only and earned the dress only. What is the price of the dress?
Answer given in source but no justification given. What is the answer and why? Let's represent the month's salary as $10 + x$, where $x$ is the price of the dress in dinars. Let's assume that working for exactly one-tenth of the month means getting exactly one-tenth of the pay. Then the value of wages paid in cash and in kind is $\frac{10 + x}{10}$. This value is equal to the price of the dress, so $\frac{10 + x}{10} = x$, therefore $1 + \frac{x}{10} = x$ and then $1 = \frac{9}{10}x$. Accordingly, $x = \frac{10}{9}$, just a little over one dinar.
(The most valuable dinar at the time of this posting is the Kuwaiti dinar, currently worth 3.32 USD each. Admittedly naively comparing this medieval dinar to any modern one and not correcting for inflation, the monthly wages for this worker would then be under 37 USD. Those were the days, when money really had value!)
The Terrible Twins, Innumeratus and Mathophila, were bored.
‘I know,’ said Mathophila brightly. ‘Let’s play dice!’
‘Don’t like dice.’
‘Ah, but these are special dice,’ said Mathophila, digging them out of an old chocolate box. One was red, one yellow and one blue.
Innumeratus picked up the red die. ‘There’s something funny about this one,’ he said. ‘It’s got two 3’s, two 4’s and two 8’s.’
‘They’re all like that,’ said Mathophila carelessly. ‘The yellow one has two 1’s, two 5’s and two 9’s – and the blue one has two 2’s, two 6’s and two 7’s.’
‘They look rigged to me,’ said Innumeratus, deeply suspicious.
‘No, they’re perfectly fair. Each face has an equal chance of
turning up.’
‘How do we play, anyway?’
‘We each choose a different one. We roll them simultaneously, and the highest number wins. We can play for pocket money.’ Innumeratus looked sceptical, so his sister quickly added: ‘Just to be fair, I’ll let you choose first! Then you can choose the best die!’
‘Weeelll . . . ’ said Innumeratus, hesitating.
Should he play? If not, why not?
(Source: Professor Stewart's Cabinet of Mathematical Curiosities, Ian Stewart)
This is one of those instances where averages don't really mean anything. Every one of the dice has the exact same expectation: $\frac{1}{3}(3 + 4 + 8) = \frac{1}{3}(1 + 5 + 9) = \frac{1}{3}(2 + 6 + 7) = \frac{1}{3}(15) = 5$. On this account, the game seems totally fair. So, should Innumeratus play? The names of the twins are a big hint: he should not. The way to know this is by pitting the dice against each other. For any two dice, the set of equiprobable outcomes of the game is the Cartesian product of the distinct numbers on the faces of the dice. For instance, the outcomes of casting the red die vs. the yellow die are $\{3, 4, 8\} \times \{1, 5, 9\} = \{(3, 1), (3, 5), (3, 9), (4, 1), (4, 5), (4, 9), (8, 1), (8, 5), (8, 9)\}$. In five out of these nine cases, the value of the yellow die exceeds that of the red die. Mutatis mutandis, the blue die beats the yellow die and the red die the blue die, five times out of nine. The situation described above is somewhat like playing rock-paper-scissors after you already know the opponent's choice, although more slyly, because the outcome is probabilistic rather than dead certain and, at that, nearly fair. Mathophila was attempting to lead her twin brother on with this offer to pick the "best" die, because the best die is the one chosen knowing what the other player has.
Another somewhat similar gimmick in probability that is apparently often successful in siphoning money out of people is the standard game of craps.
The following is not from a puzzle book but from the competitive programming website HackerRank. The problem in question was Strange Counter from the Algorithms section. I felt that the discussion was not adequate for help in solving the problem but I was able to write my own solution and share it with the others. Here is a full explanation. First, let's include a bit of the problem description:
Bob has a strange counter. At the first second $t = 1$, it displays the number $3$. At each subsequent second, the number displayed by the counter decrements by $1$.
The counter counts down in cycles. In the second after the counter counts down $1$, the number becomes $2 \times$ the initial number for that countdown cycle and then continues counting down from the new initial number in a new cycle. The diagram below
shows the counter values for each time $t$ in the first three cycles:
In other words, first there is a countdown from $3 * 2^0$, then a countdown from $3 * 2^1$, then a countdown from $3 * 2^2$, and so it goes. If it looks like the sum of a geometric series is being used here, it absolutely is. Recall that the sum of the first $n$ terms of a geometric series is (justification here):
$$a \frac{1 - r^n}{1 - r}$$
And in this particular instance, the formula is:
$$3 \frac{1 - 2^n}{1 - 2}$$
This information is very useful for solving the problem without any kind of brute force. Given $t$, it is possible to know directly how many of these countdowns have already passed by completely. The length of these past countdowns can then be subtracted from $t$, and then $t$ can be subtracted from the length of the current countdown to find the value of the counter. Before going any further with the mathematics, consider a number of examples:
At $t = 1$, no counters have passed by completely. The current counter is therefore the counter that goes from three down to one. Because the counter indexing is one-based (like vectors in R, let's say), the value of the counter is $3 - t + 1$ or very simply three.
At $t = 2$ and $t = 3$, the same reasoning applies and the values of the counter are, respectively, two and one.
At $t = 4$, however, a full prior countdown has now passed. The reasoning is different here. The current countdown goes from six to one. Subtracting the length of the previous countdown from $t$ is necessary to find out what $t$ indexes relative to the current countdown. Because the length of the prior countdown was three, then the value of the counter is $6 - (t - 3) + 1$ or very simply six.
The same reasoning applies for $t \in \{5, 6, ... , 9\}$
At $t = 10$, two entire counters have passed by entirely. Their lengths, three and six, need to be added together and subtracted from $t$ so that the value of the counter can be found. Then applying the previous reasoning results in the value of 12 for the current value of the counter.
So far it seems like there are two central questions here:
What counter does $t$ belong to?
What offset needs to be subtracted from $t$ so that it can be used to index the current counter?
The answer these questions, note that $t$ is greater than or equal to the summed lengths of zero or more countdowns that have fully elapsed. This can be stated accordingly:
In programming terms, $n$, the number of fully elapsed countdowns that happened before timestep $t$, can be determined by evaluating the right-hand expression and then finding its floor (i.e. the largest integer less than or equal to it).
After doing this, the offset, namely the sum of the first $n$ terms of the geometric series can be evaluated as described above for this value of $n$ and subtracted from $t$. This value can then, in turn, be subtracted from the length of the current counter, which is $3 * 2^n$, to find the current value of the counter, with one exception: when $t$ indicates the final value of the current counter, namely, one. Here the current counter has ended, but the next has not yet begun. This case can be detected by the fact that $t$ minus the offset is equal to zero. The case can then be handled simply by printing one. In all other cases, the process I described above applies. Finally, implementing the algorithm in Scala, we have a very short and efficient program indeed:
importscala.io.StdInimportscala.math._objectSolutionextendsApp{val t =StdIn.readLine().toDouble
// for the expression 3 * (1 - 2^n) / (1 - 2) which is the sum of the first n terms of the seriesval n =((log(t +3)- log(3))/ log(2)).floor
val offset =3*(1- pow(2, n))/(1-2)if(t - offset ==0){
println(1)}else{
println(f"${3 * pow(2, n) - (t - offset) + 1}%.0f")}}
Notice that, in the else clause above, the output is formatted so that the Double used for calculation will appear to be an integer. This is not a fundamental part of the algorithm but simply a requirement for the code judge to accept the output.
