## dan815 one year ago a+b+c+d = k a<b<c<d everything is an integer can you find the number of solutions as a function of K

1. dan815

@TrojanPoem

2. TrojanPoem

Solve this in front of me. And give me another example

3. dan815

okay umm lemme show u why i think this relation is important one

4. dan815

okay ill show u all my work so far, its not much lol

5. TrojanPoem

:)

6. dan815

okay so i started working backwards, now i allowed 0 to be in the first place of the digit, we can take care of the problems of that later on

7. dan815

im looking at only the increasing case, and the decreasing case will be the same numbers

8. dan815

so for 10 digit numbers we have 1 non bouncy number that is strictly increasing 0123456789 and 1 non bouncy number that is strickly decreasing 9876543210

9. dan815

if there were 2 strickly increasing then there have to be 2 strictly decreasing so you can see why we only care about one half

10. TrojanPoem

123 increasing 321 decreasing 456 inc 654 dec ( non bouncy) all )

11. dan815

yes that is correct

12. dan815

okay now lets move to the 9 digit case

13. dan815

here is where we can see the pattern

14. TrojanPoem

123456789 987654321

15. dan815

leets only look at the increasing for now

16. TrojanPoem

Ok.

17. dan815

dont think about the decreasing its just a mirror and repeated

18. TrojanPoem

Yeah, you just turn left to right and so on.

19. dan815

okay umm wait this is important first

20. dan815

if u look at the 10 digit case

21. dan815

|dw:1435690693214:dw|

22. dan815

there is 1 difference between all the digits,

23. dan815

the sum of the difference have to add upto 9, and all of them have to be more than 0

24. dan815

so u can see there is no way to arrange the 1s to get anything new that tells us there is infact only 1

25. dan815

now if u look at the 9 digit, case we have 8 difference now there is a max number we can pick for the first place

26. TrojanPoem

What do you mean by all of them have to be more than 0 ? why not 0 ?

27. dan815

which is 1, not 0 anymore, but anything more than 1 means we will fail

28. dan815

because if the difference is 0 then we have 1 1 1 1 1 which is bouncy

29. dan815

12345 all have diff 1 for their digits

30. dan815

following so far?

31. TrojanPoem

You mean the difference between the numbers can't be zero. Fine I understood all.

32. dan815

okay now look at this

33. TrojanPoem

The sum of difference 12345 is 4

34. dan815

|dw:1435690935221:dw|

35. dan815

so for the 9 digit case we know that 1 is the biggest number

36. dan815

now if you pick 1, then all the following differences have to be 1, so we know starting with 1 there is only 1 number 123456789

37. dan815

when you pick 1, the difference have to add up to 8 and we have 8 places so everything is 1

38. dan815

but when you pick 0, the differences can add up to 9 and we have 8 places

39. TrojanPoem

But if we used 2, won't the number above 23456789--- will be bouncy if we added any other digit ?

40. dan815

yes that is why 2 is not possible

41. dan815

are u good upto here?

42. dan815

this is where the parition question starts

43. TrojanPoem

Yeah. But you must give me 1 or 2 easy questions as not to lose the info I gained.

44. dan815

okay i think we should just work on this simpler problem

45. dan815

a+b+c+d = k a<b<c<d everything is an integer can you find the number of solutions as a function of K

46. dan815

lets say K = 7

47. dan815

a+b+c+d=7 how many solutions are there to this? where a<b<c<d

48. TrojanPoem

Bouncy or non bouncy numbers ?

49. dan815

no this is just a separate question

50. dan815

you have to find hte number of integer solutions to that equation

51. TrojanPoem

Lol a = 0 , b = 1, c= 2 , d= 4 or a = 0 , b = 0 , c = 0 , d = 7 there is infinity. Clarify your aimbition

52. dan815

a<b<c<d is a condition

53. TrojanPoem

Oh

54. TrojanPoem

a = 4 ,b = 2, c = 1 ,d = 0

55. dan815

you have to find the number* of integer solutions

56. TrojanPoem

a+ b = 2 , a < b < solve this.

57. dan815

there is only 1 solution to that

58. dan815

oh and a b c d > 0 ofcourse

59. TrojanPoem

Ok .. because only when a = 2 But what about this a + b + c = 50 a < b <c

60. dan815

or equal to 0

61. dan815

yeah thats the question im asking u lol

62. dan815

50 is a big one try just 7 for now

63. TrojanPoem

Ok a = 4, b = 2, c = 1, d = 0 (1) a = 5, b= 2, c =1 , d= =0 Maybe 2 or so

64. dan815

i think a logical way to break this question down is to look at the differences

65. dan815

a+b+c=7 okay say a=0 this means we have a difference of 7 to distribute

66. TrojanPoem

Ok , so failed because it doesn't satisfy the condition.

67. dan815

0 , 1, 6 0,2,5 0,3,4 no other solutions with a = 0

68. dan815

hmm okay u think about it for a bit, i am gonna look at something

69. TrojanPoem

Damn -_- I saw the condition a > b > c >d

70. dan815

thats okay too same thing

71. TrojanPoem

But In your solution you made a = 0 and other number = 0 this is not possible you have broken the condition right ?

72. dan815

xD dont get caught on details lol

73. dan815

we need to work faster rn

74. TrojanPoem

Lol, details is important. But what about a+b+c+d = 10^9 won't I die before completing it ?

75. TrojanPoem

are*

76. dan815

i found 11 increasing non bouncy numbers for digit 9 , im gonna work on 8 now

77. dan815

try this problem instead ditch the older one a + b+ c = 7 and a,b,c >0 and

78. dan815

so we are allowing the equal case now

79. TrojanPoem

Ok first a =0 b + c = 7 b = 0 c = 7 b =2 c = 5 b = 1 c = 6 b = 3 c = 4 b = 4 c = 3 b = 5 c = 2 b = 6 c = 1 Ok I got it , but still there is a lot a lot a lot of solutions

80. TrojanPoem

I got a scheme on how to do it first a = 0 b +c = 7 ( b from 0 to 7) and calculate c then a = 1 b+c = 6 (b from 0 to 6) and calculate c ... until the end.

81. dan815

yes thats where i am right now

82. dan815

now instead of this, people have found a formula to do that counting for the number of solutions

83. dan815

which is our goal

84. TrojanPoem

AND YOU LEFT ME CALCULATING !!!!!!!!!!!!!!!!! >:(

85. TrojanPoem

But at least I learnt the basics :P

86. dan815

this stuff is an intro to something called paritioning theorems in mathematics

87. dan815

people have been working on approximations formulas for this count

88. TrojanPoem

approximations ? So answers are not accurate ?

89. dan815

the degree of error is quite low, so for the number we are dealing with the error will not effect it

90. TrojanPoem

What's that formula ?

91. dan815

in other words its like people are finding formulas that are able to solve higher and higher values for k a+b+c=k

92. dan815

i dont know, there are a lot apparently

93. dan815

okay but theres still work to be done here before the formula

94. dan815

there are more simpler ways to count

95. TrojanPoem

Like ?

96. dan815

okay like take this case for 9 digit

97. dan815

the difference if you pick 0 as the start

98. dan815

are 1,1,1,1,1....,2 there is one of 2 that means there are 9 ways with a dfference of 2 and all 1s

99. dan815

the other 2 cases are when all the differences are 1 which gives us 2 more cases so a total of 9

100. dan815

now for the 8 digit case, we can use some combinatorics to count faster

101. dan815

for a starting value of 1 we have 8 cases for a starting value of 0 we can have a 3 somewhere or a 2 somewhere so 16 more ways from that

102. dan815

and so on for 7

103. TrojanPoem

explain " there is one 2" we can have a 3 somewhere or a 2 somewhere

104. dan815

if u look at the differences

105. dan815

when u have 0 as a start

106. dan815

|dw:1435693429832:dw|

107. dan815

and we can have 2 and 2

108. dan815

how many ways to distribute 2, 2s in 8 positions

109. dan815

it would be 8*7/2

110. TrojanPoem

I am dumb lol. |dw:1435693617081:dw|

111. dan815

oops lol it should be 1 1, 2

112. dan815

|dw:1435693673194:dw|

113. TrojanPoem

And you didn't tell me where the 3 gone ?

114. dan815

what do u mean?

115. TrojanPoem

1 2 4 56789 ?

116. dan815

no look at the differences

117. dan815

we are trying to find the unique differences and see the number of permutatiosn each have

118. dan815

there is 1 way to arrange all 1s there are 8 ways to arrange one 2 and rest 1 there are 8 ways to arrange one 3 and rest 1 there are 8*7/2 ways to arrange two 2s and rest 1

119. dan815

and that completes the case for a=0 for the 8 digit case

120. dan815

for a=1 there are 8+1 way for a=2 there is 1 way so a total of 1+8+8+8*7/2+9+1= eight digit CASE

121. dan815

so everything is basic computation including the combinatorics we can make computer do, the one part we need to figure out is the unique solutions

122. TrojanPoem

Give me simple exercise

123. TrojanPoem

a simple*

124. dan815

a+b+c=5 a,b,c>0

125. dan815

find a nice solution to that and we will solve this whole quetion in like 0.0000000000001 computation time hehe

126. dan815

a+b+c=5 a,b,c>0 Total number of solutions = ?

127. TrojanPoem

hahahahahahahahahaaaaaaaaaaaa, Nice solution ? I am using dumbs way.

128. dan815

here is something that might be useful im not sure yet

129. dan815

if you take the 2nd differences we can allow 0 so this is great

130. dan815

then we can use a nice combinatorics trick

131. dan815

like look at this other question okay where we allow 0

132. dan815

a+b+c = 10 lets say

133. dan815

you can think of this problem like this think of the 10 as being 10 ones

134. TrojanPoem

|dw:1435694528337:dw|

135. dan815

1 1 1 1 1 1 1 1 1 1 and the number of places we can put 2 plus signs to get unique solution

136. dan815

will tell us total number of solutions

137. dan815

1 1 1 1+ 1 1 1 1+ 1 1 this is saying 4 + 4 + 2

138. TrojanPoem

Wait wait, here is my problem "put 2 signs to get unique solution"

139. dan815

there are a total of 12 spots if u count the 1s and + sign as spots so that means 12 choose 2 are the total number of integer solutiosn to a+b+c = 10

140. TrojanPoem

I understood !

141. TrojanPoem

HAHAHAHA , I UNDERSTOOD Xd

142. TrojanPoem

Give me example fast I understood xD

143. dan815

this is a useful result, now u can answer questions like say you and 2 friends have 10 dollars and only loonies allwoed now u know the total number of ways your money can be split

144. TrojanPoem

You were explaining to me combinations and permutations ?

145. dan815

or something with a huge solution but u can atleast get an expression for it, like a billion dollars is in a town of 10,000 people, you can now answer the total number of ways this money can be split between the people

146. dan815

the solution to his, if its loonies must be

147. dan815

billion + 9999 choose 9999

148. TrojanPoem

1,000,000,000 P 10,000

149. dan815

not Permute but choose

150. dan815

but if u want to allow cents too then its ((billion*100 )+ 9999) choose 9999

151. TrojanPoem

But Permutations are right here ?

152. dan815

when we say chosoe and permute we are actually not thinking about permute and choosing

153. dan815

in your mind you know the formula you get and u just say was it a choose or permute

154. TrojanPoem

But how about the a+b+c+d = k ? I still can't think about it

155. dan815

okay so here is what im thinking about a way to solve this

156. TrojanPoem

When It was 7 you told me write them as 1111111 now 11+111+11 and calculate 2+3+2

157. dan815

wait i wanna work something out on paper first

158. TrojanPoem

159. dan815

hey man I think I found something very interseting :O but im not quitee sure yet what to do with it!! but taking a look at the 2nd difference is very very very very very interseting

160. dan815

I feeel like this will eventually lead to our own counting method for this whole thing

161. TrojanPoem

What did you find ? :>

162. dan815

okay okay look at this!! there is only 1 case we even need to lookat!

163. dan815

okay for example this one a+b+c=7 lets say and a,b,c>= 1

164. dan815

now we consider the simplst case

165. dan815

1+1+5

166. dan815

okay now here is what we do

167. dan815

|dw:1435695479325:dw|

168. dan815

now that 2nd difference can be solved with this method

169. dan815

5 choose 1 ways

170. dan815

so there msut be 5 solutions to this

171. dan815

let see if its right!

172. dan815

|dw:1435695530619:dw|

173. dan815

this gives us all the solutions for fixing first number

174. dan815

lets try a bigger example

175. dan815

|dw:1435695642003:dw|

176. dan815

i just need to deal with that first digit part lemme see about that one thing hmm

177. TrojanPoem

I must give you 100 medal for that work , awesome.

178. dan815

hahaha itss nothinngg

179. dan815

this stuff is very interestin :D i feel like we found something very neat!

180. TrojanPoem

:D

181. TrojanPoem

Oh, before I forget. Dan are you good at partial integration ?

182. dan815

okay wait here is the bad part

183. dan815

we solved a slightly different problem

184. dan815

lol because 112233 is still classified as a increasing lmao

185. TrojanPoem

Oo

186. dan815

but this is kind of good because we found this really cool relationship!

187. dan815

ill change that question and post it ON OS, let other ppl try it!

188. TrojanPoem

As you like.