Genie and Hitch

Suppose Genie walks her dog Hitch on a trail where Hitch can run around without a leash. Genie wants to make sure Hitch gets a certain number of miles of running per day, but she doesn't want to walk that far herself. How long does Genie have to walk to make sure Hitch gets enough running?

The first step to solving most problems is to figure out what you know, and what you are trying to find out. Writting things down is always a good idea. Trying to keep it all in your head just makes things harder.

For Genie to figure out how far she needs to walk, she's going to have to make some estimates or measurements. She wants to know how fast Hitch is running so that she'll know how far he runs fur the duration of the walk. Let's say Genie estimates Hitch's running speed to be twice as fast as her walking speed. So if Genie walks at X mph, Hitch runs at 2X mph. In time T, Genie walks T*X miles, and Hitch runs T*2X miles. In comparing those distances, we see that Hitch runs twice as far (2XT) as Genie walks (XT). That means, Genie only needs to walk half the distance she wants Hitch to cover.

Solution...

Hide solution.

More Unintelligent Design

Both eukaryotes and bacteria must transcribe the genes in their DNA into RNA transcripts in order to use them. The process starts out much the same in both kinds of organisms. In bacteria, the process is logical and efficient. In eukaryotic organisms like plants, fungi and animals (us), the process has gone hideously awry, and evolution has again employed a sloppy and inefficient fix.

Most organisms store the bulk of their genome in DNA. The DNA double helix is more stable than the RNA single helix. DNA is a long list of genes, you can think of them as recipes in a cookbook. (It isn't set up like a logical cookbook. There are long spans of gobbledygook between the genes, which have to be edited out each time the gene is used.) DNA is the master copy of the cookbook. It's stored in the nucleus, away from all the ingredients, so the pages don't get torn, singed or spilled upon. In order to make the recipe, you must first make an RNA copy that you can take out of the nucleus, but you had to make the RNA copy anyway, because the machinery that uses the recipes can only read RNA. We call the enzyme that makes the RNA copy from the DNA polymerase. In eukaryotes, the polymerase transcribes the gene into RNA in the nucleus, and the RNA is taken out of the nucleus to be put to further use. Bacteria have don't have nuclei, but they still have to make the RNA copy of the gene in order for their machinery to put it to use.

Both bacteria and eukaryotes have promoters - sequences at the beginning of the genes that signal where the copy should start. Bacteria and eukaryotes also have sequences that signal the end of the gene, but they work differently. In bacteria the "end" signal is called a terminator. When the polymerase reads the terminator, it detaches from the DNA and releases the RNA copy to be used by the cell. Makes sense.

When eukaryote polymerase gets to the "end" signal, it transcribes it and keeps going. The transcribed end signal causes proteins that have been monitoring RNA transcript to cut off the transcript and take it away for processing so it can be used by the cell. Meanwhile, polymerase keeps going like a runaway train, transcribing hundreds of nucleotides, whatever happens to follow the gene. Biologists haven't completely figured out what happens next, but here's their best guess: An enzyme comes up and digests the trail of RNA gobbledygook that the polymerase is spewing out, recycling it back into unattached nucleotides. When that enzyme reaches polymerase, it knocks polymerase off the DNA, and transcription stops.

To summarize, bacteria have a system that works perfectly. Their polymerase starts at the start signal, transcribes, and stops at the stop signal. We organisms with nuclei have defective polymerases that no longer recognize the stop signals. Rather than fix the polymerases, evolution threw us some proteins to collect the RNA transcript and then another enzyme to clean up the mess and slide tackle the runaway enzyme off the DNA. That deserves a very special contraction: untelligent design. Keep in mind that every time polymerase attaches a nucleotide to the RNA strand, it's using energy - the equivalent to one ATP molecule. We don't get that energy back when we recycle the nucleotides. What kind of Intelligent Designer would have left such a mess?

Then again maybe there is some wisdom here. Bacteria are better at both DNA replication and RNA transcription. Maybe the Designer made the universe for the bacteria, and we're just here to be their hosts. After all, for every human cell in your body, you also have ten to twenty bacteria living in and on you - in a magnificent diversity of 500 - 1,000 different species. That's about 10¹², or 1 million × 1 million, bacteria living in and on each and every one of us. All hail our glorious Bacterial Creator?

Solution...

Hide solution.

Unintelligent Design

I'm taking some biology classes. From a engineer's point of view, living things are not intelligently designed. Vestigial organs, vestigial genes, and a multitude of other obvious design flaws litter the biological landscape. For instance, we havean ugly hack embedded in our DNA replication.

Telomeres are what is known in the software design world as a "hack" - they fix the immediate problem without correcting the underlying cause of the problem. To understand the problem that telomeres are meant to fix, you have to know a little about DNA and DNA replication. (I've attempted a terse explanation here, but there's always Wikipedia for a more thorough description.) DNA is a double helix consisting of two strands nucleotides. These nucleotides contain the familiar A, C, G and T bases that are held by 5-carbon sugar rings, and the rings are connected by phosphate groups. These sugars are asymmetrical, with an oxygen atom in one part of the ring, and a carbon atom sticking off the side. Biologists have labeled the carbons 1 - 5. The 3' carbon and the 5' carbon are the two that bond to the phosphate group, and to make a strand of DNA, you have to keep all the nucleotide lined up the same way: 3' - 5' - phosphate - 3' - 5' - phosphate and so on. So each double helix is made up of two nucleotide chains pointing in oposit directions.

When DNA is replicated, the enzymes that assemble new DNA strands can only add nucleotides to the 3' end, not the 5' end. The following video demonstraits how strand can be replicated continuously as it comes unwound, and the other must be copied backwards, one loop at a time, as it comes unwound.
That in it self is a bit of a hack. Why not just make an enzyme that can copy the nucleotide string going the other way? In fact, some viruses use such backwards-moving enzymes to replicate their own genetic code.

A larger problem occurs when the enzymes get to the end of the DNA strand. Because the copying enzyme is unidirectional, when it comes to replicating the final loop of the wrong-facing nucleotide strand, the enzyme attaches to the end of the strand and works back toward the copied section. But it cannot copy the spot where it attaches, only what is in front of it. That means there is a small part at the end of one strand of nucleotides that cannot be copied. Each time your DNA replicates, a piece on the end is lost. Since DNA is only stable with both complimentary strands, the corresponding bit on the other strand also falls off.

The patch that we use to compensate for the immediate problem is this: whenever you make a gamete (sperm or egg) a special enzyme adds telomeres - non-coding nonsense DNA - to the ends of all of your chromosomes. (Chromosomes are long, coiled and packed strands of DNA.) We are all conceived with telomeres on the ends of our DNA so that, as our DNA replicates and we loose little bits on the ends, we're only loosing nonsense... until our cells have replicated for many years. When humans were only living into their 40s, this wasn't so much of a problem. Now, this might be one of the causes of aging. You can think of it this way: if all of the important instructions on how to make your cells were held in a manual, telomeres would be blank pages at the front and the back of the book. Each cell needs it's own copy of the book, and each time the book is copied, it looses a few of the pages at the front and the back. If the book is copied enough times, it starts loosing valuable information.

Whereas a bad engineer might have come up with the temporary, wasteful fix of telomeres, a good engineer would have found a way to fix the underlying problem. As previously mentioned, she could have engineered an enzyme that could copy DNA in the other direction. This would solve two problems and make your DNA replication much more efficient, both in time and energy consumption. The second fix is already used by bacteria. If the DNA were stored in long rings, or just connected the ends during the final steps of replication, then there would be no "end", and our enzyme could copy the entire strand until it looped back upon itself. Bacteria store some or all of their DNA in rings, and those rings don't loose bits when they are copied because the DNA strands have no ends. An intelligent designer would have seen the problem, thought over possible solutions, and implemented a solution to permanently fix the problem. Evolution blindly fumbled around for whatever fixed the immediate problem, and we ended up with telomeres.

Solution...

Hide solution.

In Stitches

After doing the back-stitching on a few of the letters in this counted cross stitch pattern, I wondered if there would always be an even amount of stitches in the outline of a block shape.

Problem:

Define a "block shape" as any shape that can be created by coloring in squares on graph paper. Each square in a multi-square block shape must share at least one side with another square in that shape. Call the length of a square on the graph paper one unit. Prove or disprove: the perimeter of a block shape will always be an even number of units.


Solution:

I will prove that the perimeter is always an even number of units using the Principle of Mathematical Induction.

• Base case: consider a one-square block shape. Its perimeter is 4 units - one for each side. Since 4 is even, the proposition holds for the base case.


• Inductive hypothesis: assume that a block shape consisting of n squares has an even perimeter.


• Deductive step: What happens when I add a square to the n-block shape?
  
  
  
  • If the new square is touching exactly one other square, then I am taking away 1 unit from the perimeter and adding 3 units. That's a net gain of 2 units, so the perimeter remains even.
  
  
  • If the new square is touching exactly two other squares, I am taking away 2 units and adding 2 units to the perimeter. The net change is 0, so the perimeter remains even.
  
  
  • If the new square is touching exactly three other squares, I am reducing the perimeter by 3 units and adding 1. The net loss is 2 units, so the perimeter remains even.
  
  
  • If the new square is touching exactly four other squares, I am taking away 4 units from the perimeter and adding none. The perimeter remains even.
  
  In each possible case, the perimeter of the (n+1)-block shape remains even.

Therefore, by the Principle of Mathematical Induction, the perimeter of a block shape will always be even.

Solution...

Hide solution.

S.A.Tricky

Here's an S.A.T. problem that stumped my students and me (for a little while).

Problem:

a - b = 10
a² - b² = 50

Find b.

Solution:

My instincts were to look for a connection between (a - b)² and a² - b², but it's really much simpler than that. Solve for a in terms of b in the first equation, and substitute into the second equation.

---

Edit: The original post contained a mistake. (10 + b)² = 100 + 20b + b², not 100 + 2b + b².

Solution...

Hide solution.

IDEAs

Here's another S.A.T. problem.

Problem:

In the correctly worked addition problem to the left, A, B, D, E, I, and S each represent a different digit. What is the smallest possible value of D?


Solution:

You don't need to know what every digit in the problem is. You only need to know which digits have to be assigned to which letters in order for the addition problem to work.

Starting in the one's column, E + A = A, or E + A = A + a carry digit. The most two one-digit numbers can add to is 18, so the carry digit would have to be 10. If E + A = 10 + A, then E = 10, but we know that E < 10 (all of the variables are single digits). Thus, E + A = A, and E = 0. Filling that value into the puzzle we get: The value of A doesn't matter. We can forget about the two right-most columns of the addition and look at two left columns. B + S = 10I + D. The most that B and S can add up to is 17 (with B and S equaling 9 and 8), and the least they can sum to is 3 (if B and S equal 1 and 2). However, if B + S < 10, I = 0. We can't have another 0, so B + S must be greater than 10. Therefore, I = 1. Since we've used up 0 and 1, smallest digit we have left for D is 2. We can use 4 for B and 8 for S to make B + S = 12. If we use these values to fill in the puzzle, it all adds up. The smallest number D can be is 2.

Solution...

Hide solution.

Prime Factorization

This problem comes form Project Euler. I solved it with a computer program written in C++.

Problem:

What is the largest prime factor of the number 600851475143?

Solution:

It is tempting to write a function to find the prime factorization of a given number. Why? Because it's cool. I wrote that function, too, but I'm only going to cover the process of solving the given problem.

When solving a programming problem, you should always start on paper to get an idea of what your algorithm needs to do. Suppose I wanted to find the largest prime factor of 90, or what if I wanted to find the largest prime factor of 260? I might do something like what I did in the diagram to the right. In words, our algorithm might look something like this:

Start with your number.
Keep dividing by its factors until you find the biggest prime.

How is the computer going to know which numbers to try? We'll be using a loop, so we can start at 2 and work our way up through the numbers. The computer's factorization of 260 would look more like this: 13/7 is less than 2, 13/8 is even smaller, and 13/9 is smaller still. We're not going to get any more numbers that go evenly into 13 once our divisor is greater than 13/2. We can stop dividing whenever the divisor is greater than half of the number we're dividing. Notice that 4 divides 260, but it did not come up in our list of factors. Instead, we divided 2 out twice. 2 is prime, and 4 is not. Our algorithm automatically sifts out composite numbers by dividing their prime factors out first. In words, our algorithm looks something like this:

Start with your number.
Divide it by 2.
If it divides evenly, keep dividing by 2, otherwise, try 3.
If it divides evenly, keep dividing by 3, otherwise, try 4.
Keep dividing this way until your divisor is greater than or equal to half the original number.

Now we're ready for pseudo-code:

from ( divisor = 2 until divisor >= number/2 )
{
  if ( number is divisible by divisor ) then
    number <- number/divisor
  else
    increment divisor
}
return number

We would like to save our selves some time by only using prime numbers, but we don't have a list of primes. However, we do know that 2 is the only even prime number, so after trying 2, we only have to try odd numbers, which cuts our list of divisors in half. This is my final code:

unsigned long long LargestPrimeFactor(unsigned long long number)
{
  int divisor = 2;
  while(divisor<=sqrt((float)number))
  {
    if(number%divisor==0)
    {
      number = number/divisor;
    }
    else if(divisor==2)
    {
      divisor++;
    }
    else
    {
      divisor+=2;
    }
  }
  return number;
}

The largest prime factor of 600851475143 is 6857.

Solution...

Hide solution.