J(p)=s

Genie and Hitch

2010-06-03T12:32:00.000-07:00

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.

More Unintelligent Design

2010-04-15T12:02:00.000-07:00

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?

Unintelligent Design

2010-04-14T15:33:00.000-07:00

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.

In Stitches

2008-05-06T12:14:00.000-07:00

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.

S.A.Tricky

2008-04-29T06:15:00.000-07:00

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².

IDEAs

2008-04-24T18:07:00.000-07:00

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.

Prime Factorization

2008-04-10T09:40:00.000-07:00

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.

Atari Space

2008-03-31T17:20:00.000-07:00

My friend Justin was reminiscing about some Atari-aged video games: Subspace/Continuum. The problem they inspired reminds me more of Asteroids.

Problem:

A turret in a video game can rotate but not change location. It shoots bullets that travel with a constant velocity V_B. An asteroid travels at a constant velocity V_A. Where should the turret aim to hit the asteroid?

Solution:

You'll never find where you're going if you don't know where you started. Let's put the turret at the center of a Cartesian plane. Add a point A for the asteroid at (x₀, y₀), and add a point for the eventual collision at (x₁, y₁). Label the distances traveled by the asteroid and the bullet D_A and D_B. Recall that little ditty: "Distance = Rate × Time." We can use this whenever we are dealing with constant velocities. I've already labeled arrows R_A and R_B to represent the rates in the diagram.(I'm listing the equation numbers (abbreviated "eqn") on the left. When I use those equations later, I'll show which equation number I used on the right.) Note: the bullet and the asteroid travel for the same amount of time once the bullet is fired, so T has the same value in each equation.

We have two equations and three unknowns, so we'll need to find some more relationships. I can find more information about D_A and D_B by breaking the distances into their horizontal and vertical components. I've added these components to the diagram below.Let β be the angle that the bullet's trajectory makes with the x-axis, and call the angle that the ship flies at with respect to the x-axis α.With all of these variables in play, let's take a moment to recap what is known and what we need to find.Now, we need to trade our variables down to get rid of some of those unknowns. I'll start with x₁. Now do the same with the sines to get rid of y₁. Now that we've gotten rid of x₁ and y₁, solve for T in equation 11 and substitute into equation 15... ...and simplify. Now we're down to one unknown: β. To find β, solve for sin(β), square both sides, and substitute 1 - cos²(β) for sin²(β). Then, use the quadratic equation to solve for the possible values of cos(β), and convert those values into the angles we want. Once we have β, we use equation 18 to find T and equations 4 and 5 to find x₁ and y₁.

I'm not going to attempt to finish this solution unless someone asks me to. I'm too likely to make a mistake somewhere in the tangled mass of algebra that is to follow, and Justin has access to math software that can do the manipulations for him. Comment if you have any questions.

S.A.T. Inequalities

2008-03-27T11:02:00.000-07:00

This one comes right out of the S.A.T.s.

Problem:

Each of the following inequalities is true for some values of x EXCEPT

Solution:

The process of elimination is perfect for this problem. A quick look eliminates (A) as a possibility. Anyone could think of a value for x that would make (A) true; for instance, if x = 2, then x² = 4 and x³ = 8, so we can cross of choice (A).
What other kinds of numbers are there? What numbers are "tricky"? Fractions and negatives. If x = 1/2, then x² = 1/4 and x³ = 1/8. That fits with the last inequality, so we can cross off choice (E).
Letting x = -2 makes x² = 4 and x³ = - 8. Ordering those gives us x³ < x < x², so we can cross off choice (D).
Now we only have two possibilities left, and they both look kind of goofy. If you were running out of time on the S.A.T.s, you could just guess between the two earning an expected value of 3/8 of a point, but we're not running out of time. We've tried positive integers, negative integers and fractions, so what's left: negative fractions. If x = -1/2 then x² = 1/4 and x³ = -1/8. That lines up as x < x³ < x², just like choice (B).
Therefore, the only inequality that will not be true for a value of x is choice (C).

Squares of Triangles

2008-03-19T11:10:00.000-07:00

Pythagoras was a Greek philosopher and mathematician who lived in the sixth century B.C.E. He acquired a following in his time, and there was a cult built up around him in which he was worshiped as a demi god¹. Today, he is most well known for his contribution to Euclidian geometry: the Pythagorean Theorem. Today's challenge is to prove the Pythagorean Theorem.

Problem:

Given any right triangle ABC, prove A² + B² = C² using only simple geometric formulas. (No trigonometric functions allowed).

Solution:

This problem seeped into my head as I was trying to fall asleep some nights ago, and I never could solve it lying in bed in the dark. It wasn't until I sat down with a pencil and paper and studied the problem from several different angles (during the second and third quarters of the Superbowl) that I came up with a solution.

The first thing I did was to redraw the diagram like this:
That way, I could visualize the quantities, A², B² and C² as the areas of the squares made from the sides of the triangles.

Next, I started to think about this:
Maybe we can find a relationship between a square with the side lengths of A + B and the grey square with lengths C.

The final thing you need to know is that the area of a triangle is equal to half the base times the height: The answer becomes clear when you draw in the rest of the triangles. Look at the red square.The lengths of each of its sides are equal to A + B, so it has the area (A + B)².

If you look at the triangles shaded in pink......you should see that each has a height of A and a base of B, so their areas are ½AB. Therefore, the area of the grey square is equal to the area of the red square from above minus the areas of the four triangles.

Weighing in on Icy Roads

2008-03-19T10:35:00.000-07:00

Problem:

Does increasing your vehicle's mass increase your maneuverability on icy roads? Assume the vehicle and all contents are treated as a point mass.

Solution:

It all comes down to two things: momentum and friction. Momentum (p) = the mass of the car (m) times the car's velocity (v), which is a term for a directed speed. We can change momentum by applying a force for a duration of time. Change in momentum = force × time.

Δp = F⋅t
Δm⋅v = F⋅t

What kind of force are we talking about? When it comes to driving a car, it's almost entirely related to the force of friction. When you apply the breaks, you're using
the friction between the tires and the road to stop the car. When you turn the wheel, it's the friction between the tires and the car that will ultimately change your direction, and when you accelerate, without the friction between the road and the tires, you'd just be spinning your wheels.

The force of friction (F_f) = the normal force (F_n) times the coefficient of friction (μ). The normal force of any object is equal to the product of the objects mass, the acceleration due to gravity, and the cosine of the angle (θ) between the horizontal and the surface providing the friction.

F_f = F_n⋅μ
F_f = m⋅g⋅cos(θ)⋅μ

Now, let's look at the change in momentum due to the force of friction applied over time t:

Δp = F⋅t
Δm⋅v = F_f⋅t
Δm⋅v = F_n⋅μ⋅t
Δm⋅v = m⋅g⋅cos(θ)⋅μ⋅t

The m on each side of the equation represents the same thing: the mass of the vehicle plus contents. Dividing each side by m gives us:

Δv = g⋅cos(θ)⋅μ⋅t

Thus, taken as a point mass, the mass of your vehicle has no effect on your ability to change your direction or speed.

Welcome to J-Function Problem Solving

2008-03-18T19:09:00.000-07:00

Here's the deal: you send me math or science problems, and I'll post solutions up to as often as one per day. I'll solve problems from any of the subject areas I tutor and also from logic or philosophy. Ask away.