ChapterZero » 2005

First Putnam problem

Mathematics — Alex @ 9:37 am

I’ve made a deal with another guy hear at UH to help me study for the Putnam competition: we’ll be working on the A problems from the 85-90 competitions. Luckily, I bought a book with all the problems and solutions from 85-2000 this summer, so I’m set. Here’s the first one I’m working on:

A1 (1985). Determine, with proof, the number of ordered triples of sets which have the property that

$A_1 \cup A_2 \cup A_3 = \{1,2,3,4,5,6,7,8,9,10\}$ , and

$A_1 \cap A_2 \cap A_3 = \emptyset$

where $\emptyset$ denotes the empty set. Express the answer in the form , where ,,, and are nonnegative integers.

I’ll post my solution when I get one. Feel free to let me know yours

First Attempt: Let i+j+k=10

and $i\neq 0 \neq j \neq 0 \neq k$ , then what we’re looking for is $Q = \sum_{i,j,k} \binom{10}{i}\binom{10-i}{j}\binom{10-i-j}{k} = \sum_{i,j,k} \binom{10}{i}\binom{10-i}{j}$ . That is, $Q = \sum_{i=1}^8 \sum_{j=1}^{9-i} \binom{10}{i} \binom{10-i}{j} = \sum_{i=1}^8 \binom{10}{i} \sum_{j=1}^{9-i} \binom{10-i}{j}$ . Let m=10-i

, then $\displaystyle Q = \sum_{i=1}^8 \binom{10}{i} \sum_{j=1}^{m-1} \binom{m}{j} = \sum_{i=1}^8 \binom{10}{i} \left( \sum_{j=0}^m \binom{m}{j} - \binom{m}{0} - \binom{m}{m} \right) .$ Substituting back, $Q = \sum_{i=1}^8 \binom{10}{i} (2^{10-i}-2) .$ Doesn’t seem quite right, some how, but I’m going to continue on, and see if I can factor it when I’m done.

Hmmm, thanks to Ronald’s comment, it seems that I’ve been doing the problem all wrong— the intersection of all three sets is empty— I was working as though the sets were mutually independent.

Possibly relevant posts:

Prime factorizations of Binomial coefficients (1/13/2005)
an ‘official’ Putnam sample problem (1/21/2005)
Not a frame, but Bessel (5/26/2006)

Comments (3)

And so it begins, again

General — Alex @ 5:04 pm

Today was the first day of the semester, and frankly, I’m already tired of school. I am tempted to drop my engineering classes and take all the courses I need to graduate with my math degree, but what’s the point? I didn’t apply at any grad schools last semester, because I thought it would be a good idea to take the extra year to finish both my math and engineering degrees, so I would have a free semester— enough time to spend more money than I can afford, but not enough to get a decent job. But now, when I hear everyone that has been taking engineering courses along with me is taking Senior Design this semester— the pointless, time-consuming class that is the final requirement for graduation— I start doubting the sanity of my choice. After all, I know math is what I want to do, so why finish the engineering degree? Anyhow, I have committed myself irrevocably to this course of action, so I must see it through. I just hope this strange fatigue isn’t the first sign of a burnout.

Possibly relevant posts:

Just about done with Math (6/13/2005)
To do, to school (8/19/2003)
Course planning (5/4/2005)

Comments (1)

Hyperbolic Areas

Mathematics — Alex @ 10:27 am

Recall that $\cosh(u) = \frac{e^u + e^{-u}}{2}$ and $\sinh(u) = \frac{e^u - e^{-u}}{2}$ parameterize the (unit?) hyperbola x^2-y^2=1 in the same way $\cos(\theta)$ and $\sin(\theta)$ parameterize the unit circle. But, if the parameter $\theta$ is in radians, it also indicates the arc length along the circle from (1,0) . However, under the Euclidean arc length, the parameter doesn’t represent the arc length from (1,0) , unfortunately.

However, recall that in the unit circle, $\theta$ is also the area enclosed by that sector of the circle. A similar fact is true for : If the hyperbola is parameterized as $\left(\cosh(a), \sinh(a)\right)$ , find the area bounded by the point $\left(\cosh(u), \sinh(u)\right)$ , the hyperbola itself, the x-axis, and the point $\left(0,0\right)$ . Interesting, isn’t it?

I worked on that problem, earlier in the week, while reading an excellent book called “The Geometry of SpaceTime: An Introduction to Special and General Relativity” by James J. Callahan. So far, this just seems like thought-provoking trivia that popped up along the way, but maybe it has some significance to the theory. I recommend this book to anyone who is looking for a gentle but detailed introduction to relativity and the mathematics it uses: I’ve tried reading several books, and own at least two that cover the same topic, but all I’ve seen before are written for physics students. This one is purely mathematical— and nicely so: there are actual proofs, and no handwaving—, yet seems to explain the physical theory better than the others. The only prerequisites are linear algebra and multivariable calculus.

Possibly relevant posts:

Comments (0)

Hardware hacking

General — Alex @ 2:46 pm

Ahh… every once in a while, I am reminded of the things I thought I was going to be able to do after getting a BSEE– and I laugh at how naieve I was.

Today, the reminder came in the form of a sweet project to make a mini MP3 player that fits in an Altoid can, and can interface with your car by broadcasting over FM; all for about $50. There are a couple more at the same site, but this is definitely the coolest.

Unfortunately, we don’t learn anything useful at UH: soldering, PCBs, how to hook things together, … nothing!

Maybe I can get the guy that wrote the page to recommend some resources for me to get started.

Possibly relevant posts:

victory is mine over probability! (3/28/2007)
Final grades are in (12/19/2001)
Due South (3/26/2002)

Comments (0)

Prime factorizations of Binomial coefficients

Mathematics — Alex @ 3:12 am

Here’s an interesting problem just posted on Isabel’s math blog:

take the sequence of binomial coefficients

$\binom{2k}{k}, \binom{2k+1}{k}, \binom{2k+2}{k},\ldots$

and determine the prime factorizations. For a given , what is the least number of prime factors of any member of this sequence, counting by multiplicity? Call this number . For example, we say that has four prime factors. An unambiguous way to say this would be to determine which member of the sequence has the smallest number of prime powers dividing it.

Update: I’ve starting attempting this problem, using Legendre’s formula

$\displaystyle n! = \prod_{p \leq n} p^{\sum_{m=1}^\infty \lfloor \frac{n}{p^m} \rfloor},$

where is a prime. Using it, you can reformula the problem as one of, for a given , finding the which minimizes

$\displaystyle \sum_{p \leq 2k + n} \sum_{m=1}^\infty \left( \lfloor \frac{2k+n}{p^m} \rfloor - \lfloor \frac{k}{p^m} \rfloor - \lfloor \frac{k+n}{p^m} \rfloor \right).$

That’s about as far as I got.

Possibly relevant posts:

Kronecker’s Method of Factoring Polynomials over $\Q[x]$ (2/19/2005)
First Putnam problem (1/19/2005)
One direction in Khintchine’s inequality for Rademacher sums (9/26/2008)

Comments (0)

Measures (of Sets)

Mathematics — Alex @ 4:18 pm

One of several mathematical concepts that I keep encountering, and don’t apparently (determined from postings to math newsgroups and talking on a math IRC channel) have the background to comprehend completely, is that of a measure of a set.

I can’t count the number of places that the idea of measurability has popped up in my browsing; the most obvious, and the only one I can readily recall, is integration. If I have it correctly, an integral is a type of measure, and (therefore?) only measurable sets are integrable. That raises the question for me, what does it mean to integrate a set? I can sort of see, if that set can be represented by a Reimann integrable function– you are measuring the area under the function represented by the set of (x,y) pairs.

I finally got some clue as to what a measure is in the past few days. First I read something about how n-dimensional figures ‘naturally’ have n measures, in the same manner that a three dimensional figure has a volume, surface area, and some type of length/depth/etc. Then I saw this:

The idea behind the concept of a measure is that of assigning a non-negative, possibly infinite number to many of the subsets of a given set in such a fashion that the number represents a quantity associated with the set.

What a simple, intriguing, completely vague, yet incredibly promising definition that is. Moral: don’t listen to all those people who say you aren’t educated enough to grasp the essentials of something you are interested in; chances are, they just aren’t articulate enough to express the idea in plain language. That seems to be a big problem in math circles, even in (especially in?) the literature.

Possibly relevant posts:

Today in complex analysis… (2/22/2005)
Contractivity (12/27/2005)
Integrability of matrix functionals (10/6/2008)

Comments (5)

Potential Energy

General — Alex @ 5:03 pm

The physical concept of energy is one that has always fascinated me. I remember in high school when we covered the chapter on kinetic and potential energy, and I spent a long time trying to come to terms intuitively with the concept. I still haven’t— for that matter, I don’t have a firm grasp of forces. I can memorize the formulas and definitions, but those seem like after the fact justifications, but I don’t grok the idea. I can’t say I understand the concept until I see what motivated Newton and his contemporaries to come up with it.

Recently I saw a nice derivation of potential energy that takes some of the mystique out of that arena, and naturally develops all the minutae about potential energy that can be difficult for me to remember; unfortunately, it starts from the definition of kinetic energy, so I need to find a separate rationale for that. Anyhow, here’s the development.

Let $T = \frac{1}{2} m v^2$ be your potential energy, then $\dot{T}=mv \dot{v} = ma v = Fv$ . Fix x_0 as the starting position of the object, and assume it has a starting velocity, and therefore an inital kinetic energy of T_0 . Then

$T(t) = \int_{t_0}^t Fv\; dt + T_0 = \int_{x_0}^x F dx + T_0$

Define the potential energy $V = \int_{x}^{x_0} F dx$ and for convention’s sake, let E = T_0 , then we have the relation

If depends on position only, is only a function of , and this relation is very powerful— unless someone who knows better lets me know, I think this is the only situation in which this relation is useful, but it always holds even if is more complicated. Two of the aforementioned minutaie that this derivation makes explicit are the relation between and , and the definition of : $V = - \int_{x_0}^x F dx$ , so $F = -\frac{dV}{dx}$ ; I always tripped on these negative signs, but the derivation makes their source obvious.

Clearly this is a purely mathematical derivation, but it makes more sense than the ‘physical’ explanations I’ve been given of the ‘meaning’ of potential energy. Without getting into philosophy, it seems clear that this is just a simple of case of exploiting the relationship x + (-x) = 0 . It also makes it explicit that the same procedure can be extended for conservative forces in higher dimensions.

Possibly relevant posts:

Physical Semantics (7/2/2002)
Update (7/9/2002)
Dif. Eq. (8/29/2002)

Comments (2)

Java does Regular Expressions

Programming — Alex @ 3:44 pm

I don’t think I’ll be using my IllustRender plugin too often— the effort required is such that I will either have to be working on a well-planned post, or have gained a lot more familiarity with MetaPost and Postscript than I currently have. Even taking those factors into consideration, it seems like it would be annoying to have to save the post every now and again while working on it, simply to check that an illustration is developing as planned. So I wrote a utility (in Java) along with a simple extension to the plugin that lets you enter the code in it, and shows the results that IllustRender would give, minus the overhead of the browser. You can save and load code too. The idea is that you use this utility to develop the code on your desktop, then put the finished code into your entry. I just had the thought of implementing cut and paste (don’t know why I’m now thinking of it)— but I think Java automatically supports that— if not, I’m sure it won’t be too hard to handle. I’m going to finish testing it, and then add it to the plugin.

Java supports regular expressions automatically! I had always thought that you had to download third party libraries for that; and maybe you did, in JDKs before 1.4. But apparently, Sun added an API for regexps (Perl style!) in the package java.util.regex. Until I discovered that this morning, I was debating whether to hand code any future finite state automata I might need for regular expression parsing tools, to maintain a nice portable and self contained code base, or to be lazy and find a third party library. After checking out the section of the Java Tutorial on the java.util.regex package, however, looks like I can accept no compromises. Now, I can tackle one of those projects I always have on the backburner: an XBEL, multi-browser capable, cross-platform, user friendly, extensible, small footprint bookmark manager. Of course, there are already a ton of projects to create bookmark managers which have several of these features, but none of the ones I’ve encountered have all. It’s either that they must be installed instead of simply ran from the desktop, are not cross-platform, are unreasonably large, are not easily extensible (I don’t want to have to hack the core code), are not user friendly (please, give me a more flexible GUI than the bookmark manager in Opera and IE— at the least, one on par with Firefox, but even that can be improved), don’t support XBEL, can’t auto-upload/-download to a specified location, don’t export back to the browsers that the bookmarks were imported from, or aren’t free.

I think Java is an ideal tool for the job, now that I see it has regexp support. Swing can handle the GUI stuff, and there are APIs out there for using XML with Java that I can look into. The handling of specific browsers can be done via a plug-in architecture, which judging from this article will be a breeze to implement.

Possibly relevant posts:

Page parsing quandry (6/17/2005)
Java Web Start (1/30/2005)
The sad reality of Scheme (3/11/2005)

Comments (1)

An Inversion Theorem for Formal Power Series

Mathematics — Alex @ 6:16 pm

I ran across a very interesting theorem concerning the inversion of formal power series. Recall that if $\{a_n\}$ is a sequence of numbers, then the associated function $A(s) = \sum_{n=0}^\infty a_n s^n$ is called a formal power series; note that A(s) does not need to converge for any particular value of (other than 0)— hence the qualifier ‘formal’. Another name for a formal power series is a generating function, because it is associated with, or generates the sequence $\{a_n\}$ .

Let $A(s) = a_0 + a_1s^1 + a_2s^2 + \ldots$ and $B(s) = b_0 + b_1s^1 + b_2s^2 + \ldots$ be two formal power series and suppose B(0)=b_0 = 0 . Then
$A(B(t)) = a_0 + a_1b_1 t + (a_1b_2 + a_2b_1^2)t^2 + (a_1b_3 + 2a_2b_1b_2 + a_3b_1^3)t^3 + \ldots$ .

Here’s the interesting theorem:

Let a function $B(t) = b_1t + b_2 t^2 + b_3t^3 + \ldots$ be such that and $b_1 \neq 0$ . Then there exist functions
$A(s) = a_1 s + a_2 s^2 + a_3 s^3 + \ldots$ and $C(s) = c_1 s + c_2 s^2 + c_3 s^3 + \ldots$ such that and . Each of the functions and is a unique function possessing this property.

The function is said to be the left inverse of ; is said to be the right inverse. The interesting thing about this theorem is that polynomials are formal power series, so it says that every polynomial has a right and left inverse formal power series. Also, if the polynomial is one like x + x^3 whose range is $\mathcal{R}$ , the left inverse is a power series that converges on all of $\mathcal{R}$ .