Vampire Burial Discrimination


THE PROBLEM:
A cemetery with 20 rows of graves has 10 graves in the first row and 1 more grave in each successive row. If vampires are allowed to bury their coffins in any row but not next to another vampire in that row, find the maximum number of vampires who can be buried in this graveyard.

THE SOLUTION:
On the entry gate to this cemetery, there used to be posted a guide to the "Maximum number of vampires Cemetery Can Hold". The guide showed exactly which plots in each row could hold vampires and which plots couldn't. Here is a copy of that guide. (NOTE: "V" stands for vampire; "x" stands for nonvampire.)

    ENTRANCE
Row 1:  xVxVxVxVxV = 5
Row 2:  xVxVxVxVxVx = 5
Row 3:  xVxVxVxVxVxV = 6
Row 4:  xVxVxVxVxVxVx = 6
Row 5:  xVxVxVxVxVxVxV = 7
Row 6:  xVxVxVxVxVxVxVx = 7
Row 7:  xVxVxVxVxVxVxVxV = 8
Row 8:  xVxVxVxVxVxVxVxVx = 8
Row 9:  xVxVxVxVxVxVxVxVxV = 9
Row 10:  xVxVxVxVxVxVxVxVxVx = 9
Row 11:  xVxVxVxVxVxVxVxVxVxV = 10
Row 12:  xVxVxVxVxVxVxVxVxVxVx = 10
Row 13:  xVxVxVxVxVxVxVxVxVxVxV = 11
Row 14:  xVxVxVxVxVxVxVxVxVxVxVx = 11
Row 15:  xVxVxVxVxVxVxVxVxVxVxVxV = 12
Row 16:  xVxVxVxVxVxVxVxVxVxVxVxVx = 12
Row 17:  xVxVxVxVxVxVxVxVxVxVxVxVxV = 13
Row 18:  xVxVxVxVxVxVxVxVxVxVxVxVxVx = 13
Row 19:  xVxVxVxVxVxVxVxVxVxVxVxVxVxV = 14
Row 20:  xVxVxVxVxVxVxVxVxVxVxVxVxVxVx = 14
TOTAL NUMBER VAMPIRES ALLOWABLE= 190
Visiting the graveyard one evening, the vampire Jarno (who always questions everything) wondered what might happen if each row began with a vampire rather than a nonvampire. Jarno rediagrammed the grave plots and compared them to the guide as depicted by the cemetery planners. Here's what Jarno discovered:

    ENTRANCE
Row 1:  VxVxVxVxVx = 5
Row 2:  VxVxVxVxVxV = 6
Row 3:  VxVxVxVxVxVx = 6
Row 4:  VxVxVxVxVxVxV = 7
Row 5:  VxVxVxVxVxVxVx = 7
Row 6:  VxVxVxVxVxVxVxV = 8
Row 7:  VxVxVxVxVxVxVxVx = 8
Row 8:  VxVxVxVxVxVxVxVxV = 9
Row 9:  VxVxVxVxVxVxVxVxVx = 9
Row 10:  VxVxVxVxVxVxVxVxVxV = 10
Row 11:  VxVxVxVxVxVxVxVxVxVx = 10
Row 12:  VxVxVxVxVxVxVxVxVxVxV = 11
Row 13:  VxVxVxVxVxVxVxVxVxVxVx = 11
Row 14:  VxVxVxVxVxVxVxVxVxVxVxV = 12
Row 15:  VxVxVxVxVxVxVxVxVxVxVxVx = 12
Row 16:  VxVxVxVxVxVxVxVxVxVxVxVxV = 13
Row 17:  VxVxVxVxVxVxVxVxVxVxVxVxVx = 13
Row 18:  VxVxVxVxVxVxVxVxVxVxVxVxVxV = 14
Row 19:  VxVxVxVxVxVxVxVxVxVxVxVxVxVx = 14
Row 20:  VxVxVxVxVxVxVxVxVxVxVxVxVxVxV = 15
TOTAL NUMBER VAMPIRES ALLOWABLE= 200
Jarno was also able to demonstrate his conclusion without having to go through this elaborate drawing. Jarno figured that each row of graves has 9+n graves, where n = 1 through 20. So, row 1 has9+1=10 graves, row 2 has 9+2=11 graves, row 3 has 9+3=12 graves, and so on. Jarno also figured that at most (9+n)/2 vampires could be buried in rows with an even number of graves, so row 1 could have (9+1)/2 = 5 vampires, row 3 could accomodate (9+3)/2 = 6 vampires, etc. Since there are 10 even rows, there are a total of 5+6+7+...+14 = 95 vampire graves in these rows.

Furthermore, at most (9+n+1)/2 vampires can be buried in rows with an odd number of graves, so row 2 could have (9+2+1)/2 = 6 vampires, row 4 could sleep (9+4+1)/2 = 7 vampires, etc. Since there are 10 odd rows, there are a total of 6+7+8+...+15 = 105 vampire graves in these rows.

Altogether, 95 + 105 = 200 vampires can be buried in this cemetery.

Jarno promptly sued the cemetery owner for discriminiation against vampires and won.