Feb 18 2013

Sudoku: the basics

Categories:

Sudoku

by

Those of us who think we'll live a long time (not me) have a couple near certain conditions to look forward to. For men, it's prostate cancer. But for either gender, it's dementia. Puzzles ward off dementia. I'm not all that good at puzzles. Over the years I've done crosswords, but they require a bit too much outside knowledge (not to mention having a large lexical database with words like oleo, Olin, Gynt, etc). For awhile I did the newspaper Cryptoquote, but those became a bit too easy.

But eventually, I did the LA Times' Sudoku, which I found appealing because it's somewhat more logical in nature than those other ones. I want to dig into some advanced techniques, because solving a Sudoku should (almost) never involve guessing. However, it's worth going over the basics of Sudoku.

All people can learn Sudoku. Sudoku has several difficulty levels, and the puzzle is classified roughly by how advanced the solution technique is. Gentle/easy is the lowest difficulty. These can be finished with only basic (direct) techniques. Moderate and Tough generally speaking require indirect techniques. Expert/Diabolical require the most advanced techniques. Today I only want to talk about basic technique.

Consider the following puzzle:

SudokuBasic1

The Sudoku board is a 9 x 9 square board with squares of 3 x 3 grouped by dark lines (in the puzzle above, the darker colors of green also denote a separate box). There is only one rule: each line, column, and 3 x 3 box must contain every number between 1 and 9. Because each of those groups has nine entries, we can also say that no line, column, or 3 x 3 box will contain more than one of the same digit. This is how we solve the puzzle.

Any solution technique for Sudoku should also come along with it a search pattern. A strategy is not useful unless you know how to look for an instance of where it gets used. So, I'm going to go through the techniques I would use to first attack the puzzle.

Technique 1: Box by box

I start by looking at the upper left 3 x 3 box. I start with number 1, which is not filled in. Can I find out where 1 must be in that box? No. The only 1 that "touches" that box is the 1 in the next box over to the right, but that one only tells me that the 1 in the first box is not in the middle row, which is not enough to go on.

Then I count 2. Already there. 3, already there. Now 4.

SudokuBasic2

The 4s in the next two boxes are in the first row and the second row. Mentally, I draw a line from each of these through the box I'm focusing on. I see that once those boxes that are excluded by those 4s are eliminated, there is only one possibility for where the 4 goes, in the bottom right square of the box.

SudokuBasic3

I'm leaving the solved squares in yellow to remind us that they weren't in the original puzzle. I continue in this way. Can 5 be solved in the first box? No. 6? Yes.

SudokuBasic4

The 6 in the box below it excludes it being in the first column, and the 6 in the upper right box excludes it from being in the center row. Had we not already solved for 4, we would still have two possibilities, but since we have, we know it must be in the upper right square.

SudokuBasic5

Let's adopt a naming scheme. Let's call the upper left box "box 1", then number them going left to right. So, the box to its right is "box 2" and the one under box 1 is "box 4". "box 8" is the middle box of the bottom row of boxes. Then, we'll name each square in the box the same way. Rather than go through each deduction, I'll just summarize the ones I find by continuing with this strategy, then show you the board with all of them filled in.

Box 1, square 1 = 1
Box 1, square 5 = 7
Now in Box 1 there is only one square left open, so square 6 must = 5
Box 3, square 5 = 8
Box 4, square 4 = 2
Box 4, square 1 = 7
Box 4, square 8 = 5
Box 4 square 6 = 8
Now in Box 4, there is only one square left open, so square 9 must = 1
Box 5, square 8 = 3
Box 5, square 2 = 8
Box 5, square 5 = 1
Box 5, square 6 = 7
Therefore Box 5, square 4 = 5
Box 6, square 1 = 5
Box 6, square 2 = 1
Box 6, square 4 = 6
Box 6, square 9 = 7
Therefore Box 6, square 6 = 9
Box 7, square 5 = 1
Box 7, square 3 = 3
Box 7, square 2 = 6
Box 7, square 7 = 8
Therefore Box 7, square 1 = 4
Box 8, square 7 = 4
Box 8, square 8 = 6
Box 8, square 2 = 7
Box 8, square 3 = 5
Therefore Box 8, square 6 = 9
Box 9, square 1 = 2
Box 9, square 4 = 4
Box 9, square 5 = 6
Box 9, square 7 = 7
Therefore Box 9, square 9 = 1

At this point I've done one "pass" through the puzzle with only this technique. The board looks like this:

SudokuBasic6

Wow, just one pass through the puzzle with the box-by-box search filled in most of the puzzle.

At this point, we actually have three columns with only one blank entry, and so we know that entry must be whichever number doesn't appear. Column 6 is missing an 8, column 7 is missing a 1, column 8 is missing a 7. Also, row 2 is missing a 2. Thus, these can be filled in immediately.

SudokuBasic7

The remaining entries can be filled in without any other techniques necessary. That is, we got through the entire puzzle with just one strategy.

SudokuBasic8

The full solution has all digits in every row, column, and box. Once you get good enough, such a puzzle takes about 3 minutes.

More to come.

This post has no tag

Feb 06 2013

Thermo for Normals (part 29): Radiation, continued

Categories:

Science, Thermo for Normals

by

Now we know the amount of radiation coming from an object with a surface at temperature T. And we know the amount for each frequency of light. It's

\mathcal{P}(f) = a(f) \frac{h}{c^2} \frac{f^3}{e^{hf/kT} - 1}


where f is frequency you're interested in, c is the speed of light, and a(f) is a property of the object called emissivity. Emissivity measures the fraction of white light that is emitted and absorbed by the surface, and could be a function of f if, say, something absorbed blue but not red and green (such an object would be yellow). This equation tells you the energy radiated per time and per surface area in the neighborhood of f:

\begin{align*}\mathcal{P}(f) \, df = & \text{The amount of energy that leaves a body at temperature $T$} \\
& \text{as radiation at frequency $f$, per second and per square meter}.\end{align*}

(This isn't precise. Technically this only gives you the amount in a small range around f, and the only way to get the amount is to integrate. However, that's confusing as hell until you get used to it.) To get the actual amount of energy radiated out of it, you have to add up the values for the frequencies you want to know about, multiply by the surface area of the object, and multiply by the time it radiates for.

But let's assume we just want to know the total amount of all radiation, no matter what frequencies it's composed of. Then we just need to add up \mathcal{P} for every frequency. That will give us the cooling rate for a body with surface temperature T due to radiation:

Important!

The total amount of energy radiation per unit area per unit time is

\int_0^\infty \mathcal{P}(f) \, df = \int_0^\infty a(f) \frac{h}{c^2} \frac{f^3}{e^{hf/kT} - 1} \, df.


The integral of x^n/(e^{x}-1) is quite difficult, so I'll just quote the result (but see here for the calculation) which is \pi^4/15. We have to get rid of the h/k T in the exponential to use this, so let x=h f / k T, dx= (h/kT) df. Therefore,

\int_0^\infty a(f) \frac{h}{c^2} \frac{(kTx/h)^3}{e^x - 1} (kT/h) \, dx.


Now, and this is a very important assumption, assume that the emissivity is the same for all frequencies. That is, a is a constant for a given object. Then,

a \frac{k^4}{h^3 c^2} T^4 \int_0^\infty \frac{x^3}{e^x - 1} \, dx = a \frac{k^4}{h^3 c^2} T^4 \pi^4/15.


Let's wrap all those constants into a number called \sigma.

The total radiation from a body at surface temperature T per time per surface area is, then,

P_\text{tot.} = a \sigma T^4.

This is the Stefan-Boltzmann Law, and it's quite a simple law, really. The total radiation (per surface area per time) is just a constant (\sigma = 5.67 \times 10^{-8} W m^{-2} K^{-4}) times T^4, times the emissivity. The temperature is the temp at the surface, which might not be the same as the temperature of the interior! The interior of the Sun is millions of kelvin, but its radiation temperature is 6000 K because that's the temperature of the surface.

If you have an object with surface area A, then in time t it radiates A t \sigma a T^4 of energy. Human skin is an almost perfect emitter in the IR (emissivity is 0.98), and so is clothing for that matter. Assuming that an average person has about 2 square meters of skin, and that skin is 33 °C = 306 K, then the amount of heat radiated every second by a naked person is 1000 J. You are emitting 1000 watts if you're standing around naked. At that rate, you'd be freezing in a very short time! Now, the thing is that the environment around you is radiating back at you as well (unless you're in outer space without a suit ...). If the walls are 20 °C = 293 K, then they radiate an energy per unit area of a \sigma (293)^4, and drywall emissivity is also close to 1. You absorb A \sigma (293)^4 of energy every second from your environment. So the net loss is only \sigma (306^4 - 293^4) = 158 watts, or 158 joules every second if you're naked. If you're clothed, then the temperature of the surface is the temperature of clothing, which is more like 28 °C = 301 K. In that case, usually you are losing 95 watts in radiation, enough to power a very bright light bulb (in principle). Of course, I've left out any effects of the other two ways heat gets around: conduction and convection. We come back to that next time, where I'll speak about the way humans experience and perceive heat.

Now think about the Earth. It has no conduction or convection with the rest of the universe, since all that there is outside of the thermosphere is vacuum. The Sun is the same. So the Earth radiates some energy a_E A_E \sigma T_E^4 for its surface temperature T_E, surface area A_E, and emissivity a_E; and the Sun emits a_S A_S \sigma T_S^4 for its surface temperature T_S and area A_E. Now, the radiation from the Sun has spread out in all directions, so the energy per area is lower by 1/4 \pi r^2, where r is the distance from the Sun. So if we take the distance from the Sun to the Earth to be r, then the amount of radiation the Earth emits is

a_E A_E \sigma T_E^4

and the amount it absorbs from the Sun is

a_E A_E \sigma a_S T_S^4/4 \pi r^2.

Why? Because a_E is both the fraction emitted and the fraction absorbed, and A_E is the area that the radiation density \sigma a_S T_S^4/4 \pi r^2 is incident on. So long as the Earth's temperature isn't rapidly changing, then these two values must balance. This gives you a small taste of the thermodynamics of climate change, which we'll take up in detail later.

During the calculation, one has to assume that the object emits and absorbs all frequencies at the same rate for all frequencies or light, which is to say that emissivity is just a number. This is not always going to be very accurate. Tungsten, which is used as the filament in light bulbs, has an emissivity that looks like this:

er

Spectral emissivity of tungsten at high temperatures (from R.D. Larrabee, MIT Technical Report 328 (1957))

You can see that the value for emissivity actually depends not only frequency, but also on temperature. Nevertheless, observe that the vertical axis is not a very big range (from 0.4 to 0.5), so if you were to say that the emissivity of tungsten is about a=0.45, you'd be correct within 10%. To do any better, you have to calculate the above numerically, using the data from experiments. The point is, tungsten radiates more at 1000 THz than it does at 400 THz, but not by a huge amount. However, the emissivity for things such as clouds in the atmosphere may be very important, so keep it in mind.

This post has no tag

Feb 01 2013

New American Cancer Society report

Categories:

Science

by

The American Cancer Society just published their 2013 Facts and Figures report. It's kind of interesting to look at the time dependence of the rates. First for men:

Males

Cancer death rates for males (click for full size)

Since 1990, the rate of lung (mostly smoking induced) cancer has been falling, presumably due to the government's concerted effort to force people to stop---absent any other compelling reason that we should believe rates would be falling so fast, this is reasonable and not surprising.

It's notable that, due to H. Pylori being wiped out by antibiotics, rates for stomach cancer have steadily fallen from 45/100,000 to only about 5/100,000, a factor of 9 decrease since 1930. For most intents and purposes, that cancer has been "cured", although its decline is due to prevention rather than actual curing once a patient has it.

Prostate cancer is the largest non-lung cancer. Oddly, "for reasons that remain unclear, incidence rates are 70% higher in African Americans than in whites", the report states. The two possibilities are difference in lifestyle or differences in genetics, but determining which is contributing is so far elusive. The death rate among African Americans to prostate cancer is double that of whites; presumably the balance is due to poverty and lack of good medical care. Deaths due to prostate cancer are falling for America overall. However, incidence rates for prostate cancer are also falling, at a rate of about 2% per year between 2005 and 2009.

For Women:

Females

Cancer death rates for females (click for full size)

The vertical scale on these two charts is the same, and while all these curves are significantly smaller than that of men, it should not be construed that women die less often from cancer. In fact, the rate of death for women from all cancers is only about 10% smaller than men. The death from lady-parts cancers (breast and genitals) is about 68,000 per year, whereas men die of man-parts only about 31,000 cases per year, which explains this apparent discrepancy. Dispensing with gender-exclusive body parts, women have lower deaths of cancer of almost every part of the body.

Male Female
Oral 5500 2390
Digestive 82700 61870
Respiratory 90600 73290
Bones 810 630
Soft tissue 2500 1890
Skin 8560 4090
Breast 410 39620
Genitals 30400 28080
Urinary 20120 9670
Eye 120 200
Lymphoma 11250 8950
Myeloma 6070 4640
Leukemia 13660 10060
Other 25020 20400
Total 306920 273420

Survival rates (5 years past diagnosis) are highly dependent on body part. 90% of women will live 5 years beyond their diagnosis of breast cancer, and nearly 100% of men past their prostate cancer diagnosis. On the other hand, pancreatic cancer survival is a mere 6%, with liver and lung about 16-17%.

Survival

Medical science has made little progress in pancreatic cancers, but has nearly cured prostate and breast cancer since the 1970s. Significant improvement in leukemia, lymphoma, and testicular cancers has also been seen. For most categories, however, the decrease in deaths has been due not to treatment, but rather to prevention.

This post has no tag

Jan 16 2013

Mark Kelly is right about gun policy. His 85% statistic is bullshit

Categories:

General

by

ScreenClip

Not even close.

I strongly support gun control. This country has gun laws dictated by a relatively small group of highly vocal lunatics who believe all manner of strange things, from doomsday scenarios to byzantine and ghastly conspiracy theories. Any sane political theory dictates that if we take sensible steps to reduce the number of semi-automatic firearms in the US it would probably greatly decrease our homicide rate.

Nevertheless, Mark Kelly and others who declare that 85% of all children killed in the world with guns are killed here in the US are promoting a pants-on-fire lie that is off by probably more than one order of magnitude. We on the left rightly criticize those on the right for making horrifically huge and stupid misstatements. Let's not become that.

Where does the 85% figure even come from? My hope is that anyone who hears it would be immediately incredulous, given that Americans make up only about 4.2% of the world's population and that deplorable violence is pervasive throughout the developing world. Though no citation was immediately apparent, a little Googling turned up a study by Erin Richardson and David Hemenway from 2010, published in what was then the Journal of Trauma, Injury, Infection, and Critical Care (I found the full text here). The authors took data from the 23 richest nations (Australia, Austria, Canada, the Czech Republic, Finland, France, Germany, Hungary, Iceland, Italy, Japan, Luxembourg, Netherlands, New Zealand, Norway, Portugal, Slovakia, Spain, Sweden, England/Wales, North Ireland, Scotland, and the US) furnished by the World Health Organization and filtered the data according to the ICD-10 classification system of causes of death, such as firearm-related homicides, suicides, and several other variants. The data was from 2003, when the US still was under the 1994 Assault Weapons ban, which restricted magazine size and banned many types of firearms.

Richardson and Hemenway found that 87% of all children aged 0 to 14 killed by firearms in these 23 countries were US children. 80% of all firearm deaths in this group occurred in the US. The US overall had a rate 19.5 times higher than the other 22 countries, driven mainly by guns.

Ok, good, stop there. Just say "compared to other developed countries, our laws are ridiculous and it's literally killing our citizens". Great, factual argument.

What about the original claim? The study cited could not possibly have been carried out for all 196 countries in the world. However, the UN (specifically the UNODC) collects data on all homicides in a country, and the data was particularly well-filled-out in 2008 (only 18 countries had no data). I calculated overall homicide rates for the world vs the US using data from 2008.

Whereas the US had a rate 6.9 times higher than the 22 other rich countries, it had a below average rate for the world. The US share of homicides in 2008 was 3.57%, whereas its share of population (surveyed) in 2008 was 4.66%.

98 countries on the list had higher homicide rates than we do. The US's rate was 5.4 homicides per 100000 people. Contrast that with Burundi (21.7), Ethiopia (25.5), or Kenya (20.1). Ivory Coast (cote d'Ivoire) had 10,801 homicides in a population of only 19 million people, a rate of 56.9 per 100000. Jamaica: 59.5, El Salvador 51.9, Honduras, for Christ's sake, 61.3 (4473 homicides in a population of only 7.3 million!).

The statement Mark Kelly made is probably off by a factor of 20. Liberals, myself included, are proud of the fact that we are, for the most part, the party of intellectuals, operating in reality and fact that Fox News and their ilk ignore. Great. Let's act that way.

This post has no tag

Dec 28 2012

Thermo for Normals (part 28): How things radiate

Categories:

General

by

Every object, including you, radiates all the time. The radiation comes in the form of light, also known as electromagnetic radiation. Most of the time, this light isn't visible. Right now I'm radiating, and almost all of what is coming off is infra-red (IR), though there is also a tiny amount of radio, and microwaves. Your eyes can't see light with such a long wavelength, so in a dark room, you would see me using an infra-red camera, but not a regular visible-light camera. Hotter things, such as filaments in light bulbs, do radiate light that can be seen. The surface of the Sun, at around 6000 Kelvin, also creates ultraviolet (UV) rays. And the blazing hot corona of the sun emits x-rays, and gamma rays, in addition to all of these previous kinds.

We normally talk about the different types of light as distinct objects. IR is "heat" radiation, because normally when we encounter it that's what it's doing: heating us. Then there's what most people call light, but which I call "visible light"; that kind of light is between 400 nm and 700 nm in wavelength, or between about 4.28 and 7.50 \times 10^{14} cycles per second. 1 cycle per second is called a Hertz (Hz). And if you have 10^{12} of them, that's a terahertz (THz). So visible light is 428 to 750 THz. Your eye was adapted to collect light of this type, so that's what you see.

There are two things to consider. 1. What kinds of light does an object at temperature T radiate? and 2. How much light does it radiate? Radiation is constantly providing cooling and warming of objects, so we need to know the answers.

A substance is always made up of atoms, and the atoms all have electrons. These electrons orbit the nucleus, but only at certain energies. These energies form discrete steps. When the atoms knock into each other, which they are constantly doing, there's a chance that the electron gets promoted to a higher step. If it picks up a lot of thermal energy from the atoms, it can suddenly jump up a few steps. After a short time, it will fall back down. If it falls down, a particle of light is generated, called a photon. Since the electron loses energy during that fall, the photon must be carrying away energy.

That's right, photons, which are what light is made of, have energy. The energy of a photon depends on its frequency or wavelength. If its frequency is f then its energy is E=h f. h is just a constant, named for Max Planck, and called Planck's constant. If you'd prefer wavelength, it's E=hc/\lambda, where \lambda is the wavelength and c is the speed of light. Light is characterized only by frequency (or wavelength). The different types of light (radio, microwave, IR, visible, UV, x-ray, and gamma ray) are determined solely by f, and so by energy. Thus, the type of light emitted will have something to do with energy the electrons pick up, and hence on the temperature. On the other hand, the brightness only depends on how many photons there are. Brighter light, more photons. So what we have to figure out is how many photons of each type are made.

Here I'm going to write the amount of radiation emitted per second (the power) at each frequency for a body at temperature T. The only way I know to derive it is very advanced (a 4th year undergraduate physics major problem), so I'm not going to. After I write it, we can see its general features, and then we can try to figure out the total power radiated. Here it is:

\mathcal{P}(f) = a(f) \frac{h}{c^2} \frac{f^3}{e^{h f/k T} - 1}.

This answers both questions at once. If you want to know the amount of light at some frequency, you just plug in f and T to this*. If you want to know the total energy being radiated, you just sum up the energies for all the possible frequencies, which we'll do next time. Here a(f) is called the emissivity, and it depends upon the object itself. If an object is perfectly absorbing, and reflects nothing, then a will be 1 for all frequencies. Otherwise, a is somewhere between 0 and 1, and it might depend on frequency.

(*The above is actually per unit area. The bigger the object, the bigger the surface area, and the more photons. Also, since this is a distribution, we have to take an area to get an intensity, but this is a mathematical kink that the reader should not be worried about)

Here's what the spectrum looks like for an object at 300K:
Blackbody300KFor simplicity we'll say this is a black object like coal. The area under the curve represents the total brightness, or the number of photons coming off. The range on the x-axis is all in the "far infrared" segment of the electromagnetic spectrum. All of the frequencies lower than this are squished into the far left of the graph, so they aren't visible. Here's a close-up of the left part of the graph:
Blackbody300KLowerThere is very little radio being emitted, a tiny amount of microwaves, and then we get into the Far IR. It's very tempting to just say that objects at room temperature only radiate IR. The fraction of light emitted in the radio/microwave range is only 0.0005%, which I determined by comparing the area under the curve for the radio and microwave parts to the area under the curve for the rest. It's not nothing, but it's quite small.

Now let's look at what happens for an object at twice the temperature, 600 K, which is hotter than your oven gets:
Blackbody300600KWow, the 600 K object radiates a lot more light! I would say, just to eyeball it, that the area under the green curve is more than 20 times larger than the blue curve, and the area, as I've said, corresponds to more photons ("brighter", in a sense, except you can't actually see it). It also goes to larger frequencies than the 300 K object, but it's still very much in the infrared region. It has not even gotten to the "near infrared" region, which is above 300 THz (and which some insects can see). So we think that probably things have to be quite hot before they start to radiate light we can see. Notice that the peak frequency (the frequency that the most photons come off with) has also moved to the right, from about 18 to 40 THz. We'll think about that again later.

Now, let's increase the temperature until we see the object start to glow red. Here's the spectrum at 1600 K:
Blackbody1600KThe tail on the right is finally barely overlapping the visible. A huge, huge majority of the light is still in the Far IR part. This thing is still mostly radiating heat, rather than useful visible light. But your eyes are fairly sensitive, so you can actually see an object start to glow red at 1600 K (I have seen it myself). Now let's heat up to 2100 K:
Blackbody2100KAt 2100 K, you can see that there is significant overlap of the curve with red, and some overlapping with green. Red and green makes yellow, so as you increase the temperature, it turns red hot, and then yellow hot. It never turns "green hot", because the tail always has to start at infrared and go down. Any time green is emitted, red is also emitted. And, of course, once we turn the temperature up even higher, there will be blue photons, and we start to get white light, which is a combination of red, green, and blue.

Now let's check out the surface of the Sun, which is about 6000 K:
Blackbody6000KSurfSunHere we still have a huge amount of IR radiation. A little less than half of the light coming off is still "heat" radiation, which can warm us up but can't be seen. The visible region is well represented, which means we have a significant amount of white light that is just a little bit less blue than it is red and green. Finally, we start to have significant amounts of radiation in the UV range. This is both the near-UV (which include UVA and UVB photons), and some far UV. Above UV would be X-rays and gamma rays. The surface of the sun does not create these; instead, they originate in the upper layer of hot gas around the sun called the Corona, for which the physics may be a bit different.

The phenomenon of objects radiating visible light when they get very hot is called incandescence. Regular old light bulbs use incandescence to create light. Here's what the electromagnetic spectrum for a tungsten filament in a light bulb (T equal to about 3000 K) looks like:
Blackbody3000KLightBulbThat sure seems like a dumb way to make light. Only about 20% of the photons are useful for seeing. The rest are just being radiated out as heat, warming up the glass bulb, the fixture, and your house. It is for this reason that it makes sense to ban incandescent light bulbs. The government has not yet seen fit to do so, but it should. We have much smarter ways of doing this.

Next time we'll look more carefully at the total amount of radiation coming off something at temperature T, and we'll also start to investigate what happens when the object is not totally absorbing. We'll look at how things receive radiation, and so why temperature has to be given "in the shade" to be comparable from day to day. We'll see that we feel warmer when this radiation is incident upon us. And we'll see how reflection moderates how hot things get when sitting out in the Sun. Eventually, we'll be able to start talking about the phenomenon of climate change using this information.

This post has no tag

Older posts «

» Newer posts