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.
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.
How many non-negative integral solutions of x+y+z=15?
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
where n= stars, k-1=bars, and k= distinguishable groups