At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
Solve this in front of me. And give me another example
okay umm lemme show u why i think this relation is important one
okay ill show u all my work so far, its not much lol
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
im looking at only the increasing case, and the decreasing case will be the same numbers
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
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
123 increasing 321 decreasing 456 inc 654 dec ( non bouncy) all )
yes that is correct
okay now lets move to the 9 digit case
here is where we can see the pattern
leets only look at the increasing for now
dont think about the decreasing its just a mirror and repeated
Yeah, you just turn left to right and so on.
okay umm wait this is important first
if u look at the 10 digit case
there is 1 difference between all the digits,
the sum of the difference have to add upto 9, and all of them have to be more than 0
so u can see there is no way to arrange the 1s to get anything new that tells us there is infact only 1
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
What do you mean by all of them have to be more than 0 ? why not 0 ?
which is 1, not 0 anymore, but anything more than 1 means we will fail
because if the difference is 0 then we have 1 1 1 1 1 which is bouncy
12345 all have diff 1 for their digits
following so far?
You mean the difference between the numbers can't be zero. Fine I understood all.
okay now look at this
The sum of difference 12345 is 4
so for the 9 digit case we know that 1 is the biggest number
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
when you pick 1, the difference have to add up to 8 and we have 8 places so everything is 1
but when you pick 0, the differences can add up to 9 and we have 8 places
But if we used 2, won't the number above 23456789--- will be bouncy if we added any other digit ?
yes that is why 2 is not possible
are u good upto here?
this is where the parition question starts
Yeah. But you must give me 1 or 2 easy questions as not to lose the info I gained.
okay i think we should just work on this simpler problem
a+b+c+d = k a
lets say K = 7
a+b+c+d=7 how many solutions are there to this? where a
Bouncy or non bouncy numbers ?
no this is just a separate question
you have to find hte number of integer solutions to that equation
Lol a = 0 , b = 1, c= 2 , d= 4 or a = 0 , b = 0 , c = 0 , d = 7 there is infinity. Clarify your aimbition
a = 4 ,b = 2, c = 1 ,d = 0
you have to find the number* of integer solutions
a+ b = 2 , a < b < solve this.
there is only 1 solution to that
oh and a b c d > 0 ofcourse
Ok .. because only when a = 2 But what about this a + b + c = 50 a < b
or equal to 0
yeah thats the question im asking u lol
50 is a big one try just 7 for now
Ok a = 4, b = 2, c = 1, d = 0 (1) a = 5, b= 2, c =1 , d= =0 Maybe 2 or so
i think a logical way to break this question down is to look at the differences
a+b+c=7 okay say a=0 this means we have a difference of 7 to distribute
Ok , so failed because it doesn't satisfy the condition.
0 , 1, 6 0,2,5 0,3,4 no other solutions with a = 0
hmm okay u think about it for a bit, i am gonna look at something
Damn -_- I saw the condition a > b > c >d
thats okay too same thing
But In your solution you made a = 0 and other number = 0 this is not possible you have broken the condition right ?
xD dont get caught on details lol
we need to work faster rn
Lol, details is important. But what about a+b+c+d = 10^9 won't I die before completing it ?
i found 11 increasing non bouncy numbers for digit 9 , im gonna work on 8 now
try this problem instead ditch the older one a + b+ c = 7 and a,b,c >0 and
so we are allowing the equal case now
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
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.
yes thats where i am right now
now instead of this, people have found a formula to do that counting for the number of solutions
which is our goal
AND YOU LEFT ME CALCULATING !!!!!!!!!!!!!!!!! >:(
But at least I learnt the basics :P
this stuff is an intro to something called paritioning theorems in mathematics
people have been working on approximations formulas for this count
approximations ? So answers are not accurate ?
the degree of error is quite low, so for the number we are dealing with the error will not effect it
What's that formula ?
in other words its like people are finding formulas that are able to solve higher and higher values for k a+b+c=k
i dont know, there are a lot apparently
okay but theres still work to be done here before the formula
there are more simpler ways to count
okay like take this case for 9 digit
the difference if you pick 0 as the start
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
the other 2 cases are when all the differences are 1 which gives us 2 more cases so a total of 9
now for the 8 digit case, we can use some combinatorics to count faster
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
and so on for 7
explain " there is one 2" we can have a 3 somewhere or a 2 somewhere
if u look at the differences
when u have 0 as a start
and we can have 2 and 2
how many ways to distribute 2, 2s in 8 positions
it would be 8*7/2
I am dumb lol. |dw:1435693617081:dw|
oops lol it should be 1 1, 2
And you didn't tell me where the 3 gone ?
what do u mean?
1 2 4 56789 ?
no look at the differences
we are trying to find the unique differences and see the number of permutatiosn each have
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
and that completes the case for a=0 for the 8 digit case
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
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
Give me simple exercise
find a nice solution to that and we will solve this whole quetion in like 0.0000000000001 computation time hehe
a+b+c=5 a,b,c>0 Total number of solutions = ?
hahahahahahahahahaaaaaaaaaaaa, Nice solution ? I am using dumbs way.
here is something that might be useful im not sure yet
if you take the 2nd differences we can allow 0 so this is great
then we can use a nice combinatorics trick
like look at this other question okay where we allow 0
a+b+c = 10 lets say
you can think of this problem like this think of the 10 as being 10 ones
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
will tell us total number of solutions
1 1 1 1+ 1 1 1 1+ 1 1 this is saying 4 + 4 + 2
Wait wait, here is my problem "put 2 signs to get unique solution"
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
I understood !
HAHAHAHA , I UNDERSTOOD Xd
Give me example fast I understood xD
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
You were explaining to me combinations and permutations ?
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
the solution to his, if its loonies must be
billion + 9999 choose 9999
1,000,000,000 P 10,000
not Permute but choose
but if u want to allow cents too then its ((billion*100 )+ 9999) choose 9999
But Permutations are right here ?
when we say chosoe and permute we are actually not thinking about permute and choosing
in your mind you know the formula you get and u just say was it a choose or permute
But how about the a+b+c+d = k ? I still can't think about it
okay so here is what im thinking about a way to solve this
When It was 7 you told me write them as 1111111 now 11+111+11 and calculate 2+3+2
wait i wanna work something out on paper first
Take your time.
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
I feeel like this will eventually lead to our own counting method for this whole thing
What did you find ? :>
okay okay look at this!! there is only 1 case we even need to lookat!
okay for example this one a+b+c=7 lets say and a,b,c>= 1
now we consider the simplst case
okay now here is what we do
now that 2nd difference can be solved with this method
5 choose 1 ways
so there msut be 5 solutions to this
let see if its right!
this gives us all the solutions for fixing first number
lets try a bigger example
i just need to deal with that first digit part lemme see about that one thing hmm
I must give you 100 medal for that work , awesome.
hahaha itss nothinngg
this stuff is very interestin :D i feel like we found something very neat!
Oh, before I forget. Dan are you good at partial integration ?
okay wait here is the bad part
we solved a slightly different problem
lol because 112233 is still classified as a increasing lmao
but this is kind of good because we found this really cool relationship!
ill change that question and post it ON OS, let other ppl try it!
As you like.