Wikipedia:Reference desk/Archives/Mathematics/2009 November 18

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.

November 18

Items from a list

I'm trying to work on a traveling salesman problem. I have 7 locations, and up to 4 can be visited each day, with no repeats in any one day (if location 1 is visited on Monday, it cannot be visited again that day). 26 trips are needed in a week, and I have a list like this: [1,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,5,5,5,6,6,6,6,7,7,7]. I'm trying to figure out the number of arrangements of trips that are possible in 1 week. I used 4!*₇C₄ = 5040 + 2 = 5042 total, but I don't think that this is correct. 149.169.96.160 (talk) 04:32, 18 November 2009 (UTC)

I don't have a verified answer to this - some musings however. The 7C4 gives you the number of possible options for any one day, assuming that all 7 options remain available. I'm not sure what the 4! gives you. If you had [7*1,7*2,7*3,...,7*7] then an answer would be 7C4^7 but you don't have that list and that list would not guarantee each location is visted the right number of times. Alternatively you could add two more locations [8,8] where 8 means 'stay at home and don't visit. This gives you 28 trips in a 7 day week with exactly 4 per day. In which case I guess the answer is 28C4*24C4*20C4*16C4*12C4*8C4*4C4. May well be wrong - ah it is wrong, it allows repeat visits in a day. -- SGBailey (talk) 17:25, 19 November 2009 (UTC)

Last step of a graph theory proof

I am working on a homework problem involving a simple undirected graph, and I've figured out an inductive procedure that reduces the general problem to the case in which the graph is complete, but the key operation that I perform in my inductive step is this:

Find a non-edge in the graph and identify its endpoints.

When I do this, I need to avoid increasing the size of the largest clique in the graph (so that my induction works), so I need to be careful about the non-edge I use. If I perform this operation on a non-edge {x, y} for which there exists a maximum clique Q such that $\{x,y\}\cap Q=\emptyset$ and {x, y} dominates Q, then I form a larger clique. Now it seems that I can always choose a non-edge that works; in other words, it seems that

It is impossible for the following to happen, unless the graph is complete: For every non-edge {x, y}, there is a maximum clique Q such that $\{x,y\}\cap Q=\emptyset$ and {x, y} dominates Q.

Can anyone help me out by providing a counterexample or a hint about how I might prove this? —Bkell (talk) 05:47, 18 November 2009 (UTC)

I think a cycle of length 5 is a counter example. Rckrone (talk) 06:20, 18 November 2009 (UTC)

Ah, of course, thank you. I should have just run through the list of typical counterexamples, I guess. —Bkell (talk) 10:40, 18 November 2009 (UTC)

Fixed Point Existence of an almost-contraction map

Hi all,

I've been trying to conquer this question on and off for a couple months now to no avail and was hoping someone out there might be able to help me out, since it's getting very frustrating!

Let (X,d) be a non-empty complete metric space and let $f:\,X\to \,X$ be a function s.t. $\forall$ positive integer n:

(i) $d(x,y)<n+1\Rightarrow d(f(x),f(y))<n$ and

(ii) $d(x,y)<1/n\Rightarrow d(f(x),f(y))<1/(n+1).$

Must f have a fixed point?

Now I've tried looking for a counterexample on $\mathbb {R}$ but even then I failed to find anything - I really don't have any intuition on this problem leading me either way: I can't see how to prove it or come up with an example to disprove it. Please help! The more detail you can give the better, since I'm clearly quite useless at this!

Thanks very much, Mathmos6 (talk) 05:53, 18 November 2009 (UTC)

Try the following. Let X be the set of positive reals with the standard metric, and f(x) := x/2. I think this satisfies your conditions but has no fixed points. – b_jonas 13:02, 18 November 2009 (UTC) Wait, you said complete metric space. Sorry. – b_jonas 13:03, 18 November 2009 (UTC)

The result holds for X=Rⁿ (or any complete metric space where bounded sets are totally bounded). Still thinking about the general case. Algebraist 13:13, 18 November 2009 (UTC)

Note that in these hypotheses, if the orbit of x₀ is bounded, then it is a Cauchy sequence and converges to a fixed point. But it seems a delicate point to decide whether there can be unbounded orbits. I'd suggest to look for a counterexample, with X:=N and f(x)=x+1: try to find a complete distance satisfying (i) and (ii) in this situation. (then maybe you will find that there is no such a distance and get a hint to prove the result) --pma (talk) 17:14, 18 November 2009 (UTC)

In fact, any point of $\textstyle X$ generates a bounded orbit. Take $\textstyle x_{0}\in X$ and define $\textstyle x_{k}:=f^{\,k}(x_{0})$ for all $\textstyle k\in \mathbb {N} .$ Since by (i) and (ii) we have $\textstyle d(x_{k},\,x_{k+1})\to 0,$ we can assume w.l.o.g. $\textstyle d(x_{0},\,x_{1})<1.$ Then, iterating (ii),

$d(x_{0},\,x_{n})\leq \sum _{k=1}^{n}d(x_{k-1},\,x_{k})<\sum _{k=1}^{n}{\frac {1}{k}}\leq 1+\log n,$

for all n (the latter coming from the well-known integral bound). In particular,

$d(x_{0},\,x_{n})<1+p\log 2,$

for all $\textstyle p\in \mathbb {N}$ and $\textstyle 1\leq n\leq 2^{p}.$ Now, iterating (i) for (at most) $\textstyle 1+\lfloor p\log 2\rfloor$ times, and then (ii), you have

$d(x_{2^{p}},\,x_{2^{p}+n})=d\left(f^{2^{p}}(x_{0}),\,f^{2^{p}}(x_{n})\right)<{\frac {1}{2^{p}-p\log 2}},$

for all $\textstyle p\in \mathbb {N}$ and $\textstyle 1\leq n\leq 2^{p}.$ The latter is the p-th term in a convergent series, which proves that the orbit of $x_{0}$ is bounded (actually, it tells you directely that it is a Cauchy sequence). Notice that you don't need continuity of $\textstyle f$ to prove that its limit is a fixed point -just use (ii).--pma (talk) 01:05, 19 November 2009 (UTC)

Forgive me if I'm mistaken, but doesn't (ii) imply continuity? --COVIZAPIBETEFOKY (talk) 03:11, 19 November 2009 (UTC)

yes, you're completely right (for a moment the continuity seemed to me something that needed a proof!) --pma (talk) 07:30, 19 November 2009 (UTC)

And we also have a counter-example to that very statement! I hide it here below not to spoil the chase, should you like to find it by yourself. --pma (talk) 01:19, 19 November 2009 (UTC)

(Click the "show" button to see the counterexample, or the "hide" button to hide it.)

Hey! aren't you willing too much ??

Sorry, also have a counterexample to which statement? The existence of a fixed point you mean? Surely, it can't be both true and untrue at once (lest the walls come tumbling down) - or am i missing something and has your proof (which was brilliant, thankyou for the help) only proved the existence in certain cases? Sincere thanks, Mathmos6 (talk) 02:29, 19 November 2009 (UTC)

Pma wrote that, "Notice that you don't need continuity of $\textstyle f$ to prove that its limit is a fixed point -just use (ii)", and subsequently followed by a counterexample. However, the idea of the counterexample was only a joke (I was fooled into clicking the "show" button, I should add ;)); that is, no such counterexample exists. If you like, just look at the first two posts of pma and not the third to save confusion (but then, you will miss out on the joke ;)). --PST 02:44, 19 November 2009 (UTC)

Yes it was a joke ;-) Also, it seems it's still OK to bound with 1/(2^p-p log 2) instead of 1/(2^p-p log 2 -1) above (I've changed) --pma (talk) 07:30, 19 November 2009 (UTC)

Also, I guess that the result holds true more generally if you assume that f verifies, in place of (i) and (ii) : for some double-sequence ε : Z → R₊ such that ε(k) → 0 as k → +∞ and ε(k) → +∞ as k → -∞ :

(∗) d(x,y) < ε(k) ⇒ d( f(x), f(y) ) < ε(k+1),

for all x, y in X and k in Z (so e.g. the preceding (i) and (ii) may be summarized in (∗) with ε(k):=(|k|+1)^-sgn(k), for k in Z). Moreover, it should be true that there exists an equivalent metric that makes f a contraction. --pma (talk) 10:12, 19 November 2009 (UTC)

In fact, the nice way to state the hypotheses on f should be: f:X → X has a modulus of continuity ω such that ω(t)<t for all t>0. Then every orbit converges to a fixed point. You can find it as thm 17.4 in chapt. 5 of in K.Deimling's book Nonlinear Functional Analysis (with a proof completely different from the one I made for you). Deimling quotes it as a particular case of a theorem by F. Browder (Remarks on fixed point theorems of contractive type, Nonl.Anal. 1979) -one of the over 5000 metric fixed point theorems that have been produced as generalizations of the Banach contraction principle (which however remains the most important of all) --pma (talk) 04:47, 21 November 2009 (UTC)

divisibility

If 24 divides mn+1 how can I show that it divides m+n. Thanks-Shahab (talk) 14:31, 18 November 2009 (UTC)

Multiply your expression by m, and use the fact that m² ≅ 1 (mod 24) whenever m is coprime to 24 (you can do it directly I guess, or you can work separately mod 3 and mod 8 and combine the results). — Emil J. 15:05, 18 November 2009 (UTC)

Thanks for replying. I am sorry but I must trouble you again. I have two questions: What if (m,24) is not 1. How does the proof proceed in that case? Secondly how do you rigorously show that m² ≅ 1 (mod 24) whenever m is coprime to 24. I can see that it is true because the invertible elements in Z/24 have order two but that's not a good proof, right.-Shahab (talk) 16:53, 18 November 2009 (UTC)

That is a good enough proof. If you can show it for every single element, then it is true in general. Since there are only finitely many elements, it is not difficult. StatisticsMan (talk) 17:07, 18 November 2009 (UTC)

As for the first question, your assumption that 24 divides mn + 1 implies that m is coprime to 24, so there is no other case. — Emil J. 17:15, 18 November 2009 (UTC)

Oh yes.(to the first question) Thank you, I understand now. But my second question was not whether my method was valid, rather is there any better way to prove m² ≅ 1 (mod 24) whenever m is coprime to 24 then squaring 5,7,11,13,17,19,23 in Z/24.-Shahab (talk) 18:35, 18 November 2009 (UTC)

Well, you can make some optimizations. First, as I said, since 24 = 3 × 8 and 3 and 8 are coprime, it suffices to show the property mod 3 and mod 8, which cuts down the number of residues to check a little bit. Second, you can save some work by choosing representatives of the residues in a more clever way. A complete set of coprime residues mod 3 is {−1, 1}, and (±1)² = 1 (you could also appeal to Fermat little theorem, as 3 is prime); a complete set of coprime residues mod 8 is {−3, −1, 1, 3}, again (±1)² = 1, and (±3)² = 9 ≅ 1 (mod 8).

You can use some higher-level methods to get the same thing (such as the description of groups of units in the rings Z/nZ: the multiplicative group (Z/3Z)^× is isomorphic to C₃₋₁ as 3 is prime, and (Z/8Z)^× is C₂ × C_8/4 as 8 is a power of 2, hence (Z/24Z)^× is isomorphic to C₂ × C₂ × C₂ which is a group of exponent 2), but I find this machinery ridiculously complicated compared to the task that it solves. — Emil J. 19:06, 18 November 2009 (UTC)

sig figs: 13.3 * 6009.5 = 80100 ?

I can't figure out why my chemistry book gives this answer, I get 79926.35, which I want to round to 79900 to account for the 3 signifigant digits. What is going on here? Thanks, 99.129.149.93 (talk) 15:32, 18 November 2009 (UTC)

I don't know where the numbers come from but note that 80100/6009.5 = 13.32889... which can be rounded to 13.3. Is it possible 80100 originally came first and 13.3 was computed from that? Another note: 13.33*6009.5 = 80106.635 which can be rounded to 80100. Is it possible a 3 was lost in 13.33 at some point? PrimeHunter (talk) 17:27, 18 November 2009 (UTC)

Yes the 13.3 comes from 240/18.0 which indeed is 13.3333.... What is confusing is that my book clearly shows the 13.3, (not 13.333 or 240/18.0) being used in this calculation. Is one not allowed to round the answer to the correct number of sig figs at each step? -- 99.129.149.93 (talk) 19:28, 18 November 2009 (UTC)

It sounds like a little sloppy notation in the book if it prints a number rounded to 3 digits in a calculation but silently uses at least 4 digits when the calculation is actually performed. PrimeHunter (talk) 02:13, 19 November 2009 (UTC)

• Don't round before the last step unless you know how the rounding will affect the bottom-line answer.
• Don't round 400 to 400.02, etc. I see students do this all the time. Suppose you have 40/3, and that rounds to 13.33. Say you multiply that by 201/16, which is 12.5625, and you round that to 12.56. Then you multiply:

$13.33\times 12.56=167.4248.\,$

That bottom-line answer is nonsense! Here's a better way: first write

${\frac {40}{3}}\times {\frac {201}{16}}.$

Then notice that 201 = 3 × 67, so we have

${\frac {40}{3}}\times {\frac {3\times 67}{16}}.$

Then cancel the two 3s:

$40\times {\frac {67}{16}}$

Then notice that 40 factors as 8 × 5 and 16 factors as 8 × 2, and cancel the 8s:

$8\times 5\times {\frac {67}{8\times 2}}=5\times {\frac {67}{2}}=167.5.$

Notice that in this latter way there is no rounding. What the student did in the first method had the effect of taking the exact answer, 167.5, and rounded it to 167.4248.

Could anything be sillier?

When you put four digits after the decimal point, your claiming it's accurate to the nearest ten-thousandth. That is imbecilic nonsense.

I have to suspect something similar is going on in the example that is asked about here. Michael Hardy (talk) 04:51, 19 November 2009 (UTC)

In other words, don't do any rounding until you have the final answer. To round off earlier will multiply the round-off error dramatically. The book was trying to show that there are only 3 significant digits by listing 13.3, but I agree that this is confusing. I'd write it like this:

        (240/18.0)×6009.5 = 80100

The 240 does imply only two significant digits though, so perhaps the answer should be 80000 (or better yet, 8.0×10⁴). Alternatively, the 240 should be written as "240.", if they meant for there to be 3 significant digits. StuRat (talk) 14:19, 19 November 2009 (UTC)

If you want to use a notation that works, you don't use sigfigs. You specify the error bounds. "240" means exactly 240, "240(5)" or "240+/-5" is the correct way of writing "240 (2sf)". --Tango (talk) 23:58, 19 November 2009 (UTC)

I agree that "significant digits" are highly inaccurate, and I wish they'd stop teaching them. However, until they do, we should keep answering the questions about all the confusion they cause. StuRat (talk) 18:30, 20 November 2009 (UTC)