## mathmath333 one year ago Counting problem

1. mathmath333

\large \color{black}{\begin{align} & \normalsize \text{Find the number of natural number solutions of.}\hspace{.33em}\\~\\ & a+2b+c=100 \hspace{.33em}\\~\\ \end{align}}

2. dan815

hmm okay

3. dan815

b can be all even numbers

4. dan815

do you know how to solve the simpler version of this problem a+b+c=100

5. mathmath333

do i need to change 2b to d

6. dan815

sry i mean 2b is all even numbers

7. mathmath333

99C2

8. dan815

yeah thats right

9. mathmath333

i meant to use substitution as 2b=d

10. dan815

here is another way u can think about it a+b+b+c = 100 how would you solve this a+b+c+d=100

11. mathmath333

99C3

12. dan815

i think you would solve a+b+c=100 and divide by 2

13. dan815

as all the odd possibilities would not possible

14. mathmath333

u mean 99C2/2

15. dan815

yeah but let me think that might not technically be true we dont know if odd and even solutions that add to 100 is exactly equal or not

16. mathmath333

How about calculatinb a+b1+b2+d=100 and substracting something

17. mathmath333

?

18. mathmath333

what do u mean

19. dan815

ok back

20. dan815

okay well maybe we can go back to the stars and bars method after this but i think we can do it with just sums

21. dan815

no wait there are 101 WAYs actually to add upto 100 when u pick 2b=0

22. dan815

|dw:1440274661135:dw|

23. dan815

does 0 count as natural number though?

24. mathmath333

No

25. Zarkon

sometimes...some define it to include 0 and others don't

26. anonymous

You could brute force it, write a python program to count it .

27. dan815

okay then lets subtract that out

28. mathmath333

0 is whole number

29. mathmath333

No pen paper method i need

30. Zarkon
31. dan815

|dw:1440274943096:dw|

32. dan815

2401

33. dan815

do you want to check with brute force

34. mathmath333

yea how do u brute force lol

35. dan815

tbh its just writing what i did up there in a code lol

36. dan815

i didnt really do it a very smart way summation is pretty bruteforcy

37. dan815

the answer is definately close to (99 choose 2)/2

38. dan815

because the odd + even combinations are not equal in this case there is going to be some fluctuation around that number

39. mathmath333
40. mathmath333

a short research shows a+2b+c=10--->4! ways a+2b+c=12--->5! ways a+2b+c=14--->6! ways Can i somehow get a pattern

41. dan815

@kainui can you see a way to do this problem combinatorically

42. anonymous

this would be the 'brute force' method Python code: count=0 for a in range(1,100): for b in range(1,100): for c in range(1,100): if a + 2*b+c ==100: count = count + 1 print count >>> 2401

43. mathmath333

yea 2401 is correct

44. anonymous

a+2b+c=10--->4! ways a+2b+c=12--->5! ways a+2b+c=14--->6! ways you can derive a pattern from this

45. mathmath333

\large \color{black}{\begin{align} & \normalsize \text{When a and c are even then}\hspace{.33em}\\~\\ & 2a'+2b+2c'=100\hspace{.33em}\\~\\ & \implies a'+b+c'=50\hspace{.33em}\\~\\ & \implies \dbinom{49}{2}\hspace{.33em}\\~\\ & \normalsize \text{When a and c are odd then}\hspace{.33em}\\~\\ & 2a'-1+2b+2c'-1=100\hspace{.33em}\\~\\ & \implies a'+b+c'=51\hspace{.33em}\\~\\ & \implies \dbinom{50}{2}\hspace{.33em}\\~\\ & \normalsize \text{Total}=\dbinom{49}{2}+\dbinom{50}{2}=2401\hspace{.33em}\\~\\ \end{align}}

46. mathmath333

that pattern was incorrect

47. anonymous

edit* actually the pattern should be a+2b+c=10--->4^2 ways a+2b+c=12--->5^2 ways a+2b+c=14--->6^2 ways you can derive a pattern from this a+2b+c=n--->(1/2*n -1)^2 ways

48. anonymous

when n = 100, 1/2*100 -1 = 49 and 49^2 = 2401

49. mathmath333

yea correct 49^2

50. anonymous

thats a nice solution you have so how do you know that a' + b + c ' = 50 has (49 choose 2 ) ways to find positive solutions

51. mathmath333

u have to use stars and bars method https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

52. anonymous

interesting :)

53. anonymous

For any pair of positive integers n and k, the number of k-tuples of positive integers whose sum is n is equal to the number of (k − 1)-element subsets of a set with n − 1 elements. we had 50 is the sum , and 3 tuples so that means 49 choose 2

54. anonymous

And then consider the case when a,b are both even or both odd. Note that a,c cannot be one even and one odd, because odd + even + even = odd

55. mathmath333

yep

56. mathmath333

the language given is wikipdia is technical , if u have any doubt u can go through stars and bars videos on youtubes

57. anonymous