Archive for the ‘Misc. Problems’ Category

The One Four Puzzle (?!)

August 13, 2010

I spend a couple hours a week with Mel Hochster, chair of the math department here at UMich, for the very serious purpose of doing cryptic crossword puzzles, a shared interest.  We almost never discuss actual math problems, but last week was an exception.  He says this is something he thought of a while back but never made much progress.

Suppose a set of positive integers contains the number 4 and is closed under the maps $n\mapsto n!$ and $n\mapsto \lfloor\sqrt{n}\rfloor$.  Must the set be all of $\mathbb{Z}^+$?

The motivation comes from that game that almost everyone who likes to play with numbers has played, the four fours game, where you try to express various numbers in terms of four 4s and whatever operations you may wish.

This is the corresponding game with only one 4; accordingly, we only use unary operations, and only those which return integers.  What numbers can be expressed by starting with a 4, using factorials to go up, floored square roots to come down, going back and forth between these as desired.  Mel Hochster has verified by computer that all positive integers up to 1000 are so expressible and conjectures that all positive integers are.

But how to prove it.  He says that he asked Conway, who said something like “It’s hopeless.”  Not encouraging, sure, but I’m a person who spends time working on the Collatz problem, about which Erdős famously said “Mathematics is not ready for such problems.”

Apparently I have no idea when I’m out of my depth.  But it seems an interesting puzzle.  A good place to start seems to be a rather easier question.

Let n be a positive integer.  Let $F(n)$ be the minimal m such that $\left\lfloor (m!)^{1/2^{-k}}\right\rfloor = n$ for some integer $k$.  Can we get any nontrivial estimates on how $F(n)$ grows?

Comparing Nested Binomial Coefficients

August 13, 2010

Lately I’ve been becoming more and more interested in enumerative combinatorics.  Back in the days of contest math problems, I loved counting problems; they were one of my best strengths.  Until the gorgeous sequence of talks by Richard Stanley at January’s Joint Meetings, I never really realized that enumerative combinatorics was of interest to “real, serious” mathematicians.  Now that I know, I’ve been thinking more and more about these problems.

So last weekend at MathFest, I was pleased to learn of the following inequality involving binomial coefficients.

Let $1 be positive integers. $\displaystyle \binom{\binom{c}{b}}{a}<\binom{\binom{c}{a}}{b}$.

Apparently this inequality has been proven, but only by a lengthy and uninspiring computation involving estimating gamma functions.  There is not yet a combinatorial proof.  What do I mean by a combinatorial proof of an inequality?  I mean an interpretation of each of the nested binomial coefficients as the number of objects in some set, and then an explicit bijection of one set with a proper subset of the other.

In this case, I am thinking of $\displaystyle \binom{\binom{c}{b}}{a}$ as counting the number of ways to choose a different (not necessary disjoint) b-element subsets of a set of c elements.  For definiteness I can take the set of c elements to be $\{1,2,3,\ldots, c\}$, list the elements of a subset in increasing order, and list the subsets in lexicographical order.  This suggests the following combinatorial formulation of the inequality.

Let $1 be positive integers.  Let S be the set of $a\times b$ matrices with entries in $\{1,2,3,\ldots, c\}$.  Let $A$ consist of those matrices in S for which the elements in each row are strictly increasing, and the rows are lexicographically strictly increasing.  Let $B$ consist of those matrices in S for which the elements in each columns are strictly increasing, and the columns are lexicographically strictly increasing.  Find an explicit bijection of $A$ of some proper subset of $B$.

Haven’t cracked it yet, but I’m enjoying the attempt.