Question

Let n1 11 years ago

Answer 1

like u wanna find these numbers ?

Answer 2

very interesting question xD

Answer 3

1+2+3+4+10
2+3+4+5+6
hmm

Answer 4

@ganeshie8 check this question :O

Answer 5

@ikram002p this problem is very interesting and it is not that simple. we need method.

Answer 6

ikr :P
i was just thinking only

Answer 7

There is a method. Look up something called "Stars and Bars". This is a very well known combinatorics problem.

Answer 8

If we were looking at $$n_1+n_2+n_3+n_4+n_5=20$$where the \(n_i\ge 0\) (or non-negative, not exactly what our problem says, but close), then the way to see the answer is as follows. Consider the 20 as ones just standing next to each other: $$11111111111111111111.$$Now I'm going to place 4 \(+\)'s into the ones anywhere I want. One example is: $$1111+11111+1+11+11111111=4+5+1+2+8$$This is one particular solution to the equation. Another solutions is: $$+++11111+111111111111111=0+0+0+5+15$$This is another solution. You can probably see from here that every solution to the equation can be represented by counting how many ways there are to rearrange the 20 ones and 4 plus signs.

Answer 9

but see conditions , they are ordered u cant take 0+0+0+5+15

Answer 10

Right, thats why we have to tweak the technique of stars and bars a little.

Answer 11

oh go ahead keep going :)

Answer 12

hmm not sure how stars and bars really helps here

Answer 13

Maybe it doesn't =/

Answer 14

lets do it for 2 and 8 and see if get something

Answer 15

well maybe we can started like this
0+1+2+3+14
0+1+2+4+13
0+1+2+5+12
0+1+2+6+11
0+1+2+7+10
0+1+2+8+9
0+1+3+4+12
0+1+3+5+11
0+1+3+6+10
0+1+3+7+9
0+1+4+5+10
0+1+4+6+9
0+1+4+7+8
lol long list -.-

Answer 16

@nerdguy2535 continue with star and bar :O

Answer 17

okay

Answer 18

does that mean the answer should be 2^5 ?

Answer 19

I think you are right. Stars and bars might be too hard to tweak to the setting \(n_1<n_2<n_3<n_4<n_5.\) I'm looking in my combinatorics book atm. There is a formula for this problem, but its based on generating functions, and because 20 is so large its a little rough to actually get the answer.

Answer 20

hmm ok im gonna try to give all combination
i think only 36 if im lucky enough xD

Answer 21

1+2+3+4+10
1+2+3+5+9
1+2+3+6+8
1+2+4+5+8
1+2+4+6+7
1+3+4+5+7
2+3+4+5+6

Answer 22

i see like a decreasing sequence pattern

Answer 23

shud be some kind of summing series problem in the end we shud get a concise form for how its decreasing

Answer 24

the biggest constraint is the min value like ikky start with 0

Answer 25

" be positive integers"

Answer 26

see how for eve its 6, then odd its 4 then 3
notice the 4 came up instead of 5 because 8,8 spit was not possible

Answer 27

there are 7...I listed them

Answer 28

oh so we should start from 1 ?

Answer 29

there shud be a pattern emerging like for starting at 1, maybe its everything -1

Answer 30

or -2 in some cases dependning on dd or even change

Answer 31

have to work out for a smaller problem or a couple more numbers just to see it all i dont have paper or anything sooo -.-

Answer 32

nvm lol
its start from 1 :)
so only 7 xD

Answer 33

ok thats the patternn

Answer 34

i wish they had this fancy internet when i was a wee lad
i would have 7 PhDs by now
see #51 for a worked out solution

Answer 35

ya lol xD kinda silly shudda seen once u put in 2 its too much

Answer 36

so it seems the #of solutions for below 3 equations is same :

\[\large n_1 + n_2 + n_3 + n_4 + n_5 = 20 \tag{1}\]
\[\large n_1 + n_2 + n_3 + n_4 + n_5 = 10 \tag{2}\]
\[\large n_1 + n_2 + n_3 + n_4 + n_5 = 5 \tag{3}\]

Answer 37

nice :) so its 7 xD

Answer 38

now lets write a matlab code for this

Answer 39

to solve for 10 partitions and 1000 sum

Answer 40

ill race you >_>

Answer 41

i dont have the program on my laptop :'(
i would be faster than u xd

Answer 42

suureee

Answer 43

then use scilab or octave

Answer 44

or java, c++, c#.... ;)

Answer 45

oh ya ikky there is matlab excecutor right here

Answer 46

wait c++ i think i have borland or something
gimme link dan

Answer 47

http://www.compileonline.com/execute_matlab_online.php

Answer 48

This question is puzzling even the best on OS...

Answer 49

I'll wait to see if it actually gets solved....(-:

Answer 50

it has been solved for a while now

Answer 51

just writing a code

Answer 52

ramananjuns solution though is O_O

Answer 53

really pretty

Answer 54

yeah not possible to bruteforce dan, you need to use/invent some sensible algorithm

im getting avagadro number for your problem : sum=1000,partitions=10
http://www.wolframalpha.com/input/?i=1000+choose+10

Answer 55

why ?

Answer 56

how do u know they are ordered :O

Answer 57

its not 1000 choose 10 though

Answer 58

ordering is not a problem because you can always sort a given a list of 10 distinct integers.

\(\large \binom{1000}{10}\) is the number of ways of picking 10 distinct intgers from the first 1000 positive integers. we fail miserably if we try to brute force this because no computer can ever finish executingyour program

Answer 59

http://prntscr.com/51yc4e look at this we are to reduce to this form with 1000 and 10 parttions now

Answer 60

do u get how simplfied the problem to be partitions like this

Answer 61

lol i had problem with excuting this though xD

Answer 62

we can reduce 1000 to 965
further it reduces to 955. thats the end.

Answer 63

oh

Answer 64

i don't think we can deal 955 choose 10

Answer 65

i see a more realistic problem would be
10 and 50 then?
or better reducton with
100 and 500

Answer 66

100 = partitions, 500 = sum right ?

Answer 67

yes

Answer 68

sorry not possible !

Answer 69

xD

Answer 70

100 and 500 is easy
0 solutions :)

Answer 71

ya haha

Answer 72

umm (100*101)/2 + 500 then

Answer 73

wait that is also no good thats only 1 solution i think

Answer 74

okay wait, can we talk about his steps though, how did he reduce this problem to

Answer 75

those 7 tuples in the end

Answer 76

(5), (1,4) ,( 2,3)....(1,1,1,1,1)

Answer 77

he created a bijection between sequences of "Strictly increasing positive integers" and "monotonically increasing positive integers"

Answer 78

4, 10 (6-1)
5 9 (1 , 5-1)
6, 8 (2, 4-1)
4, 5 , 8 (1,1,3)

Answer 79

what is a bijection

Answer 80

so suppose the sum was 21 instead itd be
6
1 5
2 4
3 3
1 2 3
1 1 1 3
1 1 2 2
1 1 1 2
1 1 1 1 1

9 arrangements?

Answer 81

bijection associates each solution for sum=20 with a unique solution for sum=10

Answer 82

however sum=20 is strictly increasing and sum=10 is just nondecreasing

Answer 83

cuz the other one is already based off differences right

Answer 84

as long as equal or greater difference exists we are fine, when there is an even separation there must be a strictly decreasing when its odd separation it can be equal

Answer 85

yes i think you're right.

consider strictly increasing sequence : 1, 5, 6
after subtracting you get : 1, 4, 4

Answer 86

This is the way I thought of solving this - since the terms are increasing, then we can write the 5 terms as:\[d_0,d_0+d_1,d_0+d_1+d_2,d_0+d_1+d_2+d_3,d_0+d_1+d_2+d_3+d_4\]where \(d_i\gt0\). Then using the restriction on the sum of these numbers we get:\[5d_0+4d_1+3d_2+2d_3+d_4=20\]The minimum value for \(d_1\), \(d_2\), \(d_3\) and \(d_4\) is \(1\), which implies the maximum value for \(d_0\) is \(2\).
We therefore end up with two equations:\[5.2+4d_1+3d_2+2d_3+d_4=20\tag{1}\]\[5.1+4d_1+3d_2+2d_3+d_4=20\tag{2}\]For equation (1), the only solution is where each unknown is equal to \(1\), i.e.:\[5.1+4.1+3.1+2.1+1=20\]For equation (2) we first set \(d_1\), \(d_2\) and \(d_3\) to their minimum value of \(1\) to get \(d_4=6\), i.e.:\[5.1+4.1+3.1+2.1+6=20\]Now we just need to distribute this \(6\) amongst \(d_1\), \(d_2\) and \(d_3\) to get:\[5.1+4.1+3.1+2.2+4=20\]\[5.1+4.1+3.1+2.3+2=20\]\[5.1+4.1+3.2+2.1+3=20\]\[5.1+4.1+3.2+2.2+1=20\]\[5.1+4.2+3.1+2.1+2=20\]That gives us \(7\) solutions in total.

Answer 87

I don't know if this is a strict solution or not or even if it is the correct solution but I thought I'd put down my thoughts on this.

Answer 88

"so suppose the sum was 21 instead itd be
6
1 5
2 4
3 3
1 2 3
1 1 1 3
1 1 2 2
1 1 1 2
1 1 1 1 1

9 arrangements?"

1 1 4

Answer 89

ah right

Answer 90

I do not believe there is a closed form solution to this problem

Answer 91

*this type of problem

Answer 92

@Zarkon - what method did you use to get the solution?

Answer 93

I just listed the possible sums

1+2+3+4+10
1+2+3+5+9
1+2+3+6+8
1+2+4+5+8
1+2+4+6+7
1+3+4+5+7
2+3+4+5+6

Answer 94

then I counted ;) there are 7 :)

Answer 95

fair enough :)

Answer 96

if it was much larger one would probably need to write some computer code

Answer 97

i tried to code dan question xD
but seems i had dumb code , dint execute

my idea was like this
1- give all possibles values for each number from 1 to 1000
2- finding sum for all different combination
3- check if values are distance + sum =1000
4- give count of match + output them xD