Wikipedia:Reference desk/Archives/Mathematics/2009 May 1

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 1

Pairing colours, permutations and such

Argh numbers. I've been trying to work this out manually all evening and I have no idea if it's mathematically possible. I'll try to explain it clearly...bear with me...

• I have a pool of eight colours, four hot and four cold.
• I have six groups of four tiles. Imagine them as currency, valued as 1, 2, 3, and 4.
• I know that a selection of four colours, two hot and two cold, can make six differing permutations, not counting pairing a colour with itself.
• I'm trying to colour each tile so that no colour pairing is repeated anywhere, attempting to use a selection of four colours as above to colour each tile 'denomination'.

Thus far I've always hit a snag. I've no idea how to work it out using magic formulae. Is there a way of doing this?

Lady BlahDeBlah (talk) 00:42, 1 May 2009 (UTC)

Could you clarify a bit - how many colours per tile. 4?

Also if you have four hot colours, and four cold - and pick two of each, then I think you will have 4*3/2=6 choices for hot, and the same for cold. So there should be 6*6 hot/cold combinations = 36 Is that the answer you wanted?

ie there are 36 ways to colour a tile with 2 hot and 2 cold colours, all colours different.

ie you've got six hot tiles (bi-colored) and six cold tiles (bi-colored) to make 36 quad tiles.

(This gets more complex if your tile matters which way round the colours are placed - eg like a 2x2 checkerboard - does it matter if hot is next to hot, or diagonal?)HappyUR (talk) 01:16, 1 May 2009 (UTC)

Eeep. I knew I was being unclear, bugger. It's only two colours per tile. Lady BlahDeBlah (talk) 01:36, 1 May 2009 (UTC)

ok two colours per tile.

Questions:

on a tile - what commbinations of colours to use - is it either hot/hot or cold/cold or something else.

You say 'six groups of four tiles' - is that the same as 24 tiles - is there something special about the four tile groups? Is there some sort of 6x4 grid going on here.

Do you wany to know the number of combinations, and/or a way of generating all the combinations, or maybe something else.?

When you say "..colour each tile so that no colour pairing is repeated anywhere, attempting to use a selection of four colours as above to colour each tile 'denomination' " that means six colour combinations in total to choose from per tile, which sounds like you've already got the answer - unless you meant -"no two adjacent tiles are colour paired in the same way as another two colour tiles" or something like that. CheersHappyUR (talk) 12:41, 1 May 2009 (UTC)

I'm confused. OK You have four hot colours (a,b,c,d) and four cold colours (w,x,y,z). You can have two colours per tile - Is this (two hot or two cold) or is this (one hot and one cold) or this this anything with anything? IE which of the following are valid tiles: The hot tiles: ab, ac, ad, bc, bd, cd; The cold tiles: wx, wy, wz, xy, xz, yz: The hot&cold tiles aw, ax, ay, az, bw, bx, by, bz, cw, cx, cy, cz, dw, dx, dy, dz. This is a set of 6 hot pairs, 6 cold pairs and 16 mixed pairs. (I excluded aa, bb, ww etc from the list as you said you couldn't pair with itself.) Where do "four colours" come into it? Are you trying to then join a hot pair to a cold pair (there will be 6*6=36 ways of doing this). -- SGBailey (talk) 08:08, 1 May 2009 (UTC)

There is a 6x4 grid, yes. I'm trying to design a fictional currency based on small Mah-Jongg tiles, which are generally white with two coloured inks making the design. There are six 'backing tints' of tile, assuming to be differing locale's legal tender: white, black, green, grey, peach and mauve. I'd like for the first four of those to use a combination of colour pairs from the pool of eight that are hot-cold, using all colours once; and the last two to have only hot-hot and only cold-cold. The 'x4' bit comes from the denomination of tile; if you know of Mah-Jongg then think the suits, but basically each of these six legal tenders have 4 general designs.

Um, the 'four colours' bit came from me working out that four colours in their pairs can make six permutations that fit my pattern above, (ont hot, one cold, four both) and I was trying to make that fit but I found I was repeating permutations later on, which I don't want to do. I want to use the colours in an equal spread across the 6x4 table, 6 times each. I don't think the 'four colours' thing is going to work but I have no way of knowing that, hence the post. If this pattern will not work, should I assume that I need 24 out of 36 permutations and I can colour my tiles uniquely? Lady BlahDeBlah (talk) 13:13, 1 May 2009 (UTC)

Right so there are 16 tiles with hot/cold pairs, and 4 tiles with cold/cold pairs, and 4 tiles with hot/hot pairs.

There are 24 tiles, a total of 48 colour spots (2 per tile), and you have 8 colours total, so that means each colour needs to be used 6 times (6*8colours=48) across the whole grid?

If so you will have 8 spots from hot/hot tiles, and 8 spots from cold/cold tiles, that means each hot (and cold) colour will be used twice in these tiles, giving each colour equal preference.

That leaves you with the hold/cold tiles (16) - a total of 16 hot, and 16 cold spots, 1 each per tile. So you need to use each hot (and cold) colour 4 times.

For each colour choice eg "hot1" there are 4 ways of choosing from cold. - just the right number.

It looks like you can do what you want

ie if hot colours =1234, and cold = abcd

you can do:

1a 2b 3c 4d 11 aa

1b 2c 3d 4a 22 bb

1c 2d 3a 4b 33 cc

1d 2a 3b 4c 44 dd

As far as I can tell you have no problems - note there is more than one way to arrange them - the example I gave above is just one.

Comment - the problem is a bit similar to the round robin problem (see Round-robin tournament) - ie where players in a group must play a different player each time in a series of rounds. In this case the players (colours) happen to play each other.. making it different - the links might be useful to you, or might not.

Did I understand the question?HappyUR (talk) 15:20, 1 May 2009 (UTC)

Oh Lady Blah I beg your pardon, for I put a post here by mistake --pma (talk) 05:57, 2 May 2009 (UTC)

Complex integral

I know I can do this integral by using residues. But, I'd probably have to add together like 1004 2008th roots of -1. Is there a trick to do that, or is there some other way to do this? This was on a recent analysis qualifying exam and I'm not sure how to go about it.

$\int _{0}^{\infty }{\frac {1}{1+x^{2008}}}\,dx$

Thanks StatisticsMan (talk) 02:06, 1 May 2009 (UTC)

That wasn't 2048 instead of 2008 was it? i.e. 2¹¹ That's pretty bad and I'm not sure how to do it quickly and cleanly but it's nowhere as bad as 2008 because lots of stuff will cancel out. Dmcq (talk) 10:01, 1 May 2009 (UTC)

The trick to add 1004 2008th roots of −1 together is to observe that they are arranged in a geometric series. — Emil J. 10:37, 1 May 2009 (UTC)

So, the integral (let's denote it by I) is 1/2 of the integral of f(z) = 1/(1 + z²⁰⁰⁸) over a path which goes from −R to R and then by a half-circle in the upper half-place back to −R, for large enough R. Singularities of f in this region are simple poles at a_k = e^kπi/2008 for 0 < k < 2008, k odd. The residue of f at a_k is

${\frac {1}{(1+z^{2008})'(a_{k})}}={\frac {1}{2008a_{k}^{2007}}}=-{\frac {a_{k}}{2008}},$

hence

$2I=-{\frac {2\pi i}{2008}}\sum _{n<1003}e^{(2n+1)\pi i/2008}=-{\frac {2\pi ie^{\pi i/2008}}{2008}}{\frac {-1-1}{e^{\pi i/1004}-1}}={\frac {\pi i(e^{-\pi i/2008}-e^{\pi i/2008})}{502|e^{\pi i/1004}-1|^{2}}}={\frac {2\pi \sin {\frac {\pi }{2008}}}{502\left(2-2\cos {\frac {\pi }{1004}}\right)}},$

and the original integral is

$\int _{0}^{\infty }{\frac {1}{1+x^{2008}}}\,dx={\frac {\pi \sin {\frac {\pi }{2008}}}{1004\left(1-\cos {\frac {\pi }{1004}}\right)}}.$

Not sure I haven't made any mistakes there, but the fact that the result is real and positive is an encouraging sign. — Emil J. 10:56, 1 May 2009 (UTC)

It can't be quite right, as it's easy to see that the integral should be numerically ≈ 1.0. Changing the "+" to a "−" in the denominator gives the right result. Fredrik Johansson 11:29, 1 May 2009 (UTC)

You're right, a silly mistake. Fixed now. — Emil J. 12:02, 1 May 2009 (UTC)

Further simplified, it is $\left(\mathrm {sinc} \left({\frac {\pi }{2008}}\right)\right)^{-1}$. Fredrik Johansson 11:42, 1 May 2009 (UTC)

Yes, I missed that. Now, here's a challenge. The argument above actually shows that

$\int _{0}^{\infty }{\frac {1}{1+x^{n}}}\,dx={\frac {\pi /n}{\sin(\pi /n)}}$

for every even n ≥ 2. What about odd n? — Emil J. 12:57, 1 May 2009 (UTC)

Wow, thanks. That's a good point that it is a geometric series. I do not have time right now to look at this but will later. And, since I'll be studying all summer for this exam, I will be asking many questions here!

As far as n odd, the answer is the same I believe because I saw that Rudin's Real and Complex says it is in some exercise. But, I don't remember where that was in the book because I forgot what I was looking up originally. I will look for it again later. Thanks again, very helpful. StatisticsMan (talk) 13:54, 1 May 2009 (UTC)

Not to mention $\int _{0}^{\infty }{\frac {1}{1+x^{\pi }}}\,dx={\frac {1}{\sin(1)}}$ ... --pma (talk) 17:50, 1 May 2009 (UTC)

Now that's just adorable :-) Fredrik Johansson 20:33, 1 May 2009 (UTC)

(INSerted from another point) - see edit history

Actually EmilJ's formula holds for any real $n>1$ also. It is this: if we change variable in the integral, putting

$x=\left({\frac {t}{1-t}}\right)^{\frac {1}{n}}$

we find

$\int _{0}^{\infty }{\frac {1}{1+x^{n}}}\,dx={\frac {1}{n}}\int _{0}^{1}t^{{\frac {1}{n}}-1}(1-t)^{-{\frac {1}{n}}}\,dt$

But the latter is the Eulerian Beta function, so the integral is

${\frac {1}{n}}B\left({\frac {1}{n}},1-{\frac {1}{n}}\right)={\frac {1}{n}}\Gamma \left({\frac {1}{n}}\right)\Gamma \left(1-{\frac {1}{n}}\right)={\frac {\pi /n}{\sin(\pi /n)}}$,

where in the last equality I used the Euler's reflection formula. --pma (talk) 20:06, 1 May 2009 (UTC)

Pma, did you mean to post the above response below (i.e. in the next section)? --PST 21:59, 1 May 2009 (UTC)

Thank you PST, I think I was not completely self-controlled while editing. BTW, the same identity holds true for complex $n$ with $\scriptstyle \Re (n)>1$, because all passages work as well in the complex case (or just by analityic continuation of both sides of the real identity) --pma (talk) 06:00, 2 May 2009 (UTC)

Thanks, that is very nice to know. StatisticsMan (talk) 19:18, 2 May 2009 (UTC)

Alright, I finally worked through all the details and it works great. I learned a trick or two along the way as well, so thanks. If I were to do this for n odd using residues again, of course the same method does not work because -1 would be a root and would be on the boundary of our region. Would I just choose a similar circle that goes in and around the -1, as in the picture in Example 4 (flipped) on the Methods of contour integration? Also, I will check out that Beta function stuff. I have learned about the Gamma function, but not since undergrad and it's been a while, 8 years or something. But, it's worth looking at it and the Beta function. Thanks StatisticsMan (talk) 01:16, 3 May 2009 (UTC)

To adapt Emil's computation to odd n maybe one could try changing variable with x=y². This gives 1+y²ⁿ in the denominator, although with a 2y in the numerator. And if you manage to do it more in general with y^p in the numerator, you have the value of the original integral for all rational n>1, hence by density for all real n. Having the value of the integral for all real n can be used to give a proof of the Euler reflection formula for the gamma, using the equality I wrote) --pma (talk) 07:11, 3 May 2009 (UTC)

In fact EmilJ's computation works nicely also for

$\int _{0}^{\infty }{\frac {1}{1+x^{\,p/q}}}\,dx$

with integer $\textstyle p$ and $\textstyle q$, $\,p>q>0$, $\,p$ even and $\textstyle q$ odd. With the change variable $\textstyle x=z^{q}$ we first write

$\int _{0}^{\infty }{\frac {1}{1+x^{\,p/q}}}\,dx=q\int _{0}^{\infty }{\frac {z^{q-1}}{1+z^{p}}}\,dz.$

Since the integrand is an even function the integral is

${\frac {q}{2}}\int _{-\infty }^{\infty }{\frac {z^{q-1}}{1+z^{p}}}\,dz,$

and since the integrand is also $\textstyle o(1/|z|)$ for complex $\textstyle z$ as $\textstyle |z|\to \infty$, the residue formula holds for the integration along the real axis as well. One finds:

$\mathrm {Res} \left({\frac {z^{q-1}}{1+z^{p}}},\,e^{i\pi k/p}\right)={\frac {e^{i\pi k(q-p)/p}}{p}},$

which have to be considered for all odd $k$, $0<k<p$, corresponding to the poles of the integrand in the upper half-plane. Summing as before the geometric sum given by the residue formula one eventually gets

$\int _{0}^{\infty }{\frac {1}{1+x^{s}}}\,dx={\frac {\pi /s}{\sin(\pi /s)}},$

for all rational $s={\frac {p}{q}}$ of the above form. By continuity the identity extends to all real s>1 (in fact to all complex s with $\scriptstyle \Re (s)>1$, by analytic continuation). This covers in particular the case of odd integers, even if I find it quite odd that one has to get the value of the integral e.g. for s=3 by approximating with (6N+1)/2N. There are certainly other ways to compute directly the integral. Anyway, as I mentioned the computation is worth since it implies the Euler reflection formula, using the above identity

$\Gamma (z)\Gamma (1-z)=B(z,1-z)={\frac {1}{z}}\int _{0}^{\infty }{\frac {1}{1+x^{1/z}}}\,dx$.

Thanks, I will think about this as well. A friend of mine showed me a nice way today as well. Instead of integrating over all of the upper semicircle, instead just make a sector that contains just one of the roots of the denominator, an angle of pi/1004 in the 2008 example. This method works for odd n as well. It also eliminates the need to add up all the residues. However, that was my question in the first place and I am glad I know how now. The more methods I learn for this type of problem, the better. StatisticsMan (talk) 00:17, 4 May 2009 (UTC)

Exact, that's what I thought also. There is no restriction on parity in the p and q case, also. For $\scriptstyle f(z):={\frac {qz^{q-1}}{1+z^{p}}}$ we integrate around the pole $\zeta :=e^{i\pi /p}$ as you are saying, along the positive real axis and in the direction of $\zeta ^{2}$. Since $f(\zeta ^{2}x)\zeta ^{2}=\zeta ^{2q}f(x)$ the path integral of $f(z)$ along the two half-lines is just

$\textstyle (1-\zeta ^{2q})\int _{0}^{\infty }f(x)dx$,

so by the residue formula we have

$\textstyle (1-\zeta ^{2q})\int _{0}^{\infty }f(x)dx=2i\pi \,\mathrm {Res} (f,\zeta )=-2i\pi {\frac {q}{p}}\zeta ^{q}$

and the $\sin(\pi q/p)$ factor comes out nicely on the left dividing by $-2i\zeta ^{q}$. Nice question, StatisticsMan --pma (talk) 06:38, 4 May 2009 (UTC)

Exponential Addition

What is u where c is a constant and $x^{u}=x+c$. This question may also be stated as the following:
Solve for u where $dc=0,x^{u}=x+c$The Successor of Physics 05:09, 1 May 2009 (UTC)

Consider the logarithm to the base x on either side of the equation. The resultant equation after the perfomance of this operator is $u=\log _{x}(x+c)$ and thus u is the composition of a logarithmic function with a linear function. The most important link of these is logarithmic function. --PST 06:47, 1 May 2009 (UTC)

You might also be interested in Bring radical Dmcq (talk) 10:10, 1 May 2009 (UTC)

It's not a composition of a logarithmic function and a linear function, since the base of the logarithm depends on the variable x that is the argument to the "linear function". Notice that

$u=\log _{x}(x+c)={\frac {\log(x+c)}{\log x}},$

where the base of the logarithmic function may be anything you want. Michael Hardy (talk) 13:07, 2 May 2009 (UTC)

You are right - it is really embarassing to have made that mistake. --PST 00:21, 3 May 2009 (UTC)

Since you were talking about logarithm as a function of the base x too, thus $\log _{x}(y)$ as a two variables function, I found nothing strange or wrong in your post, the linear function composed with the logarithmic being $\scriptstyle x\mapsto (x,x+c)$. At most, maybe, "affine" is more proper than "linear". --pma (talk) 11:51, 3 May 2009 (UTC)

Thanks, guys!The Successor of Physics 12:39, 3 May 2009 (UTC)