I will keep this post short. First make sure you take a look at the original puzzle - link here.
The shortest sequence is 6 bits long and is “100110″ (or its inverse “011001″). The smallest amount of bits needed to determine a direction is 5, i.e. any 5 consecutive bits seen by the snail could help him determine the direction home.
It’s been a while since I posted some puzzles or solutions to puzzles. I noticed that I concentrated lately more on tricky circuits and fancy ideas but neglected the puzzle section. Some readers asked me to post some more puzzles. Before I can do that, I have to first clear the list of all unsolved puzzles.
The clock frequency driver puzzle drew little attention compared to the others and I got only one complete and correct solution for it.
What follows is my own solution which I hope will be easily understood.
The requirement was to have a NAND gate as the last output stage with one input driven by a rising edge triggered memory element and the other by a falling edge triggered memory element.
A look at the NAND gate truth table reveals that somehow the inputs have to toggle between “11″ (to generate a logical “0″) and “10″, “00″ or “01″ (to generate the logical “1″) on each and every clock edge!
I will now describe the solution for a certain case while the value in brackets will represent the analogous opposite case.
This in tern means (and without loss of generality) that with each rising[falling] clock edge the output state of both flops should be “11″. On the falling[rising] edge we should have the states “00″, “01″ or “10″.
The state “00″ can be immediately eliminated because the transition “00″ –> “11″ means we have to have both bits change on the rising[falling] edge together.
we are left with the following possible cases for the transitions (”r” marks a rising edge transition, “f” a falling edge transition):
Looking at the first option reveals that the rightmost bit needs to change on the rising edge from “0″ to “1″ and on the falling edge from “1″ to “0″ - this is not possible or in contradiction to the rules.
The second option looks promising - the rightmost bit changes from “0″ to “1″ on the rising edge, the left most from “1″ to “0″ on the falling edge - so far so good… but, let us continue the pattern:
“10″ r–> “11″ f–> “01″ r–> “11″
Each second state has to be “11″. After continuing the sequence for one more step we see that now the rightmost bit changes from “0″ to “1″ on the rising edge, but the immediate previous transition had it change on the falling edge, therefore we get again a contradiction!
We conclude that having a NAND on the output is impossible.
As mentioned before Mark Wachsler sent his own solution long time ago. Here it is in is own words:
I’m assuming the question is, is it possible to do something like this:
always @ (posedge clock) p <= something;
always @ (negedge clock) n <= something else;
assign out = ~ (p & n);and have out toggle on every transition of the clock?
If so, the answer is no.
Proof by contradiction:
1. Assume it can be done: out toggles on every transition of the clock.
2. We know p and n never change simultaneously, so for out to toggle,
either p or n must be 1.
3. So it may never be the case that p == 0 and n == 0.
3. Since they can’t both be zero, and they never change
simultaneously, at least one of them must always be 1.
4. But if n is always one, out can’t have a transition on negedge.
And if p is always one, out can’t have a transition on posedge.
5. Therefore there are some clock edges on which out doesn’t toggle.So it can’t be done.
Here is another puzzle for you to ponder during the upcoming week. It would seem a bit far fetched from our usual digital design stuff, but the solution is somewhat related to the topics discussed in this blog. Moreover, it is simply a neat puzzle.
A group of 50 people are forming a column so person #1 is in front of all, followed by person #2 and so on up to person #50.
Person #50 can see all the people in front of him (#49..#1), person #49 can see only #48..#1 and so on.
The 50 people are now given hats in random. Each hat can be either black or white. The distribution of the hats is totally random (i.e. they might be all black or all white and not necessarily 25-25)
The people now take turn in guessing what color hat they are wearing - They are just allowed to say “white” or “black”, nothing more!. Person #50 starts and they continue in order down to person #1. If the person happens to guess the color of his own hat the group receives $1000.
What is the best strategy the 50 people should agree on before the experiments starts to maximize the amount of money they should expect? And what is the sum of money they should expect to earn from this experiment?
(you can do better than pure chance, or much better than $25,000…)
For the experts
What if the experiment is done with hats which are red, black or white? what about 4 colors? What would be the maximum color of hats that will still guarantee the amount from the original variant? and how?
Your company is pretty tight on budget this year and it happens to have only Muxes to design with.
You are required to design a circuit equivalent to the one below, using only Mux structures.
It’s been a while since I posted a nice puzzle and since I know they are so popular, here is a relatively simple one. It was used in job interviews btw (the last line will boost the amount of views for this post…)
A snail leaves his warm house and takes a crawl through the forest leaving behind him on the ground a trail of “0″s and “1″s. He takes a very complicated route crossing his path several times. At one point he becomes tired and disoriented and wishes to go back home. He sees his own path of “0″s and “1″s on the ground which he is about to cross (i.e. not the trail ending in his tail) and wonders whether to follow the trail towards the left or towards the right.
What is the shortest repeating code of “0″s and “1″s he should leave as he crawls in order to easily and deterministically track the way back home? What is the minimum amount of bits he needs to observe (or the sample length of the code)?
This puzzle created some interest, but apart from one non-complete solution which demonstrates the principle only, I didn’t receive any other feedback. Here is my own solution, which is different than the one given in the Winkler book. Naturally, I believe my solution is easier to understand, but please get the Winkler book, it is really that good and you could decide for yourself.
Now for the reason you are reading this post… the solution… oh, if you don’t remember the puzzle, please take a few moments to re-read it and understand what it is all about.
I will (try to) prove that 16 different symbols can be transmitted by flipping a single bit of the 15 which are transmitted daily.
First, for convenience reasons we define the 15-bit transmission as a 14-0 vector.
We will now define four parity functions P0,P1,P2,P3, as follows:
Why these specific functions will be clear in a moment.
Let’s try to view them in a more graphical way by marking above each bit in the vector (with the symbols P0..P3) iff this bit affects the calculation of the respective “P-function”. For example, bit 11 is included in the formula for P0 and P3 therefore we mark the column above it with P0 and P3.
So far so good, but a closer look (diagram below) on the distribution of the “P-functions” reveals why and how they were constructed.
The “P-functions” were constructed in such a way that we have 1 bit which affects only the calculation of P0, one bit which affects only P0 and P1, one which affects only P0 and P2 and so on… Try to observe the columns above each of the bits in the vector - they span all the possible combinations!
From here the end is very close.
The operators on the receiving side have to calculate the P0..P3 functions and assemble them into a 4-bit “word”.
All the spy has to do, is calculate the actual “P-functions” given by today’s random transmission and get a 4-bit “word”. The spy compares this to the 4-bit “word” she wants to transmit and discovers the difference - or in other words: the bits which need to be flipped in order to arrive from the actual “P-functions” to the desired “P-functions”. She then looks up in the diagram above and flips exactly that bit which corresponds to exactly the “P-functions” that she needs to flip. A single bit flip will also toggle the corresponding “P-function/s”.
Since the above wording may sound a big vague, here is a table with some examples:
I have to say this again, This is really one of the most beautiful and elegant puzzles I came across. It is definitely going into “the notebook”…
Take the clock frequency circuit I posted about here. As I mentioned the XOR gate at the output might cause some duty cycle distortion with some libraries, due to the fact that most XOR gates are not built to be symmetrical with respect to transition delay.
Now, assume your library has a perfectly symmetrical NAND gate. Could you modify the circuit so the XOR will be replaced by a NAND gate and still have a clock frequency at the output (You are of course allowed to add more logic on other parts of the circuit).
If not, give a short explanation why not. If yes send a circuit description/diagram.
This one was solved pretty quickly. Basically I was trying to trick you. The idea was to try to create the impression an infinite amount of memory is necessary to hold all the 0–>1 and 1–>0 transitions. In practice there cannot be 2 consecutive 0–>1 transitions (or vice versa) since if the input goes from 0 to 1 before the next 0–>1 transition it must change to a 0 and thus have a 1–>0 transition!
The FSM can have only three states: “exactly one more 0–>1″, “equal amount of 0–>1 and 1–>0″ or “exactly one more 1–>0″.
It’s time for puzzle #7.
An FSM receives an endless stream of “0″s and “1″s. The stream can not be assumed to have certain properties like randomness, transition density or the like.
Is it possible to build a state machine, which at any given moment outputs whether there were more 0–>1 or 1–>0 transitions so far?
If yes, describe briefly the FSM. If no, give a short proof.
The binary-Gray puzzle from last week generated some flow of comments and emails.
Basically, the important point to notice is the amount each counter toggles while going through a complete counting cycle.
For Gray coded counter, by definition only one bit changes at a time. Therefore, for an n stage counter we get 2^n toggling events for a complete counting cycle.
For binary coded n-bit counter, we have 2^(n+1)-2 toggling events for a complete counting cycle. you could verify this by
Anyways, given the above assumptions and the fact that per bit the Gray counter consumes 3 times more power (2 times more would also just work, but the difference would be a constant), the Gray counter will always consume more power.
3*2^n > 2^(n+1) - 2
You are currently browsing the archives for the Puzzles category.
