Micah’s Non-negative Integral Solution

I am a native of Samar, I’m only in Cebu to finish my college. I’m currently taking up Bachelor of Science in Mechanical Engineering. I was not born a math genius so I struggled in my high school, but I never quit. I just practiced more, because I always believed that there are two kinds of geniuses, the ones who are born with it and the ones who are made.  Originally, I love physics more than math, but when my teacher discovered my potential and chose me for MMC when I was in third year, I got interested in math and I realized that I can also improve in math as I am in physics. Now, I love Math more than physics“, said Micah B. Arceño. He is quizzer in their school at University of Cebu. Here are some of his achievements.

micah

MMC gold medalist third year high school , Samar Division

CESAFI Math Quiz (Cebu) 2014 – 1st Runner up

Mathalino Casio 2014 –  VisMin Region – 1st Runner up

MTAP Tertiary Level 2014 (VisMin Region) (Individuals)- 3rd Runner up

MTAP Tertiary Level 2014 (VisMin Region) (Team)-2nd Runner up

PSME Regional Mechanical Engineering Quizbowl 2013 – 1st Runner up

PSME National Mechanical Engineering Quizbowl  2013 –  Champion

He wanted to share this problem with us about algebra but requires principle of constructive counting to solve.

Problem: 

How many  non-negative integral solutions of x+y+z=15?

Solution:

You can always attack this problem by constructive counting but I like to solve this using stars and bars method by letting x,y,z be the groups, and the sum being the stars. Since the problem considers non negative integers we have to consider 0.

So, by stars and bars

★ | ★ ★ ★ | ★ ★ ★ ★ ★ ★  ★ ★ ★ ★ ★   (1,3,11) is one solution  – (diagram 1)

| ★ ★ ★ ★ ★| ★ ★ ★ ★ ★  ★ ★ ★ ★ ★   (0,5,10) is also one solution –  (diagram 2)

★ ★ ★ ★ ★ ★ ★ ★ ★ ★  ★ ★ ★ ★ ★| | (15, 0,0 ) is also another solution – (diagram 3)

We observe that the number of ways to represent 15 as the sum of 3 positive integers is just the number of ways to choose 2 locations where to put the bars out of the 14 space between the stars of the 1st diagram. So, 14C2 = 91

Now , if 1 of groups is zero, then the number of ways  will be just the number of ways to choose a location where to put a bar out of the 14 spaces between the stars and then multiplied by 3 because there are 3 groups. So,3(14C1)= 42 (notice diagram 2)

Lastly if 2 groups are zero then there are only 3 possible ways to represent 15 as the sum of these 3 groups. (notice diagram 3)

Therefore the total number of non-negative integral solutions of x+y+z=15 ,is

91+42+3 = 136

Also using the formula for stars and bars directly    

{n+k-1\choose k-1} where n= stars, k-1=bars, and k= distinguishable groups

{15+3-1\choose 3-1}={17\choose 2}=136

 

 

 

You may also like...

Leave a Reply

Your email address will not be published.

Protected by WP Anti Spam