Brain Teasers

For each brain teaser you solve, you will get a snicker.
The purpose of having brain teasers is to sharpen our creativity and to develop an original and "unconventional" way of thinking. It is this creativity and originality that will help us discover great things in research. It is hoped that the questions presented in this page will serve its purpose. 

 

Q1. [Number System, [5/29]] Show that there exists no 4 distinct integers a, b, c and n such that the following equation is true

 na + nb = nc    (Hint :- Consider this equation in base-n number system).

One easy way of doing it is, rearrange the above equation
1 = (nc - nb)/na (Using factor theorem we say that the numerator (RHS) got to have a factor of (n-1) or (n+1), say F, depending on if b, c is even/odd. But in the denominator we don't have the factor F. Thus they can never cancel out to yield 1 (LHS). Hence proved). 
But this solution is not acceptable because this does not use Number System. Find a solution using only the concepts that we learnt in lecture 1 (sec 2.1-4).
 

The following students have given the correct answer

Kevin
Anirudha Karnik
Thomas Peters

Congrats!!!
Q2. [Gray Code [6/2]] Give an efficient step by step procedure to perform addition of 2 gray code numbers to yield another gray code number (Your procedure should not involve converting a gray code number to a binary number and vice versa).

Q3. [Gray Code & Induction [6/6]] Discover a new coding scheme called gray-2 code in which a number and its successor differ each other by 2 bits. Give a step by step procedure to show how to convert a binary number to a gray-2 code number and vice-versa. Also use mathematical induction to show that every gray-2 code number represents a unique binary number.

The following students have given the correct answer

Kevin
Anirudha Karnik
Thomas Peters
Congrats!!!

 
Q4. [Branching Method 6/12] Write a program in C/C++ to compute the logic expression using branching method. Your program should take the input from a text file in.txt and should store the output in the file out.txt. The first line of the input file contains the number of primary inputs. The second line contains the variable names used for representing primary inputs. And the last line contains min-term list. An eg. is shown below
4
A B C D
0 2 4 5 6

The output file should contain the essential prime implicant expression, followed by all the possible logic expr that your program has explored. Finally it should also contain the logic expr. which is least expensive. (Note:- Those students who don't have programming background can write a pseudo-code for this problem)
Anirudha Karnik gave a psuedo-code for this probem. 
Excellent Job.
Q5. [Timing Hazard [6/16]] For the circuit given below show that the condition,
| t2,f + t3,f - t1,r |x(t1,f - t2,r -t3,r) + (t2,f + t3,f - t1,r )x|t1,f - t2,r -t3,r| = 2x(t2,f + t3,f - t1,r)x(t1,f - t2,r -t3,r)
is a sufficient condition to ensure that the ckt is glitch free.

The following students have given the correct answer.
Kevin
Anirudha Karnik
Thomas Peters

Great Job!!!
Q6. [A Strategy Game [6/24]] This problem describes an interesting card game played between two players X and Y. There are nine cards each card labeled by digits 1-9. No two card bear the same label. Both the players can look at the labels of the card. X starts the game by picking up one card. After that, players take alternating turns. In their turn they can pick any card that is left. That player wins the game who manages to pick three cards which adds up to 15. You will have to design a logic circuit using MUX, decoders and D-Latch which can play this game against any intelligent human and will never loose!!! In your solution, you should explain your strategy, the input/output of your logic circuit and a complete logic diagram of your circuit.

[A 0/1 Switch] A switch is a 3-terminal device as shown below. Here 'a' is the input. The terminals 'b' and 'c' gets shorted depending on the value of 'a' and 'b'. The truth table for 0-switch and 1-switch is shown below.
 

 

 

 

 

0-switch 1-switch
a b c behav.
0 1 X b-c short
0 0 X b-c open
1 X X b-c open
a b c behav.
1 0 X b-c short
1 1 X b-c open
0 X X b-c open
The 0/1-switch can be used to construct logic gates! The figure below shows how one can use 0/1 switch to construct a NOR gate. Click here.
Q7 [A XOR/XNOR gate [6/26]] Using only 3 0-switch and 3 1-switch construct a XOR/XNOR gate.
Q8 [A Full Adder [6/28]] Using only 9 0-switch and 9 1-switch construct a full-adder.
Q9 [A Factorial ALU [7/3]] Using 74x374 and other components, design an ALU which supports an instruction to compute the factorial of a given 8-bit unsigned binary number. Make an estimate of the number of bits required to represent the output (in BCD) and use 74x374 (or any other multi-bit register) to represent the answer. Your ALU should not just compute the factorial by recursive/iterative multiplication but should compute the answer efficiently. Interested students might wish to refer "Trachtenburg's Speed System Mathematics".
Q10 [LFSR Up/Down [7/ 3]] Design a 4-bit LFSR whose characteristics equation is 1 + x + x4. Your LFSR should also be able to generate 0000. It should have an input DIR which indicates whether the LFSR counts up or it counts down. Also design the LFSR to initialise to 0000.

Q11 [BONUS, State Machine [7/ 3]] Prove that there exists no finite-state machine that accepts precisely all those sequences that read the same forward as backward, i.e., sequences that are their own reverses. (Such sequences are called palindromes.)