Donate to Remove ads

Got a credit card? use our Credit Card & Finance Calculators

Thanks to johnstevens77,Bhoddhisatva,scotia,Anonymous,Cornytiv34, for Donating to support the site

Ways

cinelli
Lemon Slice
Posts: 550
Joined: November 9th, 2016, 11:33 am
Has thanked: 231 times
Been thanked: 160 times

Ways

#266488

Postby cinelli » November 23rd, 2019, 10:54 am

The number 3 can be expressed as a sum of one or more positive integers in four ways, namely as 3, 1+2, 2+1 and 1+1+1. In how many ways can any positive integer n be expressed?

Cinelli

Gengulphus
Lemon Quarter
Posts: 4255
Joined: November 4th, 2016, 1:17 am
Been thanked: 2628 times

Re: Ways

#266597

Postby Gengulphus » November 23rd, 2019, 6:28 pm

cinelli wrote:The number 3 can be expressed as a sum of one or more positive integers in four ways, namely as 3, 1+2, 2+1 and 1+1+1. In how many ways can any positive integer n be expressed?

Spoiler...

The integer n can be expressed in 2^(n-1) ways. The proof is just to imagine a row of n objects (which I'll represent with asterisks) and with a possible fence (which I'll represent with "|") between each pair. There are n-1 possible fences, each of which might or might not exist independently of all the others, so there are 2^(n-1) possible patterns of fences. From any particular pattern of fences, I can create a sum of positive integers adding up to n by replacing a row of m asterisks without fences between them by m and fences by plus signs, and that transformation is fully reversible to transform a sum of positive integers adding up to n into such a row of objects and fences. So the number of sums of positive integers adding up to n is also 2^(2-1).

For example, for n=4:

* * * * corresponds to 4
* * *|* corresponds to 3+1
* *|* * corresponds to 2+2
* *|*|* corresponds to 2+1+1
*|* * * corresponds to 1+3
*|* *|* corresponds to 1+2+1
*|*|* * corresponds to 1+1+2
*|*|*|* corresponds to 1+1+1+1

Gengulphus

cinelli
Lemon Slice
Posts: 550
Joined: November 9th, 2016, 11:33 am
Has thanked: 231 times
Been thanked: 160 times

Re: Ways

#266811

Postby cinelli » November 24th, 2019, 5:36 pm

Congratulations, Gengulphus. That really is a very elegant solution.

Cinelli


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 11 guests