Math Virus FormulaDate: 10/23/2001 at 05:49:48 From: Victor Lee Subject: I cannot figure out the formula to a math virus Hello Dr. Math, I have to figure out a formula for a math virus. The virus spreads to all the squares directly touching each other (not including diagonally), and I have found the formula for the number of newly infected cells (although this does not include the first minute.) The formula is 4n + 4, but I also have to find the formula for the total number of infected cells, and despite trying many times to figure it out, I still have no clue. Just to give you a headstart with this, the total number of newly infected cells goes up by 4 cells each minute, i.e. 3 minutes is 13 and 4 minutes is 25. I will be extremely appreciative if you help me with this. Thanks, Victor Lee Date: 10/23/2001 at 14:41:02 From: Doctor Greenie Subject: Re: I cannot figure out the formula to a math virus Hi, Victor - This is a nice problem. There are many opportunities with this problem to be "clever" to make finding the answer quite easy. I will present the solution in exactly the way I found it, so that you can see how the effort required to reach a solution can be reduced by studying the problem to find the "easy" path. Let's start by drawing some pictures and making a table of our results.... +---+ n=0 | | new squares: 1 +---+ total squares: 1 +---+ | | +---+---+---+ n=1 | | | | new squares: 4 +---+---+---+ total squares: 5 | | +---+ +---+ | | +---+---+---+ | | | | +---+---+---+---+---+ n=2 | | | | | | new squares: 8 +---+---+---+---+---+ total squares: 13 | | | | +---+---+---+ | | +---+ +---+ | | +---+---+---+ | | | | +---+---+---+---+---+ | | | | | | +---+---+---+---+---+---+---+ n=3 | | | | | | | | new squares: 12 +---+---+---+---+---+---+---+ total squares: 25 | | | | | | +---+---+---+---+---+ | | | | +---+---+---+ | | +---+ So we have figure number additional squares total squares --------------- -------------------- --------------- 0 1 1 1 4 5 2 8 13 3 12 25 ... The sequence we get for the numbers of squares for n = 1, 2, 3, ... is 5, 13, 25, ... One way to find a formula for generating a sequence like this is the method of finite differences. Here is a link to a page in the Dr. Math archives where there is a lengthy discussion of this method: Method of Finite Differences http://mathforum.org/dr.math/problems/gillett.10.12.00.html While the method of finite differences is often very useful, I suspected I could find the answer more quickly by analyzing the figures and coming up with some shortcut for finding the total number of squares in the n-th figure. My approach (taken with too little forethought, as you will see later) was to break up the figure for the case n=3 as follows: +---+ +---+ +---+ | | | | | | +---+---+ +---+ +---+---+ | | | | | | | | +---+---+ +---+ +---+---+ | | +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ | | +---+---+ +---+ +---+---+ | | | | | | | | +---+---+ +---+ +---+---+ | | | | | | +---+ +---+ +---+ The number of squares in this figure is the number in the central "cross" figure plus the number in the four identical "stair-step" figures. The number in the central cross figure for the n-th case is (4n+1); the number in each of the four stair-step figures is the sum of the integers from 1 to (n-1), which I know to be n(n-1)/2. So the total number of squares in the n-th figure is (4n+1) + 4(n(n-1)/2)) = 4n + 1 + 2(n^2 - n) = 4n + 1 + 2n^2 - 2n = 2n^2 + 2n + 1 When I got to this point, I tried to find a simpler way to write this formula; after staring at it for a moment, I realized that 2n^2 + 2n + 1 = (n^2) + (n^2 + 2n + 1) = n^2 + (n+1)^2 In words, this formula is quite simple - the number of squares in the nth figure is the sum of the squares of n and (n+1). Checking this formula out quickly for n = 1, 2, and 3, we find n=1: n^2 + (n+1)^2 = 1+4 = 5 n=2: n^2 + (n+1)^2 = 4+9 = 13 n=3: n^2 + (n+1)^2 = 9+16 = 25 So the formula appears to be correct, indicating I did not make any mistakes with my reasoning or with my algebra. But after I came up with this formula, I went back to look at my figures to see if I could come up with this same formula more quickly than the way I did. And just a bit of looking at the figure showed me what would have been a much quicker path to the formula. The quicker path I found was to break up the n-th figure in a different manner than I did originally. This time, I break up the n-th figure as follows: +---+ | | +---+---+---+ | | | | +---+---+---+---+---+ | | | | | | +---+---+---+---+---+ +---+---+---+---+---+---+---+ | | | | | | | | +---+---+---+---+---+---+---+ | | | | | | +---+---+---+---+---+ | | | | +---+---+---+ | | +---+ Now the figure is comprised of two parts. The number of squares in the first part is the sum of the first n odd integers, which I know to be n^2; and the number of squares in the second part is the sum of the first (n+1) odd integers, which I know to be (n+1)^2. So by breaking up the figure in this manner I am led immediately to the formula number of squares in n-th figure = n^2 + (n+1)^2 Thanks for the interesting problem. I got some valuable problem- solving experience playing with it. I hope all this helps. Write back if you have any further questions on this. - Doctor Greenie, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/