Wikipedia:Reference desk/Archives/Mathematics/2007 March 3

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 3

Test

Does 0.999... = 1 ? --hydnjo talk 01:47, 3 March 2007 (UTC)

0.999... says yes. If you want your mind to explode, take a look at the talk page and the arguments page there. x42bn6 Talk 01:51, 3 March 2007 (UTC)

BOOM! Cyraan 02:06, 3 March 2007 (UTC)

• Thanks y'all, just checking to see if anyone was paying attention and how quickly. FOUR MINUTES! - hot damn! --hydnjo talk 02:31, 3 March 2007 (UTC)

I've seen people respond faster before, though. x42bn6 Talk 02:38, 3 March 2007 (UTC)

For sure! Just checking because I haven't been around for a bit and wanted to be ... well ... sure. --hydnjo talk 03:12, 3 March 2007 (UTC)

Last I checked this forum is for genuine questions. I suggest you look up BJAODN or Google when bored.

Last I checked, you're supposed to sign your posts. Way to flout convention. (The previous post was composed by 76.175.159.246 at 17:38 on March 4, 2007. Act accordingly.) Black Carrot 19:48, 5 March 2007 (UTC)

Thick walled maze generation

Hi folks,

I'm assuming this question is best asked maths rather than computing, as it's essentially an algorithm I'm dealing with here, so my apologies if this isn't the right place.

I'm basically trying to write a maze generation routine. I've had a good look around the net and found plenty of great algorithms, but none that quite do what I'm trying for.

It seems the most common maze algorithm is the depth first search, described very nicely here: http://www.mazeworks.com/mazegen/mazetut/

The problem I have is that this treats each cell in the maze as a set of four walls which can be knocked down as needed, essentially giving you wide corridors and very thin walls (like this: http://www.mazeworks.com/mazegen/mazetut/tut1.gif). The kind of maze I am looking to generate is one where the walls and the corridors are the same thickness - as if you were drawing a maze on graph paper, and each square could either be an empty corridor space, or a solid block of wall (like this: http://www.cc.gt.atl.ga.us/projects/Learning_Research/Grid_World_Maze/LEARN2.JPG)

I have considered just doubling the distance I 'dig' each time between cells, but the problem then is that all dead ends are at least two spaces long, there are no single cell 'alcoves'

I'm sure there must be an obvious solution to this that I'm missing, but any help would be much appreciated

Thanks --Noodhoog 13:21, 3 March 2007 (UTC)

Rather than digging two squares at a time try using a different condition for if you can continue the path to a particular cell. Instead of find all neighbors of CurrentCell with all walls intact have find all neighbors of CurrentCell where the adjacent cells are still filled in.

-C-
X?X
XXX

In the above diagram C is current cell and ? is the cell your testing. If think you need all the cells marked X to be filled in to allow ? to be part of the path. --Salix alba (talk) 15:51, 3 March 2007 (UTC)

That works, and I've written a simple Perl program to implement it. It produces mazes that look something like this:

 XXXXXXXXXXXXXXXXXXXX
->  X   X XX XX     X
 XX X XXX  X X  X X X
 X  X X XX X   XX X X
 X XX X      X  XXX X
 X X  XXXXXXXXX X   X
 X X XX     X   X X X
 X   X  XXX XXXXX X X
 X X   XX         X ->
 XXXXXXXXXXXXXXXXXXXX

One problem with it is that there's no guarantee that the maze will reach any particular square or even come near it. In particular, if an area ever becomes surrounded by diagonal corridors, like this:

 XXXXXXXXXXX
 XXXX   XXXX
 XXX  X  XXX
 XX  XXX  XX
->  XX?XX  X
 XXXX???XX X
<-  XX?XX  X
 XX  XXX  XX
 XXX  X  XXX
 XXXX   XXXX
 XXXXXXXXXXX

then no new corridor can ever reach the squares marked with ?, even though they're adjacent to no corridor, since the diagonal corridors around them admit no branches. Such inaccessible areas can potentially be arbitrarily large, and may even occur in corners, as with this artificially created maze:

 XXXXXXXXXXXXXXXXXXXX
->  XX  X X         X
 XX  XX     XX XXXX X
 XXX  XX XXXX  X XX X
 XXXX  XXX    XX X  X
 XXXXX  XXX XXXX X XX
 XXXXXX  XX X  X    X
 XXXXXXX  X X XX XXXX
 XXXXXXXX   X       ->
 XXXXXXXXXXXXXXXXXXXX

However, I believe what can be guaranteed is that the maze will touch all sides of the rectangle in at least one point, so at least it should always be possible to place an entrance and an exit. —Ilmari Karonen (talk) 18:43, 4 March 2007 (UTC)

There is a simple correspondence between the thin-walled mazes and the thick-walled ones. Think of the thin walls as built up from edges of a graph, each of which is between vertices labelled by a pair of integer coordinates. Such an edge is either between (i,j) and (i,j+1) or between (i,j) and (i+1,j) for some pair of integers i and j. A thick wall, on the contrary, is built from "filled" square cells, which are again labelled by pairs of integers in an orthogonal coordinate system. A single thin edge between (i,j) and (i,j+1) now corresponds to THREE consecutive filled cells: (2i,2j), (2i,2j+1), (2i,2j+2). Likewise, an edge between (i,j) and (i+1,j) is mapped to the three filled cells (2i,2j), (2i+1,2j), (2i+2,2j). Connected edges share a filled cell. One way of thinking about this is that a cell (2i,2j) with only even coordinates correspond to node (i,j) in the thin-walled graph, and when these nodes are connected by an edge the corresponding cells as well as the in-between cell get filled.  --Lambiam^Talk 18:15, 3 March 2007 (UTC)

Fair enough, except that this restricts you to the two-cell dead ends Noodhoog was trying to avoid. With your scheme, you can't produce a thick-walled maze like, say:

### ###
# #   #
# ## ###
# #  # #
# #### #

(where the # marks are corridors). —Ilmari Karonen (talk) 19:15, 3 March 2007 (UTC)

How about if you just add another pass at the end, and change half of the two-cell dead ends to one cell dead-ends, by filling in one cell ? StuRat 20:14, 3 March 2007 (UTC)

If you look at the block maze link above, you'll note that the nodes are on even and odd squares, the simple alogirith described by the OP I think will always have intersections on even squares (as lambian describes), and filling in an extra cell on dead ends wont change this property. Avoiding this was my rational for the algorith I propose above. --Salix alba (talk) 22:03, 4 March 2007 (UTC)

Modular arithmetic

Our teacher gave us the method to easily find out the value of the number b in $a^{\mbox{big number}}\equiv b\,[{\mbox{mod}}\,m]\,{\mbox{with}}\,0\leq b<m$, that involves finding n such that $a^{n}\equiv 1\,[{\mbox{mod}}\,m]$. He said this method was nearly always possible but didn't explain.

Obviously, this is only possible if a and m are coprime, otherwise $a^{n}\not \equiv 1\,[{\mbox{mod}}\,m]\quad \forall n\in \mathbb {N} ^{\star }$. It seems to be possible in every other case but I can't manage to give a proof. I tried to list all cases (a = km, a = km+2, a=km+3, ...) and tried giving an explicit expression of n using a logarithm but I fell back on the original problem on each tentative.

Finally, the question is, what is the proof that for all coprime a and m, it is possible to find a positive integer n such that $a^{n}\equiv 1\,[{\mbox{mod}}\,m]$ ? Is there a way to directly calculate (the smallest, nonzero) n if a and m are given ?

--Xedi 22:03, 3 March 2007 (UTC)

See Euler's theorem Algebraist 22:16, 3 March 2007 (UTC)

Which tells us that for given a,m with (a,m)=1, the smallest n (aka the order of a in the group of units of Z/mZ) is a factor of φ(m). Can't immediately think of a way of determining which factor that's any better than just calculating powers of a mod m and seeing what happens. Hopefully φ(m) is good enough for you? Algebraist 22:21, 3 March 2007 (UTC) (corrected Algebraist 22:25, 3 March 2007 (UTC))

I am too stupid to click on links, apparently. The above can be improved by observing that the order of a divides the Carmichael function λ(m) which can be computed without too much difficulty. Algebraist 22:25, 3 March 2007 (UTC)

Thank you very much, exactly what I needed ! --Xedi 22:35, 3 March 2007 (UTC)

The proof that for all coprime a and m, there must be some positive integer n such that aⁿ = 1 mod m is quite straightforward. aⁿ can only take finitely many different values mod m, so there must be some distinct p and q for which a^p = a^q mod m . Suppose p > q; calculate a^p-q mod m, remembering to use the fact that a and m are coprime. This is a classic existence proof - it tells us that n exists, but does not help us find its value. Fermat's little theorem, Euler's theorem etc. extend this basic result by restricting the range of possible values for the smallest such n. Gandalf61 12:31, 4 March 2007 (UTC)

Quite true, I never really think about non constructive proofs as I always tend to start a proof by trying to find an explicit relation constructing what is needed. Thank you ! --Xedi 21:20, 4 March 2007 (UTC)

Try using TeX built-in *mod commands:

TeX	result
a^n \equiv 1 \, [\mbox{mod}\, m]	$a^{n}\equiv 1\,[{\mbox{mod}}\,m]$
a^n \equiv 1 \mod m	$a^{n}\equiv 1\mod m$
a^n \equiv 1 \pmod m	$a^{n}\equiv 1{\pmod {m}}$
a^n \equiv 1 \bmod m	$a^{n}\equiv 1{\bmod {m}}$

--CiaPan 13:49, 5 March 2007 (UTC)