Problem Solving

[roball]

I have to choose a +ve whole number and then write it as a SUM of +ve whole numbers.

eg 5 = 1 + 4 or 5 = 1 +1 + 3

I then have to investigate the number of possible ways of writing the numbers from 1 to 10 by summing other positive whole numbers.

So I started

1 = 1 ( cannot use 0)
2 = 1 + 1
3 = 1 + 1 + 1, 1 + 2
4 = 1 + 1 + 1 + 1, 1 + 1 +2, 1 + 3, 2 + 2, 3 + 1
........ and so on

I can see a lot of time compiling the table as the numbers grow and I might miss a combination or two.

Is there a formula that will allow me to correctly work out all the combinations or will I have to burn the midnight candle?

 

[Yogi]

Your result so far is inconsistent. For 3 you have 1+2 only and not 2+1, for 4 you use 1+3 AND 3+1. Which one is it?

 

[roball]

Your result so far is inconsistent. For 3 you have 1+2 only and not 2+1, for 4 you use 1+3 AND 3+1. Which one is it?

The problem given to me does not stipulate that I can use both forms ie It does not say I can/cannot use 3 + 1 AND 1 + 3.

I found the problem given to me by the teacher very confusing.

 

[Deleted member 4993]

I have to choose a +ve whole number and then write it as a SUM of +ve whole numbers.

eg 5 = 1 + 4 or 5 = 1 +1 + 3

I then have to investigate the number of possible ways of writing the numbers from 1 to 10 by summing other positive whole numbers.

So I started

1 = 1 ( cannot use 0)
2 = 1 + 1
3 = 1 + 1 + 1, 1 + 2
4 = 1 + 1 + 1 + 1, 1 + 1 +2, 1 + 3, 2 + 2, 3 + 1
........ and so on

I can see a lot of time compiling the table as the numbers grow and I might miss a combination or two.

Is there a formula that will allow me to correctly work out all the combinations or will I have to burn the midnight candle?

Yes there is a formula. But I think the idea of the task is that you investigate the pattern and come up with your conjecture.

Regarding, whether you can use ONLY '1 +3' or you are allowed to consider BOTH '1+3' and '3+1' - you can make up your rule. However, once you made it - you are not allowed to use different rule for different parts of the problem. That is choose whether you are going to use 'ONLY' or 'BOTH' and stick to it. If I were to do this problem - I would try the 'ONLY' method first.

 

[roball]

Thanks for suggestion.

I will stick to ONLY then and forget the AND bit.

If I only draw up a chart from 1 to 5, will that be enough to give me a clue as to the pattern and hence remove the need to do ALL the numbers from 1 to 10?

I am a bit pressed for time.

 

[Yogi]

I would only include 1+3 and not 3+1 since it turns out to be much less work -_-

This might help you stay organized.
Omitting the +'s to type it faster as well as being easier on the eyes.

1: you said cannot use 0 so 1+0 doesnt work.
2: 11
3: 111, 12

4: 13 1111 112 (at this point I first write 13 and 22 on the left, replace 3 with the results from above)
22 211 (this one is a repeat so cross it out)

5: 14 113 11111 1112 122 (again I write 14 and 23 first then replace 4 with the results from 4 above)
23 2111 212

6: 15 114 1113 111111 11112 1122 123(write 15 24 and 33 first, then replace 5 with the results above)
24 213 21111 2112 222
33 3111 312
etc...
So far the count is 0,1,2,4,6,10 almost Fibbonaci-like but not quite...my gut tells me that this is solve by brute force and with some minor manipulation you can check your answers here: http://en.wikipedia.org/wiki/Partition_%28number_theory%29

Yes there is a formula.

I don't think it's anything easy enough for the Arithmetic forums.

 

[soroban]

Hello, roball!

I have to choose a +ve whole number and then write it as a SUM of +ve whole numbers.

e.g. 5 = 1 + 4 or 5 = 1 +1 + 3

I then have to investigate the number of possible ways of writing the numbers from 1 to 10
by summing other positive whole numbers.

So I started

1 = 1 ( cannot use 0)
2 = 1 + 1
3 = 1 + 1 + 1, 1 + 2
4 = 1 + 1 + 1 + 1, 1 + 1 +2, 1 + 3, 2 + 2, 3 + 1
........ and so on

I can see a lot of time compiling the table as the numbers grow and I might miss a combination or two.

Is there a formula that will allow me to correctly work out all the combinations
or will I have to burn the midnight candle?

If the order of the terms is important, there is a simple formula.


Consider \(\displaystyle n = 3.\)
. . \(\displaystyle \begin{Bmatrix}1,1,1\end{Bmatrix} \quad \begin{Bmatrix}1,2 \\ 2,1 \end{Bmatrix}\)
. . 3 cases.


Consider \(\displaystyle n = 4.\)
. . \(\displaystyle \begin{Bmatrix}1,1,1,1 \end{Bmatrix}\quad \begin{Bmatrix}1,1,2 \\ 1,2,1 \\ 2,1,1 \end{Bmatrix} \quad \begin{Bmatrix}1,3 \\ 3,1 \end{Bmatrix} \quad \begin{Bmatrix}2,2 \end{Bmatrix}\)
. . 7 cases.


Consider \(\displaystyle n = 5.\)
. . \(\displaystyle \begin{Bmatrix}1,1,1,1,1 \end{Bmatrix} \quad \begin{Bmatrix}1,1,1,2 \\ 1,1,2,1 \\ 1,2,1,1 \\ 2,1,1,1 \end{Bmatrix} \quad \begin{Bmatrix}1,1,3 \\ 1,3,1 \\ 3,1,1 \end{Bmatrix} \quad
\begin{Bmatrix}1,2,2\\2,1,2 \\ 2,2,1 \end{Bmatrix} \quad \begin{Bmatrix}1,4 \\ 4,1 \end{Bmatrix} \quad \begin{Bmatrix}2,3 \\ 3,2 \end{Bmatrix}\)
. . 15 cases.


The number of cases seem to be one less than a power of two.
Why is this so?


Consider a six-inch board, marked off in one-inch intervals.

. . \(\displaystyle \square\!\square\!\square\!\square\!\square\! \square \)

In how many ways can we cut on the five interior lines?

For each line we have two choices: cut or do not cut.

Hence, the number of ways is: \(\displaystyle 2^5 = 32\)

But this includes the case when we do not cut anywhere.
. . So we have a solid six-inch board.

Since this is not allowed, there are: \(\displaystyle 2^5 - 1 \,=\,31\) ways.


In general, with an \(\displaystyle n\)-inch board, there are: .\(\displaystyle 2^{n-1} - 1\) ways.


~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~


If we disregard the ordering, the problem is more complex.
. . That is: \(\displaystyle \{1,1,3\},\:\{1,3,1\},\:\{3,1,1\}\) are considered equivalent.
It is easier to use brute-force Listing.

I'm familiar with this problem due to an innocent question asked
. . by my (then) wife about 30 years ago.

She taught severely retarded children and was making up arithmetic exercises.
She asked "How many ways can we add whole numbers and get a sum of five?"
I did some scribbling and came up with the formula given above.

Then she asked "What if we don't consider the order?"
After an hour of scribbling, I found that the numbers grew larger (of course),
. . but there was no discernable pattern.

The next day, I gave the problem to my colleagues.
Only three of us got "hooked" on the problem.
We worked on it (on and off) for a few months.
We had tables and charts, filled with numbers.
We found some quasi-recurrence relations
. . but nothing that worked.

I finally wrote to Martin Gardner and asked his advice.
He referred me to a particular book and mentioned that
the problem was solved in the 1930's (virtually yesterday!).
I finally located the book in the Boston Public Library.
The formula is one of the most complicated I've ever seen.
There is a recurrence relation, but it is quadratic in form.

Since you're working with a maximum of \(\displaystyle n = 10\),
. . I recommend making a List (carefully).


Edit: I corrected my omission in n = 5.

 

[Yogi]

eg 5 = 1 + 4 or 5 = 1 +1 + 3

If the order of the terms is important, there is a simple formula.

Consider \(\displaystyle n = 5.\)
. . \(\displaystyle \begin{Bmatrix}1,1,1,1,1 \end{Bmatrix} \quad \begin{Bmatrix}1,1,1,2 \\ 1,1,2,1 \\ 1,2,1,1 \\ 2,1,1,1 \end{Bmatrix} \quad \begin{Bmatrix}1,1,3 \\ 1,3,1 \\ 3,1,1 \end{Bmatrix} \quad \begin{Bmatrix}1,4 \\ 4,1 \end{Bmatrix} \quad \begin{Bmatrix}2,3 \\ 3,2 \end{Bmatrix}\)
. . 15 cases.

Although that was a neat wall of text, the OP uses 5=1+1+3 in an example so adding 3 numbers is possible. Where is 5=2+2+1? I think you are oversimplifying the problem a bit. It is an integer partition with no obvious pattern, but does have a generating function by Euler that I think is beyond the scope of this course.

 

[roball]

Thanks to all for your help. I had no idea that the solution was quite so complicated.

I think as a math problem for a 13 year old, the teacher is being too optimistic.

 

[lookagain]

I have to choose a >> +ve <<

whole number and then write it as a SUM of >> +ve <<

whole numbers.

Recommendation:

Please do not type "ve."

I could read that as "positiveve" or "plusve," as there is some partial
redundancy.

I would suggest typing out "positive," or possibly an abbreviation, "pos."


That is along the lines of when people type "1/3rd." There's partial
redundancy there as well.

"1/3" already means (and is read as) "one-third."