# Monthly Archives: March 2011

## Perfect Partitions II

In continuation of my previous post on perfect partitions, I seek to extend the previous result to all numbers, not just one less than a prime power.

The number of perfect partitions of the number $p^\alpha -1$ is the same as the number of compositions of the number $\alpha$.

Today, we will find a relation for the number of perfect partitions of any positive integer $n$. The first thing we note is that every number n can be written uniquely as:

$n = {p_1}^{\alpha _1}{p_2}^{\alpha _2} *…* {p_n}^{\alpha_n} – 1$ , where each of the p are distinct primes.

Parallel to the last result, we can see that the number of perfect partitions of the number ${p_1}^{\alpha _1}{p_2}^{\alpha _2} *…* {p_n}^{\alpha_n} – 1$ is the same as the number of ways to factor

$\dfrac{x^{{p_1}^{\alpha _1}{p_2}^{\alpha _2} *…* {p_n}^{\alpha_n} – 1} – 1}{x – 1}$.

This can immediately be proved by extending the previous post: still use finite geometric series and the positivity of the terms to show that each exponent can be reached in exactly one way. The different factors would again be of the form:

$\dfrac{1 – x^\gamma}{1-x^\delta}$ where $\delta | \gamma$.

In this fashion, we see that the number of perfect partitions are the same as the number of ordered factorizations of ${\alpha _1}{\alpha _2} *…* {\alpha_n}$. But we haven’t really considered this yet. How many ordered factorizations are there? This is unfortunately beyond the scope of this post, but Sloane’s has that sequence here, and there is a Dirichlet generating function: $f(s) = \dfrac{1}{2 – \zeta(s)}$.

As an aside that made more sense in the original post, I consider the number of compositions of a number. How many compositions are there for a number n?

I hadn’t seen this before, but upon consideration I see that it is a very simple exercise that one might encounter. Imagine we are thinking of the number of compositions of n. Then $n = 1 + 1 + 1 … + 1$. But then each ‘+’ symbol might be replaced by a separator, so that for example $1 + 1 + 1$ might be $1 + 1, 1 = 2, 1$. So we see that there are always $2^{n-1}$ different compositions of the number n. So we now know the number of partitions of each number n!

Posted in Expository, Math.CO, Math.REC, Mathematics | 3 Comments

## A Bag’s Journey in Search of its Owner

This is the story of a bag,
who lost its owner and trav’led the whole world!
And though it left with lots o’ tags attached,
She absolutely lost it, when she flied.

How many days would it be?
She arrived with hope, but found only tears.
The bag just disappeared,
so she flew in without any gear.
But she gets a call the next morning,
“Where are you, your bag is right here!”
Thousands of miles afar.
When she looks in the mirror so how does she choose?
The same clothes worn day after day.
When travelling homeward bound,
her bag seems never to be found.

This is the story of a bag,
who lost its owner and trav’led the whole world!
And though it left with lots o’ tags attached,
She absolutely lost it, when she flied.

[loosely to “Story of a Girl”]

This is one of those strange stories – girl gets ready for flight from Atlanta to New York to Prague, girl ends up going Atlanta to Norfolk to New York to Prague, but bag ends up going Atlanta to New York to Atlanta to New York to Prague to New York to Atlanta to a warehouse to Atlanta to New York to Prague to Krakow… you know, the typical story. To be fair, the flight change through Norfolk as opposed to a direct to New York was last minute, and it makes sense for the bag to have been detained in New York. Perhaps it would make it on a later flight to Prague – such is life.

But nothing so simple occurred. The bag makes it to Prague, and when the girl notes that the bag should be sent to her home, one might expect the story to end. Instead, the bag ends up back in New York, then back in Atlanta. Of course, girl doesn’t know this – it’s all a big mystery (as she borrows friends’ clothing, of course). Fortunately, a Delta worker named Carl (I think) finds this bag and its tag in this warehouse, looks it up and calls girl. Girl asks for it to be shipped to her – no problem, he says. Carl is very good at his job, I think, and I commend him. Unfortunately, the bag gets to Prague again and somehow whatever instructions were once somehow connected to the bag are lost. So now someone at Prague calls up girl – what do you want to do with this bag? So the bag goes to Krakow, but that’s okay. That’s where the girl found the bag.

A very logical route, one might say.

Posted in Humor, Story | Tagged , | 1 Comment

## Perfect Partitions

I was playing with a variant of my Containers of Water question where we were instead interested in solid weights on a scale. It occurred to me that, as is often the case, I should consider easier problems first and see what comes of them. Ultimately, this led me down a path towards the idea of a ‘perfect partition’ and a few papers published in the late 1800s by MacMahon. Here’s how that went:

Posted in Expository, Math.CO, Math.REC, Mathematics | | 2 Comments

On 8 March 2011, Dr. Thomas Weiler and graduate fellow Chiu Man Ho of Vanderbilt put a paper on another possibility of achieving a sort of time travel. This apparently got a good deal of press at the time, as both CBS and UPI actually picked up the story and ran with it.

Why do I mention this? It is most certainly not because I have a dream or hope of time travel – quite the opposite really. In the past, I have talked of how surprised I was at the lack of hype coming out of the LHC. The last terrible bit I heard was a sort of rogue media assault on the possibility of the LHC creating a black hole and thereby destroying everything! But that was years ago and not stirred up by the high energy physics community.

As an aside, it did provide the very comical http://hasthelargehadroncolliderdestroyedtheworldyet.com/, which includes a very simple answer and funny source code. By the way, no – as far as we can tell, it hasn’t yet destroyed the world.

Let’s get clear – I don’t think that hype is bad. Dr. Weiler himself noted the speculative interest in this idea and that it’s perhaps not the most likely theory. And it doesn’t contradict M-Theory, apparently. I know nothing of this, so I can’t comment. But I can say that such fanciful papers are wonderful. This sort of free form play is liberating, and exactly the same sort of thing that drew me into science. What can we say about the world around us that goes along with what we know? Whether it’s correct or not is something that can be explored, but it’s just an idea.

For those who don’t want to read the article, Dr. Weiler and Chiu Man Ho allude to the possibility of transferring Higgs singlets (a relative to the as-yet-only-hypothesized Higgs Boson) to a previous time. So no, unfortunately we cannot yet fix the problems of our past.

Nonetheless, there should be more hype about the LHC. The test schedule on the collider is becoming more intense all the time. Very exciting.

## A Question on Stoplights

Consider stopping at a traffic light: the normal way of things is that all the cars are packed tightly together. Decorum decrees that one waits for the car ahead to accelerate at a green light, lest accidents occur. But is that really necessary? What if instead, the cars left somewhere between a half and a full car length between them so that they could all accelerate at a green light (and still have enough time to slow down/stop if they accelerate too quickly)? Is this efficient or not? Is there any change in traffic flow?

My thinking is that in long lines, to have every car accelerate at the (almost) same time would yield faster traffic flow, but perhaps that’s misguided. But I’m thinking of doing a simple study of the idea, just to see what happens.

Happy weekend!

## A late pi day post

As this blog started after March 14th, it hasn’t paid the proper amount of attention to $\pi$. I only bring this up because I have just been introduced to Christopher Poole’s intense dedication to $\pi$. It turns out that Christopher has set up a $\pi$-phone, i.e. a phone number that you can call if you want to hear $pi$. It will literally read out the digits of $\pi$ to you. I’ve only heard the first 20 or so digits, but perhaps the more adventurous reader will find out more. The number is 253 243-2504. Call it if you are ever in need of some $\pi$.

Of course, I can’t leave off on just that – I should at least mention two other great $\pi$-day attractions (late as they are). Firstly, any unfamiliar with the $\tau$ movement should read up on it or check out Vi Hart’s pleasant video. I also think it’s far more natural to relate the radius to the circumference rather than the diameter to the circumference (but it would mean that area becomes not as pleasant as $\pi r^2$).

Finally, there is a great musical interpretation and celebration of $\pi$. What if you did a round (or fugue) based on interpreting each digit of $\pi$ as a different musical note? Well, now you can find out!

Until $\tau$ day!

Posted in Mathematics, Story | Tagged , | 1 Comment

## Containers of Water II

In a previous post, I considered the following two questions:

Questions
What sets $S$ maximize $|{\bf F}(S;p)|$ for various $p$?
What sets $S$ maximize $\lfloor {\bf F}(S; p) \rfloor$ for various $p$?

I then changed the first question, which I think is perhaps not so interesting, to the following:

What sets $S$ maximize $|{\bf F}(S;p)|_c$, where $|\cdot|_c$ denotes the largest connected interval of results?

Let’s explore a few cases to see what these answers might look like.

Posted in Math.REC, Mathematics, Open | | 1 Comment

## 2401: Missing recitation

As I went to visit Brown on the 16th-18th, I had my friend Matt cover recitation. As we have started considering double and triple integrals, and iterated integrals in particular, I thought I could point out a very good site for brushing up on material. I think it can act as a wonderful supplement to the lecture and recitation material. The Khan Academy is an online information center built around the idea that video presentations and video lectures can give intuition without adding any pressure – you can rewatch anything you’ve missed, repeat important parts, etc. all without feeling like you’re wasting someone’s time. While most of the Khan material is aimed at primary and secondary school, they happen to have a multivariable calculus section (although it’s far insufficient to Tech’s course material – don’t think of this as a replacement, but instead as merely a supplementary way to build intuition).

Here are links to the Khan Academy website, and links to 5 lectures that I think are relevant to material I would have covered.

I encourage you to check them out before we meet again for recitation.

## Containers of Water: Maybe an interesting question.

Consider the old middle-school type puzzle question: Can you measure 6 quarts of water using only a 4 quart bottle and a 9 quart bottle? Yes, you can, if you’re witty. Fill the 9 quart bottle. Then fill the 4 quart bottle from the 9 quart bottle, leaving 5 quarts in the 9-bottle. Empty the 4-bottle, and fill it again from the 9-bottle, leaving only 1 quart in the 9-bottle. Again empty the 4-bottle, and pour the 1 quart from the 9-bottle into it. Now fill the 9-bottle one last time and pour into the 4-bottle until it’s full – at this time, the 4-bottle has 4 quarts and the 9 bottle has 6 quarts. Aha!

But consider the slightly broader question: how many values can you get? We see we can get 1, 4, 5, 6, and 9 already. We can clearly get 8 by filling the 4-bottle twice and pouring this bottle into the 9. With this, we could get 4 by filling the 4-bottle again and then pouring as much as possible into the 9-bottle when its filled with 8 – as this leaves 3 quarts in the 4-bottle. Finally, we can get 2 by taking 6 quarts and trying to pour it into an empty 4-bottle. (With 2, we get 7 by putting the 2 into the 4-bottle and then trying to pour a full 9-bottle into the 4-bottle). So we can get all numbers from 1 to 9. If we were really picky, we could note that we can then easily extend this to getting all numbers from 0 to 13 quarts, albeit not all in one container.

If you go through these, it turns out it is possible to get any number between 0 and 13 quarts with a 4-bottle and a 9-bottle in at most 10 pours, where a pour includes filling a bottle from the water source (presumably infinite), pouring from one bottle into another, or emptying the water into the water source. Now I propose the following question:

Given only 2 bottles (of an integer size) and up to 10 pours, what is the largest N s.t. we can measure out 0, … , N quarts (inclusive)?

As is natural, let’s extend this a bit further. For any subset of the natural numbers $S$ and for a number of pours $p$, define

${\bf F}(S; p) :=$ the set $R$ of possible results after using at most $p$ pours from containers of sizes in $S$

For example, we saw above that ${\bf F}(4,9;10) = (0,1, … , 13).$ But is this maximal for two containers and 10 pours? If we only allow 5 pours, the set $R$ reduces to size 7; and if we consider the smallest result not attainable, we get 2 quarts. That is very small! I’m tempted to use $\lfloor {\bf F} \rfloor$ to denote the smallest unattainable positive integer amount, but that’s only a whim.

Ultimately, this leads to two broad, open (as far as I know) questions:

Questions
What sets $S$ maximize $|{\bf F}(S;p)|$ for various $p$?
What sets $S$ maximize $\lfloor {\bf F}(S; p) \rfloor$ for various $p$?

Perhaps these have already been explored? I don’t even know what they might be called.

Posted in Math.REC, Mathematics, Open | Tagged , , , | 5 Comments