Wikipedia:Reference desk/Archives/Mathematics/2010 March 30

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.

March 30

Guests at a dinner party

Having decided above that for unique beads on a necklace there are n!/2n ways of ordering them, n>2, allowing rotation and reflection.

How many ways are there of arranging guests around the table at a dinner party, such that every guest has for each ordering a) at least one different neighbour, b) two different neighbours? Thanks 89.242.246.24 (talk) 09:37, 30 March 2010 (UTC)

Are you allowing the reflection and rotation of your guests? :-) •• Fly by Night (talk) 13:45, 30 March 2010 (UTC)

Yes. 84.13.180.45 (talk) 14:00, 30 March 2010 (UTC)

I don't understand the question. Is every guest "unique" ? If so, isn't every guest always adjacent to two different "neighbors", as long as there are at least 3 guests ? Maybe the term "neighbor" is the issue. Do you mean the person who sits next to you or the person whose house is adjacent to yours ? StuRat (talk) 14:10, 30 March 2010 (UTC)

Every guest is unique (how can any human not be unique?). Neighbour here means the person they sit next to. Another way of phrasing it could be: you have n people (always the same n people) who attend a dinner party every week. There are two possible rules: every person must always either A) sit next to one person they have never sat next to in any previous dinner party, or B) sit between two people they have never sat next to in any previous dinner party. How many weeks could they keep going for if rule A applies, or if rule B applies? The rules are not mixed or swapped: they apply one or the other consistently for as long as it takes to exhaust all the combinations of arrangements. 84.13.180.45 (talk) 14:16, 30 March 2010 (UTC)

Ad rule B: if n ≥ 3, an obvious upper bound is $\lfloor (n-1)/2\rfloor$ weeks, since any fixed person has only n − 1 potential neighbours, and two of these are used up every week. If n is an odd prime, this bound is indeed exact: in week i (where i = 1, ..., (n − 1)/2), put person number ij mod n in the jth chair (numbered in clockwise order around the table). The neighbours of person number k in ith week are then (k ± i) mod n, which are all distinct.—Emil J. 16:54, 30 March 2010 (UTC)

In fact, the same construction can be used for any n, provided the week labels i are only taken coprime to n (and still less than n/2). This shows a lower bound of $\varphi (n)/2$ weeks for any n ≥ 3, where $\varphi$ is the totient function.—Emil J. 17:37, 30 March 2010 (UTC)

While I was away I did likewise realise that the upper bound would be n-1 and (n-1)/2 for A and B respectively, as a particular individual would run out of guests to sit next to. Sorry, I do not understand all the jargon - would it be possible to explain or describe in layperson's language please? 78.146.180.118 (talk) 19:22, 30 March 2010 (UTC)

Prime, mod (see also modular arithmetic), coprime. Any other term is unclear?—Emil J. 10:35, 31 March 2010 (UTC)

Well to start with: "If n is an odd prime, this bound is indeed exact: in week i (where i = 1, ..., (n − 1)/2), put person number ij mod n in the jth chair (numbered in clockwise order around the table)." You don't say why an odd prime should be considered, nor do you say what the point of the rest of it is, nor what it means, nor why it is relevant. 78.147.25.63 (talk) 16:27, 31 March 2010 (UTC)

Your question was: you have n people, ...[lot of stuff]... how many weeks could they keep going? My posts provided several partial answers to this question. Let me denote the number of weeks they can keep going (i.e., the answer you said you were looking for) as w(n). I gave an upper bound $w(n)\leq \lfloor (n-1)/2\rfloor$ for all applicable n, and a matching lower bound $w(n)\geq (n-1)/2$ (and therefore $w(n)=(n-1)/2$) valid only if n is an odd prime. I considered an odd prime because the argument only works when it is an odd prime. The rest of that post is a proof of the lower bound, which in this case consists of an explicit description of how to arrange (odd prime) n people in each of the (n − 1)/2 weeks around the table. In the second post, I generalized the lower bound to $w(n)\geq \varphi (n)/2$ for all n, not necessarily prime. If this is not relevant, then I do not understand what is it that you are asking for.—Emil J. 17:00, 31 March 2010 (UTC)

Thank you for a little more explaination. "The neighbours of person number k in ith week are then (k ± i) mod n, which are all distinct." Please explain why the neighbours of person number k in the ith week are "(k ± i) mod n"? And why are they all "distinct"? 78.147.25.63 (talk) 18:25, 31 March 2010 (UTC)

First, if j is such that k ≡ ij (mod n), then the neighbours of k in ith week are i(j ± 1) = k ± i (mod n). Second, k − (n − 1)/2, k − (n − 1)/2 + 1, ..., k − 1, k + 1, k + 2, ..., k + (n − 1)/2 are pairwise distinct modulo n because the difference of any two of them is less than n.—Emil J. 12:35, 1 April 2010 (UTC)

It may help if I give a concrete example. Let n = 13. Here are the seating layouts for (n − 1)/2 = 6 weeks, where the 13 guests are labelled by numbers from 0 to 12:

0—1—2—3—4—5—6—7—8—9—10—11—12—0

0—2—4—6—8—10—12—1—3—5—7—9—11—0

0—3—6—9—12—2—5—8—11—1—4—7—10—0

0—4—8—12—3—7—11—2—6—10—1—5—9—0

0—5—10—2—7—12—4—9—1—6—11—3—8—0

0—6—12—5—11—4—10—3—9—2—8—1—7—0

Now, for example, the neighbours of k = 9 in week i = 5 are (9 − 5) mod 13 = 4, and (9 + 5) mod 13 = 1.—Emil J. 13:10, 1 April 2010 (UTC)

"If j is such that k ≡ ij (mod n), then the neighbours of k in ith week are i(j ± 1) = k ± i (mod n)." Why would the neighbours of k in ith week be i(j ± 1)? You seem to be assuming they are moving around in a simple regular sequence, and I havnt yet seen any evidence that they would do. And why does i(j ± 1) = k ± i (mod n)? 78.149.241.120 (talk) 10:43, 4 April 2010 (UTC)

For Christ's sake, I defined the sequence in this way. No offense, but I give up, this is hopeless.—Emil J. 15:03, 5 April 2010 (UTC)

Taking log of pie sign gives summation sign

Why does taking log of a pie sign give you a summation sign? I can see this is true by plugging in random numbers for the index of pie and expand the terms and then take log, but I just don't see immediately how a log of pie sign gives you a summation sign. Is it something that should be just memorized?

If you take log of a summation sign, do you get a pie sign? —Preceding unsigned comment added by 142.58.156.64 (talk) 16:49, 30 March 2010 (UTC)

The log of a product is the sum of the logs, that is one of the most fundamental rules of logarithms (since log is the inverse of exp, it follows directly from the rule that a^maⁿ=a^m+n). There are a few technicalities required to prove it works for an infinite product, but the principle is the same. BTW, it's "pi", not "pie", it's a Greek letter. It's probably better to just called it the "product symbol", since pi has various meanings in different contexts. --Tango (talk) 17:16, 30 March 2010 (UTC)

Small correction: a^maⁿ=a^m+n, otherwise consider a=10, b=1, m,n=2 for a counterexample.--Stephan Schulz (talk) 17:29, 30 March 2010 (UTC)

Of course. I got lost in all the sup tags and put the wrong letter! Fixed now. Thanks. --Tango (talk) 17:56, 30 March 2010 (UTC)

I presume you are referring to $\log \left(\prod _{i=1}^{N}x_{i}\right)=\sum _{i=1}^{N}\log(x_{i})$. For N = 2, this is $\log(x_{1}x_{2})=\log(x_{1})+\log(x_{2})\,$. You can prove the general formula by induction using just that identity. --COVIZAPIBETEFOKY (talk) 17:17, 30 March 2010 (UTC)

As for your second question, no, $\log \left(\sum _{i=1}^{N}x_{i}\right)\neq \prod _{i=1}^{N}\log(x_{i})$. For N = 2, this is $\log(x_{1}+x_{2})=\log(x_{1})\log(x_{2})\,$. A counterexample, if we're taking logarithms base b (which I've suppressed), is $x_{1}=x_{2}=b\,$. In that case, $\log(x_{1}+x_{2})=\log(b+b)=\log(2b)=\log(2)+\log(b)=\log(2)+1\neq 1=(1)(1)=\log(b)\log(b)=\log(x_{1})\log(x_{2})\,$. --COVIZAPIBETEFOKY (talk) 17:28, 30 March 2010 (UTC)

And of course, what you do have is $\exp \left(\sum _{i=1}^{N}x_{i}\right)=\prod _{i=1}^{N}\exp(x_{i})$ and more generally $a^{\sum _{i=1}^{N}x_{i}}=\prod _{i=1}^{N}a^{x_{i}}$. -- Meni Rosenfeld (talk) 19:34, 30 March 2010 (UTC)

Simple/Compound Interest Comparison

I'm having trouble with the following theoretical problem. I can graph the accumulation functions for simple and compound interest and verify the relations as required, but I can't find a way to prove when compound > simple and vv. The problem is as follows:

Suppose that $i>0$. Show that

(i) if $0<t<1$ then $\left(1+i\right)^{t}<1+it$, and

(ii) if $t>1$ then $\left(1+i\right)^{t}>1+it$.

174.16.186.231 (talk) 22:40, 30 March 2010 (UTC)

Do you know about the Taylor series for exp(x)? 66.127.52.47 (talk) 01:31, 31 March 2010 (UTC)

Thanks for the reply. Are you saying I should be using the Maclaurin series expansion of $\left(1+i\right)^{t}$?

$\left(1+i\right)^{t}=1+\ln \left(1+i\right)\cdot t+{\frac {\left(\ln \left(1+i\right)\cdot t\right)^{2}}{2!}}+{\frac {\left(\ln \left(1+i\right)\cdot t\right)^{3}}{3!}}+\cdots$

174.16.186.231 (talk) 08:09, 31 March 2010 (UTC)

I'd go about it differently. To show (ii), let $f(i)=(1+i)^{t}-(1+it)\;\!$. Show that $f''(i)>0\;\!$ for $i\geq 0$ and use that to prove that $f(i)>0$ for $i>0$. (i) then follows easily from (ii). -- Meni Rosenfeld (talk) 09:57, 31 March 2010 (UTC)

Thanks for the input Meni - I think I have this worked out now. Since

$\left(1+i\right)^{t}>0$ and

$\left(\ln \left(1+i\right)\right)^{2}>0$ for $i>0$,

we have

$f''\left(i,t\right)=\left(1+i\right)^{t}\cdot \left(\ln \left(1+i\right)\right)^{2}>0$ for $i>0$.

But $f\left(i,0\right)^{=}f\left(i,1\right)^{=}0$, so

$f\left(i,t\right)<0$ for $0<t<1$, and

$f\left(i,t\right)>0$ for $t>1$, as required.

Any holes in my argument here?

174.16.186.231 (talk) 16:51, 31 March 2010 (UTC)

That's actually a different argument from what I had in mind (I was keeping t fixed and differentiating wrt i) but looks like this works too. I think you need to be more precise about why from $f''>0,f(i,0)=f(i,1)=0\;\!$ it follows that $f(i,t)<0,\ 0<t<1$ and $f(i,t)>0,\ t>1$. -- Meni Rosenfeld (talk) 18:17, 31 March 2010 (UTC)

I agree, although I'm not sure how to better explain the logic. Thanks again.

174.16.186.231 (talk) 19:21, 31 March 2010 (UTC)

You can start by showing that $f'(0)<0,\ f'(1)>0$. -- Meni Rosenfeld (talk) 08:12, 1 April 2010 (UTC)