Tiontobl: A combinatorial game Saturday, Dec 10 2011 

Expository and Georgia Tech and Math.REC and Mathematics , , , , , , , mixedmath 7:52 pm

As a sophomore at Georgia Tech, I took a class on Combinatorial Game Theory with two good friends, David Hollis (now at Reckless Abandon Labs, which he founded) and Michelle Delcourt (now working towards her PhD at UIUC). As a final project, we were supposed to analyze a game combinatorially. The three of us ended up creating a game, called Tiontobl, and we wrote a brief paper. We submitted it to the journal Integers, but we were asked to revise and expand part of the paper. At some point in time, we’ll finish revising the paper and submit it again (it’s harder now, since we’re split across the country – but it will happen).

Nonetheless, I was talking about it the other day, and I thought I should put the current paper out there.

The paper can be found here (tiontobl).

 

Towards an Expression for pi II Wednesday, Apr 20 2011 

Expository and Math.REC and Mathematics , , , mixedmath 2:25 am

Continuing from this post –

We start with cos( \dfrac{\xi}{2})cos(\dfrac{\xi}{4}) ... cos(\dfrac{\xi}{2^n}). Recall the double angle identity for sin: sin2 \theta = 2sin \theta cos \theta . We will use this a lot.

Multiply our expression by sin(\dfrac{\xi}{2^n}). Then we have

cos( \dfrac{\xi}{2})cos(\dfrac{\xi}{4}) ... cos(\dfrac{\xi}{2^n})sin(\dfrac{\xi}{2^n})

Using the double angle identity, we can reduce this:

= \dfrac{1}{2} cos( \dfrac{\xi}{2})cos(\dfrac{\xi}{4}) ... cos(\dfrac{\xi}{2^{n-1}})sin(\dfrac{\xi}{2^{n-1}}) =
= \dfrac{1}{4} cos( \dfrac{\xi}{2})cos(\dfrac{\xi}{4}) ... cos(\dfrac{\xi}{2^{n-2}})sin(\dfrac{\xi}{2^{n-2}}) =
...
= \dfrac{1}{2^{n-1}}cos(\xi / 2)sin(\xi / 2) = \dfrac{1}{2^n}sin(\xi)

So we can rewrite this as

cos( \dfrac{\xi}{2})cos(\dfrac{\xi}{4}) ... cos(\dfrac{\xi}{2^n}) = \dfrac{sin \xi}{2^n sin( \dfrac{\xi}{2^n} )} for \xi \not = k \pi

Because we know that lim_{x \to \infty} \dfrac{sinx}{x} = 1, we see that $lim_{n \to \infty} \dfrac{\xi / 2^n}{sin(\xi / 2^n)} = 1$. So we see that

cos( \dfrac{\xi}{2})cos(\dfrac{\xi}{4}) ... = \dfrac{\xi}{\xi}
\xi = \dfrac{sin( \xi)}{cos( \dfrac{\xi}{2})cos(\dfrac{\xi}{4}) ...}

Now we set \xi := \pi /2. Also recalling that cos(\xi / 2 ) = \sqrt{ 1/2 + 1/2 cos \xi}. What do we get?

\dfrac{\pi}{2} = \dfrac{1}{\sqrt{1/2} \sqrt{ 1/2 + 1/2 \sqrt{1/2} } \sqrt{1/2 + 1/2 \sqrt{ 1/2 + 1/2 \sqrt{1/2} ...}}}

This is pretty cool. It’s called Vieta’s Formula for \dfrac{\pi}{2}. It’s also one of the oldest infinite products.

 

Slow factoring algorithm II Wednesday, Apr 13 2011 

Expository and Math.NT and Math.REC and Mathematics mixedmath 3:57 pm

I was considering the algorithm described in the parent post, and realized suddenly that the possible ‘clever method’ to speed up the algorithm is complete nonsense. In particular, this simply reduces to trial division (except slightly obscured, so still slower). But the partition thing is still pretty cool, I think.

But I’ve suddenty become interested in different factoring algorithms again, and I think that I’ll make a series on factoring methods out there.

 

Blue Eyes and Brown Eyes Friday, Apr 8 2011 

Math.LO and Math.REC and Mathematics , , , mixedmath 6:55 pm

This is a puzzle I heard on a much smaller level while I was in my freshmen year of college. Georgia Tech has a high school mathematics competition every spring for potential incoming students. The competition comes in rounds – and those that don’t make it to the final rounds can attend fun mathematical talks. I was helping with the competition and happened to be at a talk on logic puzzles, and this came up.

I bring it up now because it has raised a lot of ruckus at Terry Tao’s blog. It doesn’t seem so peculiar to me, but the literally hundreds of comments at Terry’s blog made me want to spread it some more. There is something about this puzzle that makes people doubt the answer.

I have reposted the puzzle itself, as written by Terry. But for his included potential ‘solutions,’ I direct you back to his blog. Of course, the hundreds of comments there also merit attention.

Terry’s puzzle:

There is an island upon which a tribe resides. The tribe consists of 1000 people, with various eye colours. Yet, their religion forbids them to know their own eye color, or even to discuss the topic; thus, each resident can (and does) see the eye colors of all other residents, but has no way of discovering his or her own (there are no reflective surfaces). If a tribesperson does discover his or her own eye color, then their religion compels them to commit ritual suicide at noon the following day in the village square for all to witness. All the tribespeople are highly logical and devout, and they all know that each other is also highly logical and devout (and they all know that they all know that each other is highly logical and devout, and so forth).

Of the 1000 islanders, it turns out that 100 of them have blue eyes and 900 of them have brown eyes, although the islanders are not initially aware of these statistics (each of them can of course only see 999 of the 1000 tribespeople).

One day, a blue-eyed foreigner visits to the island and wins the complete trust of the tribe.

One evening, he addresses the entire tribe to thank them for their hospitality.

However, not knowing the customs, the foreigner makes the mistake of mentioning eye color in his address, remarking “how unusual it is to see another blue-eyed person like myself in this region of the world”.

What effect, if anything, does this faux pas have on the tribe?

Note 1:  For the purposes of this logic puzzle, “highly logical” means that any conclusion that can logically deduced from the information and observations available to an islander, will automatically be known to that islander.

Note 2: An essentially equivalent version of the logic puzzle is also given at the xkcd web site.  Many other versions of this puzzle can be found in many places.

 

 

An interesting (slow) factoring algorithm Thursday, Apr 7 2011 

Math.CO and Math.NT and Math.REC and Mathematics , , , , , , mixedmath 3:37 am

After my previous posts (I, II) on perfect partitions of numbers, I continued to play with the relationship between compositions and partitions of different numbers. I ended up stumbling across the following idea: which numbers can be represented as a sum of consecutive positive integers? This seems to be another well-known question, but I haven’t come across it before.

(more…)

 

Perfect Partitions II Thursday, Mar 31 2011 

Expository and Math.CO and Math.REC and Mathematics mixedmath 12:50 am

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.

Previously, we had:

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!

 

Perfect Partitions Monday, Mar 28 2011 

Expository and Math.CO and Math.REC and Mathematics , , , , , , mixedmath 11:32 pm

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:

(more…)

 

Containers of Water II Thursday, Mar 24 2011 

Math.REC and Mathematics and Open , , mixedmath 1:44 am

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.

(more…)

 

Containers of Water: Maybe an interesting question. Tuesday, Mar 22 2011 

Math.REC and Mathematics and Open , , , mixedmath 9:19 am

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.