100 birds for 100 coins

There is a very old style of math problem known as 100 birds for 100 coins. The usual set up is that there are three kinds of birds. The most expensive kind costs more than one coin each, the next most expensive also cost more than a coin, but the cheapest kind can be bought for less than a coin. Sometimes the three types of birds are three different species, like hawks, ducks and sparrows. In this case, let's say it's geese, ganders and goslings. Let us assume that the goslings are cheapest, the female geese are most expensive because they can either be eaten or kept to lay eggs, and the male gander is somewhere in the middle. (In some versions, the gander is worth more because he is usually larger and produces more meat when slaughtered.)

Here is the set-up for one version of this problem.

At a market, you can buy a goose for four coins, a gander for two coins and two goslings for one coin. Find all the ways you can buy exactly one hundred birds for exactly one hundred coins.

Okay, let's start with the semantics of the statement. For 50 coins, you can buy 100 goslings, but that isn't a solution to our problem because we asked for exactly 100 coins and exactly 100 birds. What we get are two equations. I will use x, y and z for geese, ganders and goslings respectively.

x + y + z = 100 (100 birds)
4x + 2y + ½z = 100 (100 coins)

Usually, if we have two equations and three unknowns, we will have infinitely many solutions. But this problem is called a Diophantine equation, which means the solutions must all be non-negative integers. (This means we can have fractions of birds.) The idea is to have one of our variables become the independent variable and the other be dependent. This can be done with linear algebra methods, subtracting multiples of one of the equation from the others. I will let the reader do this work if he or she desires, but the answers are as follows if x is the independent variable.

y = (100 - 7x)/3
z = 2(100 + 2x)/3

What this tells us is that 100 - 7x and 100 + 2x most both be divisible by 3. This is always possible if x is a number of the form 3k + 1, like 1, 4, 7, 10, 13... The limiting factors are:

Limiting factor #1:t 100 - 7x > 0
Limiting factor #2: 2(100 + 2x) < 300.

Let's start with x = 1 and see what we get.

x = 1, y = 93/3 = 31 z = 204/3 = 68
This works! 1 + 31 + 68 = 100 and 4(1) + 2(31) + ½(68) = 100.

What about x = 4? This works, too.
x = 4, y = 24, z = 72.

Let's continue on with all the solutions. (To get a new solution, add 3 to x, subtract 7 from y and add 4 to z.)

x = 7, y = 17, z = 76
x = 10, y = 10, z =80
x = 13, y = 3, z =84


This is the last possible solution, since if I subtract 7 from 3 I get -4, and we are not allowed to have -4 ganders. (This is because 100 - 7(16) < 0, so it doesn't hold with our Limiting factor #1 shown above.)

I can't just pick two whole numbers greater than 1 and less than 100 and some arbitrary fraction and get solutions to such a problem. There are some prices that produce only one legitimate answer and others that have no legitimate solutions. But the method of finding one independent variable and two dependent variables followed by guessing and checking will always find the solution set, whether it has multiple answers, one answer or none.

Two types of odd primes:4k+1 and 4k+3

Welcome to Math Year 2014. Like with Math Year 2013, I will be posting here from time to time. I will be doing election prediction work on the Senate and Governor's races when they come around and may do another series on climate change as well. Math Year 2013 will be available as a link at the top of the page. That blog started with a question about whether 2013 was a prime or not. (The answer is no, 2013 = 3 × 11 × 61.) Today, we will look a way to split the odd primes into two groups, the 4k+1 primes and the 4k+3 primes.

One of the "easiest" facts about the primes is that 2 is the only even prime. Any even number bigger than 2 is divisible by 2, so it isn't prime. Let's look at the odd numbers less than 30 to see which ones are prime.

3 is prime.
5 is prime.
7 is prime.
9 = 3 × 3, so no.
11 is prime.
13 is prime.
15 = 3 × 5, so no.
17 is prime.
19 is prime.
21 = 3 × 7, so no.
23 is prime.
25 = 5 × 5, so no
27 = 3 × 3 × 3, so no.
29 is prime.

If we divide any odd number by 4, the remainder will have to be odd, either 1 or 3. Looking at the primes on this short list, here are the 4k+1 primes.

4k+1 primes less than 30: 5, 13, 17, 29

And these are the 4k+3 primes less than 30: 3, 7, 11, 19, 23

Here is an unusual fact about the 4k+1 primes. Every one is the sum of two perfect squares. It is not easy to prove this, but it's not hard to illustrate with the early examples.

5 = 1² + 2²
13 = 2² + 3² 
17 = 1² + 4²
29 = 2² + 5²

In all cases, we will have prime = even² + odd², since even² + even² = even and odd² + odd² = even, and all the primes we are looking at must be odd, since they are all larger than 2.

Let's look at the primes between 2000 and 2100, numbers we found last year on January 2. We will split them into 4k+1 and 4k+3 primes.

4k+ 1 primes: 2017, 2029, 2053, 2069, 2081, 2089
4k+3 primes: 2003, 2011, 2027, 2039, 2063, 2083, 2087, 2099

It's not as easy to find the two squares that add up to these larger numbers, but here they are.
2017 = 9² + 44² = 81 + 1936
2029 = 2² + 45² = 4 + 2025
2053 = 17² + 42² = 289 + 1764
2069 = 25² + 38² = 625 + 1444
2081 = 20² + 41² = 400 + 1681
2089 = 8² + 45² = 64 + 2025

Another strange fact about 4k+1 number is that if they are not prime, they don't have to be the sum of two squares. For example, 21 cannot be written as the sum of two perfect squares, even though it is (4×5) + 1.