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

 

 

 

Dan

Dan

Blogger and a Math enthusiast. Has no interest in Mathematics until MMC came. Aside from doing math, he also loves to travel and watch movies.
Dan

Latest posts by Dan (see all)

You may also like...

5 Responses

  1. Linh says:

    Oh my goodness! an remarkable article dude. Thank you Having said that I’m experiencing problem with ur rss . Don’t know why Unable to subscribe to it. Is there any individual receiving identical rss difficulty? Any individual who knows kindly respond.

  2. I have read some good stuff here. Definitely value bookmarking for revisiting. I wonder how so much effort you put to create this sort of great informative website.

  3. pron best says:

    39bl0i Well I definitely liked reading it. This information offered by you is very constructive for proper planning.

  4. 148717 501664I needs to spend a while studying more or working out more. Thank you for great information I used to be looking for this information for my mission. 103952

  5. 87705 995899We clean up on completion. This could sound obvious but not a lot of a plumber in Sydney does. We wear uniforms and always treat your home or workplace with respect. 175653

Leave a Reply

Your email address will not be published.