Do networks bother you?

We’ll try to find out the total number of ways to reach a destination from a source for any given network.

In how many ways can you reach the Destination from the Source as shown in the network above?

Pretty easy. Right?

Total of 4 ways. Quite clear from the diagram.

• Start - A - C - D - E - G - Destination
• Start - A - C - D - F - G - Destination
• Start - B - C - D - E - G - Destination
• Start - B - C - D - F - G - Destination

For this diagram, it was easy to visualize all the paths from Source to Destination.

But, what if the diagram is:

or, increasing the complexity a bit further:

Would you still be able to picture out all of the possible paths for the given diagram?

We need utmost care to not possibly miss any of the paths, if we go on counting all of the paths in the network.

Let’s figure out a simple process by which we’ll able to find out the total number of paths to reach a destination from a source for any given network, however complex it may be.

For all the nodes we need to fetch the following information:

• Total incoming paths to a Node

And, the steps are:

1. Calculate total incoming paths to any node

2. Outgoing paths will contain a value which is the sum of all the incoming paths

3. So, all subsequent nodes from N can be reached by the sum of the number of all the incoming paths.

4. And, last but the most important point to consider: We’ll always assume that the total number of ways to reach our source node is 1. So, all the outgoing paths from source will start with value 1.

That’s it.

Enough of concepts.

Let’s get down with solving the networks we saw earlier.

Problem 1:

Find the total number of ways to reach Destination from Source.

Total incoming paths to B = 1 (As all the paths emanating from Source contain value 1)

Therefore, Outgoing paths from B = 1

Total incoming paths to E = 1

Therefore, Outgoing paths from E = 1

Total incoming paths to D = 1+1+1 = 3

Therefore, Outgoing paths from D = 3

Total incoming paths to C = 1+3 = 4

Therefore, Outgoing paths from C = 4

Total incoming paths to F = 3+1 = 4

Therefore, Outgoing paths from F = 4

So, Total number of ways to reach Destination = From C + From D + From F = 4+3+4 = 11

So, a total of 11 ways to reach the Destination from Source.

Problem 2:

Find the total number of ways to reach Destination from Source.

Total incoming paths to B = 1

Therefore, Outgoing paths from B = 1

Total incoming paths to G = 1

Therefore, Outgoing paths from G = 1

Total incoming paths to E = 1+1+1 = 3

Therefore, Outgoing paths from E = 3

Total incoming paths to C = 1+3 = 4

Therefore, Outgoing paths from C = 4

Total incoming paths to H = 3+1 = 4

Therefore, Outgoing paths from H = 4

Total incoming paths to F = 4+4+3 = 11

Therefore, Outgoing paths from F = 11

Total incoming paths to D = 4+11 = 15

Therefore, Outgoing paths from D = 15

Total incoming paths to I = 4+11 = 15

Therefore, Outgoing paths from I = 15

So, Total number of ways to reach Destination = From D + From F + From I = 15+11+15 = 41

So, a total of 41 ways to reach the Destination from Source.

Hope, problems from networks don’t become a problem for us in future. :)

Cheers.

What day was 15th August, 1947?

Do you know what was the day when we got independence from the britishers?

Yes, the date was 15th August, 1947. But what was that auspicious day? Was it Sunday, Monday or Thursday or any other day?

We'll try to formulate a process in this text by which we will be able to tell the exact day for any date provided. 

But before venturing further into the discussion, make sure you have the patience to sit for next 15-30 minutes with a pen and paper in your hand and a cup of coffee beside :).

Let's define a term: 

Number of odd-days = Remainder obtained when a number is divided by 7

Now:

All the years (2001, 1947, 1971 etc) can be categorized broadly into two parts:

• Non-Leap years: Years having 365 days
  

Number of odd-days (NLY) = Remainder (365/7) = 1

• Leap years: Years having 366 days.
  

Number of odd-days (LY) = Remainder (366/7) = 2

We are not through yet and need few other information as well in order to find out the day of our independence!!!!

So, let's find out a few other information as well, which will be quite helpful later on:

• Number of odd-days in 100 years:
  

In 100 years there are 76 Non-Leap years (NLY) and 24 Leap years (LY).

100 years = 76 Non-Leap years  + 24 Leap years

                    = 76 NLY + 24 LY

Now, from previous calculation we that number of odd-days is 1 for NLY and 2 for LY.

So, number of odd days in 100 years = Remainder (76 * 1 + 24*2) when divided by 7

 = Remainder ( 76 + 48) when divided by 7

 = Remainder ( 124) when divided by 7

 = 5

Therefore, Number of odd-days in 100 years = 5

• Number of odd-days in 200 years:
  

Number of odd-days in 200 years = Remainder (2 * Number of odd-days in 100 years) by 7

 = Remainder (2 *5) by 7

 = Remainder (10) by 7

 = 3

Therefore, Number of odd-days in 200 years = 3

• Number of odd-days in 300 years:
  

Number of odd-days in 300 years = Remainder (3 * Number of odd-days in 100 years) by 7

 = Remainder (3 *5) by 7

 = Remainder (15) by 7

 = 1

Therefore, Number of odd-days in 300 years = 1

• Number of odd-days in 400 years:
  

Let's add a fact before venturing into calculation:

In each 400 years 1 extra day is added to our calendar system (Some stuffs related to earth's imperfect revolution around the Sun).

So, 

Number of odd-days in 400 years = Remainder (1+ 4 * Number of odd-days in 100 years) by 7

 = Remainder (1+ 4 *5) by 7

 = Remainder (21) by 7

 = 0

Therefore, Number of odd-days in 400 years = 0

We have been calculating the number of odd-days for a quite while. Yet we are quite in dark of its roles of determining the specific day for a given date.

So, the final nail in the coffin:

If our final outcome of the number of odd-days comes out to be 0, then the day will be Sunday. If number of odd-days is 1, then the day will be Monday and so on.

Expressed in tabular format:

If Number of odd-days = 0, then the day will be Sunday

If Number of odd-days = 1, then the day will be Monday

If Number of odd-days = 2, then the day will be Tuesday

If Number of odd-days = 3, then the day will be Wednesday

If Number of odd-days = 4, then the day will be Thursday

If Number of odd-days = 5, then the day will be Friday

If Number of odd-days = 6, then the day will be Saturday

Enough discussion of concepts. Let's venture into our original problem.

Our basic problem was: 

What day was 15th August, 1947? Was it Monday or Thursday or Sunday or any other day?

15th Aug, 1947 is made up of:

• 1946 full years,
  
• 7 months (Jan, Feb, Mar, Apr, May, Jun, July), and
• 15 days of August

We'll calculate number of odd-days for each of the three afore-mentioned entities and then add them up to obtain the resultant number of odd-days.

• 1946 years
  

 1946 years = 1600 years + 300 years + 46 years 

 = (400 * 4) years + 300 years + 46 years

Number of odd-days in 1946 years = Remainder((400 * 4) years + 300 years + 46 years) by 7

= Remainder( 0 + 1 + odd days in 46 years) by 7

In 46 years, there are 11 Leap years and 35 Non-Leap years.

So, Number of odd-days in 46 years = Remainder (11*2 + 35*1) when divided by 7

 = Remainder (57) when divided by 7

 = 1

Number of odd-days in 1946 years = Remainder(0+1+1) by 7

 = Remainder (2) by 7

 = 2

So, Number of odd-days in 1946 years = 2

• 7 months (Jan, Feb, Mar, Apr, May, Jun, Jul):
  

Number of odd days in Jan = Remainder (31) by 7 = 3

Number of odd days in Feb = Remainder (28) by 7 = 0

Number of odd days in Mar = Remainder (31) by 7 = 3

Number of odd days in Apr = Remainder (30) by 7 = 2

Number of odd days in May = Remainder (31) by 7 = 3

Number of odd days in Jun = Remainder (30) by 7 = 2

Number of odd days in Jul = Remainder (31) by 7 = 3

Therefore, Number of odd-days for 7 months = Remainder (3+0+3+2+3+2+3) by 7

 = Remainder (16) by 7

 = 2

So, Number of odd-days for 7 months = 2

• 15 days of August
  

Number of odd days for 15 days of August = Remainder (15) by 7

 = 1

So, Number of odd-days for 15 days of August = 1

We are very close to our final solution.

So, total number of odd-days from all 3 parts = Remainder (2+2+1) by 7

 = Remainder (5) by 7

 = 5

AND, if the number of odd-days is 5 then the day will be FRIDAY.

Checked from calendar, the day was indeed Friday!!!!! 

Cheers!!!