Log In

Invert 3 signals using 2 NOT gates

Posted on: February 9th, 2016 by

You have 3 boolean inputs A, B and C. You want to obtain NOT(A), NOT(B) and NOT(C) all at once. However you are allowed to use at most 2 NOT gates. You may use as many AND and OR gates as you like. You may not use any other gates.

Can you build a circuit to achieve this?

- Via multiple sources including a bonus homework problem in school.


Posted on: February 7th, 2016 by
Comments Disabled

Consider the inequality

\frac{1}{x-1} + \frac{2}{x-2} + \frac{3}{x-3} + \dots \frac{70}{x-70} \geq \frac{5}{4},
where x is real.
Show that the sum of the lengths of the disjoint intervals that satisfy the above inequality is 1988.

- via International Math Olympiad 1988.

Antipodal points

Posted on: September 6th, 2015 by

Let f(t) be a continuous periodic function with period T, i.e.

  1. f(t) is continuous over reals.
  2. f(t+T) = f(t) for all real t.

Show that there always exists some time instant t_0 for which f(t_0) = f(t_0+T/2).

A dragon, a knight and poison fruits

Posted on: February 19th, 2015 by

A knight and a dragon were dueling on a remote island. After a long time, they were tired of battle and decided to instead fight with their wits. The island consists of 7 different kinds of poison fruits, namely type 1, type 2, ... type 7. These fruits are magical and they work in a special way. If you eat a fruit of type i, the only way to cure yourself is by eating a fruit of type higher than i. If not, you will die exactly 1 hour after eating the fruit. Thus if you eat a type 7 fruit to start with, you are guaranteed to die because there is no higher level fruit. A more complex example: If you eat a type 2 fruit followed by a type 1 fruit and then a type 2 fruit and finally a type 3 fruit, you are cured. The type 1 fruit is ineffective and you are still affected by type 2. The type 2 fruit is also ineffective. Finally, the type 3 fruit neutralizes the type 2 poison and you are cured. The catch is that the type 7 fruit is on top of a mountain and is accessible only by the dragon.

The knight and the dragon will meet for dinner and will give each other a fruit that they are supposed to eat. Is it possible for the knight to guarantee survival? Is it possible for the dragon to guarantee survival?

--- via n1b-algo blog.

Space filling curve

Posted on: November 29th, 2014 by

Can you find a continuous function from the unit interval [0,1] to the unit square [0,1]^2?

In other words, can you find a curve that passes through all points in a unit square?

Coin covering puzzle

Posted on: November 27th, 2014 by

100 identical circular coins are placed in a rectangular table such that no extra coin can be placed without overlapping with one of the coins already on the table. For the purpose of this puzzle, assume a coin is placed on a table as long as it's center lies on the table. Show that with 400 coins, one can cover the entire surface area of the table such that there is no patch in the table that is not covered by a coin.
-via AMS puzzle corner

Parabola puzzle

Posted on: November 25th, 2014 by
Comments Disabled

Let y=ax^2+b_1x+c_1 and y=ax^2+b_2x+c_2 be two parabolas with the same coefficient for the x^2 term. The y-intercepts of the two parabolas are (0,c_1) and (0,c_2) respectively. Let the two parabolas intersect at (x_1,y_1) and let the tangent to the two parabolas drawn at (0,c_1) and (0,c_2) intersect at (x_2,y_2). Show using physics that x_1=x_2.

Hint: Assume x is time and y is space, and there is acceleration due to gravity of a/2 in this 1-d space. View objects first in an inertial frame, and then in an accelerated frame of reference accelerating forward at a/2.

Find the product

Posted on: October 13th, 2014 by

What is (1-1/4)(1-1/9)(1-1/16)....(1-1/n^2)?

- via Mind your decision

Range finder

Posted on: October 12th, 2014 by

Let f(x) = \frac{x^2+x+1}{x^2+x+2}. Show that for real x, 3/7\le f(x) \le 1.

BRICS bank and Erlang's formula

Posted on: July 28th, 2014 by
Comments Disabled

If you have been following news, you will know that the 5 BRICS nations, namely Brazil, Russia, India, Chian and South Africa, came together to form the BRICS bank. Each country contributed $10 billion to net $50 billion of initial capital. The purpose of the BRICS bank is to provide loans for infrastructure projects in the BRICS nation. You may note that all 5 BRICS nations expect equal control and equal amount of loans, since they all contributed funds equally. Except in case of financial emergency, they don't want any one country to take too much loans. Why then go through the trouble of coming together to make a bank? You may note that India and China already have territorial disputes. They came together inspite of these disputes to actually build a common bank for developing nations.

To understand why pooling together all available capital is better than each country opening it's separate bank, we must understand what is called Fractional Reserve Banking.

In order to start any new company or business, or maybe build a home or buy a car, or perhaps get education in a college, we need a lot of capital. For this, we may obtain loans from a bank and repay them later. That will remove the constraint of actually having to accumulate enough capital before we have to make an investment.

Normally, one would think that a bank cannot lend more money than it has. However, in modern times, every bank lends more money than they have. The government has setup a body called the reserve bank, a bank of banks. One of the purposes of this bank is to set what is called the reserve ratio, which is the percentage of capital a bank should keep in reserve for every loan it makes. To understand this better, suppose a person X borrows $100 from the bank. The person will not withdraw all his money at once. He will still store it in the bank in his account and will withdraw money only when he needs it. He will of course pay interest to the bank on the loan. Now, the bank does not want to just keep the $100 loan unused in reserve. Instead, it would like to lend this money to another person, so that they can collect more interest. The bank however should still be able to let each person withdraw money from his/her account when he/she wants. For this reason, the bank needs to have some reserve capital. This is where the reserve ratio kicks in. The law requires that the bank designate 10% of the loan, say $10 as reserve capital. The bank may lend the remaining $90 in loans to a second person. Now, the second person will also store the money in the bank. The bank once again has to allocate $9 (10% of $90) in reserve capital and is free to lend the remaining $81 to a 3rd person. In this way, the bank can multiply the amount of capital available to a person. The total amount of loans given out is then $100+$90+$81+.... = $1000. In general, if the reserve ratio is r%, the bank can give a total loan equal to $100(1+(1-r/100)+(1-r/100)^2+.....) = $100*(100/r while having a capital of only $100. Thus, suddenly there is more money available to invest in infrastructure projects than is stored in the bank reserves. This is achieved without increasing the amount of money supply in the economy, therefore keeping inflation of basic goods at a check.

There are two caveats to this system of banking. The first caveat is that the banks must verify that the persons who receive the loans will be able to repay the loans. Their failure to do so caused the famous sub-prime crisis in the united states, following which more stringent rules and credit checks were introduced on borrowers to ensure defaults do not occur in larger than manageable amounts. The second caveat is that when too many people request to withdraw money at the same time, the bank won't have enough capital available to process their requests. We can see that the second caveat of having enough reserve capital ties directly to the reserve ratio. If there is no reserve ratio, there will be infinite capital available to lend to people ($100*100/r=infinity when r=0), but as soon as a few people simultaneously withdraw money, the bank, having 0 reserve capital, will immediately collapse, leading to a huge financial crisis. Hence, the bank must set the reserve ratio high enough to ensure that it doesn't run out of funds in case of simultaneous withdrawals, but low enough that there is enough capital. Indeed the amount of capital is much higher for lower reserve ratios, whereas the probability of bank default also gets higher.

Now one may still wonder why BRICS nations have to come together to setup a bank. I will explain this by first considering a simple problem related to Stanford housing. Stanford has two kinds of houses. One is a 4 people home with 2 bathrooms and the other is a 2 person home with 1 bathroom. When I want to use the bathroom, I want at least one bathroom available. Suppose that at any time, a person wants to use a bathroom with probability p=0.05 or 5%. Then in the 4 people 2 bathroom home, the chances that both bathrooms are already occupied is 3*p^2(1-p)+p^3=0.725%. However, in the 2 people 1 bathroom home, the probability that the available bathroom is already occupied is 5%. Thus even though both homes have the same number of bathrooms per person, the chances of not having a bathroom in the former home is significantly higher in the 2 bedroom 1 bathroom scenario as opposed to the 4 bedroom 2 bathroom scenario.

The scenario discussed above can also be applied for telephone lines. If there are 10,000 people, the telephone company won't want to build 10,000 lines. That is too costly. Besides, not all people will want to talk on the phone simultaneously. Therefore, the telephone company will build, say 100 lines, and allow 10,000 people to share these 100 lines. If more than 100 people simultaneously decide to call, then your call will get blocked. If during the duration of your average call, the expected number of people from the population who also want to call is E, the Erlang B formula B(E,m) gives the probability that your call is blocked when there are m telephone lines. Of course, the more precise description of Erlang formula is via a Poisson process used to model telephone calls. For example, if during every average call that you make, there are 9 other simultaneous calls on average, and the total number of lines is 10, the blocking probability for your call is the probability that all lines are busy and is equal to B(9,10). Now, let us compare B(9,10) and B(90,100) by using this online calculator: http://www.erlang.com/calculator/erlb/ . We find that B(9,10)=16.8% whereas B(90,100)=2.7% which is significantly lower. Thus even though 9 lines for 10 people and 90 lines for 100 people corresponds to the same number of lines per person, the sharing of lines among more people reduces the blocking probability of your call significantly.

We will now apply this intuition to the bank. Each dollar of loaned money, equal to $100*100/r will at some time be withdrawn independently and is deposited back into the bank after a period of time and we like to ensure that the probability of bank default is low. This probability is precisely the probability that more than $100 is simultaneously withdrawn. Now we immediately see the advantage of BRICS bank. Just like 100 lines for 90 average simultaneous calls during an average call duration is better than 10 lines for 9 average simultaneous calls during an average call duration, $50 billion shared by the 5 countries is better than $10 billion for each country in terms of avoiding bank default. Thus the BRICS bank may be able to lower the reserve ratio r for lending and thereby increase the total amount of capital $100*100/r without adversely affecting the probability of default. Now all the BRICS nations have magically increased the total amount of available capital without affecting the quality of the bank and without causing inflation.

Of course, there are other reasons for the BRICS bank. Establishing friendly relations among nations is one of them. Providing a competition to the world bank as a challenge to western hegemony over world affairs is another key reason. We did not include all the advantages of BRICS bank for the nations involved.

{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}