Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Math Virus Formula


Date: 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/   
    
Associated Topics:
High School Basic Algebra
High School Number Theory
High School Sequences, Series

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/