Wikipedia:Reference desk/Archives/Mathematics/2008 October 31

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.

October 31

Mazes

In maze it says "Another type of maze consists of a set of rooms linked by doors (so a passageway is just another room in this definition).". I could ask this on the discussion page for that articel, but my experience of discussion pages is that they, mostly, don't get replies. So..., Is the quote right? SIs it more accurate to say that the rooms are the junctions (nodes) and the doors are the passageways. -- SGBailey (talk) 16:04, 31 October 2008 (UTC)

Yes, that's a very common type of maze in adventure games especially the older ones, and seeing them that way is fine. In fact a whole adventure game besides the puzzles is often to all intents and purposes a maze. Dmcq (talk) 17:47, 31 October 2008 (UTC)

I know rooms can make a maze. What I was asking is whether the statement that the rooms were the passageways is correct. I think the rooms are the nodes and the doorways are the passageways. Your opinion...? -- SGBailey (talk) 00:03, 1 November 2008 (UTC)

Isn't the point of this model that any two-dimensional area is considered a "room", regardless of its shape, i.e., regardless of whether one would normally call it a "passageway" or a "corridor" rather than a "room"? The doorways is an entirely different matter of course. -- Jao (talk) 00:39, 1 November 2008 (UTC)

If a passageway can only link two nodes and nodes must be connected by passageways then it isn't right because two rooms might be connected directly which have more than two doors each. Of course if a passageway may connect more than two nodes then yes it would be okay. Dmcq (talk) 00:43, 1 November 2008 (UTC)

My visualisation of this is that in a standard maze, I get to a junction, lokk around and decide to take path X - I go down path X to the next junction and now choose path Y. Mapping that to rooms, I'm in a room and decide to take door X. I go through door X to another room and decide to take door Y. Which to me means that rooms are junctions and doors are passageways. But there hasn't been a clearcut response agreeing with this, so I'll leave the original article alone. Cheers. -- SGBailey (talk) 09:29, 1 November 2008 (UTC)

I think you could remove it on the basis that it isn't a notable point of view and is confusing when combined with graph theory. When people draw a graph of an adventure game they do it with lines for the doors. Dmcq (talk)

My Theory that a fraction is a sum

In my math class almost a year ago I found out a pattern in the outcome of ${\frac {1}{14}}$: It's the sum of

• 7*2⁰*10^(-2)
• 7*2¹*10^(-4)
• 7*2²*10^(-6)
• ...

Or more general the sum of ${\frac {1}{14}}=\sum _{n=0}^{\infty }7*2^{n}*10^{-n}$

it seem to be correct but I'm unable to proof that this thesis is correct.

Is this provable? Excel20 (talk) 16:53, 31 October 2008 (UTC)

You mean ${\frac {1}{14}}=\sum _{n=0}^{\infty }7*2^{n}*10^{-2-2n}$. This is both true and provable; see geometric series. Algebraist 16:55, 31 October 2008 (UTC)

group as a fundamental group

Is every group isomorphic to a fundamental group of some topological space? 212.87.13.70 (talk) 18:25, 31 October 2008 (UTC)

Apparently, yes. See Fundamental group#Realizability. --Tango (talk) 18:53, 31 October 2008 (UTC)

To expand on what's there: you do it by taking a presentation of your group, and taking a wedge sum of circles, one for each generator of your group. Then for each relator in your presentation, you glue on a 2-cell so that its boundary is the circles corresponding to the appropriate word in the generators. Algebraist 08:20, 1 November 2008 (UTC)

Sometimes you continue on Algebraists construction by gluing on cells of even higher dimensions. This will not change the fundamental group but will make the higher homotopy groups trivial. Doing this will give you a K(G,1) -- an Eilenberg-MacLane space. For example for the cyclic group of order two Algebraists construction will give you the real projective plane $\mathbb {R} P^{2}$ while continuing gluing on cells of higher dimensions will give you the infinite-dimensional projective space $\mathbb {R} P^{\infty }$. Aenar (talk) 01:18, 2 November 2008 (UTC)

Functions with finite number of local extrema

Let S be the set of positive-real-valued functions on R with continuous second derivatives. We say f ~ g if f/g has a finite number of strict local minima.

1. For f in S, is having a finite number of strict local minima equivalent to having a finite number of strict local maxima and equivalent to having a finite number of strict local extrema?

2. For f in S, does $\ln \ f$ have a finite number of local minima if and only if $f$ does?

3. For f, g in S, if f and g have a finite number of local minima then does fg necessarily have a finite number of local minima?

4. Is ~ an equivalence relation?

5. Is the equivalence class containing $e^{x}$ interesting?

The answers I got in the shower are yes, yes, yes, yes, and maybe not. The proofs were direct and short but messy. I used 2 to prove 3, and I used 3 to prove transitivity for 4. I need strict local minima, rather than non-strict local minima, so that ~ will be reflexive. I would appreciate if other people verified 1, 2, 3, and 4 as well, but assuming I didn't make any big errors, then my main interest is in problem 5.

Regarding 5, the equivalence class containing $e^{x}$ is the set of all functions f where f(x) = f'(x) finitely many times (or rather, that if T is the set of points where f(x) = f'(x), then the number of isolated points of T is finite, or something like that). This includes all functions with a finite number of strict local minima.

My purpose in creating the equivalence relation ~ is to try to create an analog of big-Oh notation to analyze the asymptotic behavior of functions... whereas big-Oh looks at asymptotic growth, this equivalence relation looks at asymptotic "smoothness" (smoothness as in the English word, not the math term). But I feel that ~ is probably too coarse of an equivalence relation to be of any use.

Thoughts anyone? Eric. 131.215.158.166 (talk) 19:49, 31 October 2008 (UTC)

Where does the bit about f(x)=f'(x) finitely many times come from? e^x itself doesn't satisfy that condition... (this may be why you mention isolated points, but that's not a trivial addition.) --Tango (talk) 21:17, 31 October 2008 (UTC)

I don't think that is an equivalence relation at all. Take these three functions:

f(x) = 0.05 * x^2 + 2

g(x) = 0.05 * x^2 + 2 + cos(x)

h(x) = 1

f~h, because f/h is just f and f has exactly one local minimum

g~h, g has four minima near zero, for large numbers x^2 dominates the oscillation of cos(x)

however f is not related to g, f/g oscillates around 1 an infinite number of times —Preceding unsigned comment added by 84.187.94.213 (talk) 07:05, 1 November 2008 (UTC)

Well spotted, 84, thanks for checking my work. I worked out my proof for number 3 and found the error; I had apparently assumed that if f and g have a finite number of local minima, then so does f + g. (I had used number 2 to transform the problem of multiplication into a problem of addition.) I went ahead and also found that number 1 is wrong (an infinite number of strict local minima imply an infinite number of local maxima, but they might not be strict), and I don't see an easy way to salvage it, either. So ~ is neither symmetric nor transitive. (But it is still reflexive!)

As for Tango's remark, the proof of that depended on 3 so the result may be false. The reason that isolated points get into it is as follows: if f'(x) = 0, then f(x) is a local extremum, but not necessarily strict; if x is an isolated zero of f' , then f(x) is a strict local extremum (not always, but it should be obvious by now that I don't check my work before posting to the reference desk). I need strict local extremum so that ~ is reflexive (since f / f = 1, which has no strict extrema but plenty of non-strict extrema). Eric. 131.215.159.8 (talk) 10:16, 1 November 2008 (UTC)