All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Rumor Rithmetic (Posted on 2008-04-25)
You start a rumor by telling it to n people and each of them tells it to another n-1 people. If each of these people, in turn, tells the rumor to another n-2 people, and so forth with no person hearing the rumor from more than one source, find a closed-form expression (in terms of n) for the total number of people that have been told the rumor.

 No Solution Yet Submitted by Dennis Rating: 2.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer aided solution (spoiler) | Comment 1 of 3

The following program keeps track of how many people are told in each generation of tellees (gen = previous generation size times the reduced number from n), and the overall number of people who have been told (told).

CLS
DEFDBL A-Z
FOR n = 1 TO 17
gen = n: told = n
FOR n1 = n - 1 TO 1 STEP -1
gen = gen * n1
told = told + gen
NEXT
PRINT USING "## ############### "; n; told
NEXT

The resulting table is:

` 1               1 2               4 3              15 4              64 5             325 6            1956 7           13699 8          109600 9          98640910         986410011       10850511112      130206134413     1692679748514    23697516480415   355462747207516  5687403955321617 966858672404689`

As a manual check for, say 4:

`You tell 4 people                           total 4 so far4 people tell 3 people each, making 12           1612 people tell 2 people each, making 24          4024 people tell 1 person each, making 24          64 `

Looking up the sequence in Sloane finds Sloane A007526, where a simple formula is given:

[e*n! - 1] where the square brackets indicate the floor function, or integer part: the greatest integer not exceeding the argument enclosed.

The following program calculates that formula and places it in a column to the right, for comparison.

CLS
DEFDBL A-Z
e = EXP(1)
nf = 1
FOR n = 1 TO 17
nf = nf * n
gen = n: told = n
FOR n1 = n - 1 TO 1 STEP -1
gen = gen * n1
told = told + gen
NEXT
PRINT USING "## ############### ###############"; n; told; INT(e * nf - 1)
NEXT

` 1               1               1 2               4               4 3              15              15 4              64              64 5             325             325 6            1956            1956 7           13699           13699 8          109600          109600 9          986409          98640910         9864100         986410011       108505111       10850511112      1302061344      130206134413     16926797485     1692679748514    236975164804    23697516480415   3554627472075   355462747207516  56874039553216  5687403955321617 966858672404689 966858672404689`

The columns do match, verifying the closed-form expression.

 Posted by Charlie on 2008-04-25 16:09:17

 Search: Search body:
Forums (0)