Embarrasing mistake

I just realized that my last post was far off the mark. There is a super-obvious example that shows that f(n) >= n/2, and so in fact f(n) = n/2. The example is the subset {n/2 + 1, n/2 + 2, ... , n} which contains n/2 elements and clearly has the non-divisible property. The problem has very little to do with prime numbers. The previously-published result was sharp.

A simple (?) number theory conjecture

Call a set S of positive integers non-divisible if, whenever a and b belong to S, it is not true that (a|b or b|a). For example, the set of prime numbers is non-divisible. Let S(n) be the set of the first n positive integers, and let f(n) be the cardinality of the largest non-divisible subset of S(n). Then clearly f(n) >= pi(n), where pi(n) denotes the number of prime numbers <= n. Furthermore, I know a pretty proof (published, but not by me) that shows f(n) <= n/2 (n even). That is, in any subset of n/2 + 1 positive integers all <= n, at least one integer divides another integer in the set. This proof involves the pigeonhole principle. So, pi(n) <= f(n) <= n/2. (n even) My conjecture is that, in fact, f(n) = pi(n) for all n > 1. Does anyone have a counterexample or a proof? It seems like it should be very simple.

More on Ordering a Multiset

I posed problem A3, to find a formula for the k-th largest element of an n-element multiset A. I found a very interesting formula that is unknown to several famous combinatorists, including Donald Knuth, and I have submitted a problem to the MAA Monthly Problems section which asks for the solution that I found, a linear combination of certain symmetric functions. However, Knuth told me that there is a simpler known formula of a different type. Knuth's formula is

min(max_k)

where (max_k) is a set of C(n,k) numbers, each of which is the maximum of a different subset of A of size k.

Pretty cute!

Update on Quadrilateral Paper

Great news! Our paper, "Constructing a Quadrilateral Inside Another One" was accepted without further changes by The Mathematical Gazette, and should appear in the November 2009 Issue. This is the same version that I have posted on scribd.

Tri-Color chessboards

When coloring a checkerboard, the basic requirement is that squares that are full-neighbors (horizontally or vertically) have different colors. Clearly, there are exactly two ways of coloring an n x n checkerboard with two colors (black and red, say). Once a color has been selected for the lower left corner, all remaining square colors are forced. I wondered how many different ways one could color an n x n checkerboard with three colors. This led me to consider two problems:

(1) How many ways are there to color an n x n checkerboard, using at most 3 colors?

(2) How many ways are there to color a 3k x 3k checkerboard, using equal numbers of red, blue, and white squares?

Bridget Tenner of dePaul University immediately came up with the answer to problem (1) by searching in Neal Sloane's wonderful Online Encyclopedia of Integer Sequences, using "3-color" as a search string. The answer is given here as a special case of A078099 (for m x n checkerboards), which is defined recursively. The sequence grows very quickly: it is 3 times a sequence beginning 1, 6, 82, 2604, 193662, 33865632, 13956665236.

A sequence to answer question (2) does not seem to appear in OEIS, so this may be an open question.