Wikipedia:Reference desk/Archives/Mathematics/2021 October 22

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded 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 22

The Discovering of true randomnes?

Randomwalk once with the number pi and once with the genome.
My question is: Is there a comparison to test different processes for its randomness, for example the signals of pulars or the like? — Preceding unsigned comment added by 2A02:908:426:D280:D82B:8A4C:3F13:8022 (talk) 15:45, 22 October 2021 (UTC)

Guessing a little at what you mean, you probably can't do it with certainty (or near-certainty) in any uniform way. There are lots of randomness tests that will pass for a truly random sequence, and usually eventually fail for a nonrandom sequence not purpose-designed to evade them. However, there are (probably) such things as cryptographically-secure pseudorandom number generators, and these, by definition, are indistinguishable from random sequences to anyone who does not have the "secret".

There are a great many different paths you can get onto from this question. There's a whole area of study of algorithmic randomness, which overlaps with effective descriptive set theory. My guess is that's not what you want to know right now, but you might someday. --Trovatore (talk) 16:36, 22 October 2021 (UTC)

There's no perfect way to test against every form of non-randomness or correlation, even for signals from distant galaxies, which is why ideas like superdeterminism are so hard to rule out. --Amble (talk) 19:19, 22 October 2021 (UTC)

3 utilities puzzle

Am I correct to state that this [[1]] does not become solvable if I place it on a different type of surface, such as a sphere or the Real_projective_plane?

Duomillia (talk) 18:55, 22 October 2021 (UTC)

We have an article on the problem (of course), but it doesn't say anything about the projective plane. It does say that the problem is solvable on the torus. It turns out that you can solve the problem on the projective plane, in fact you can connect all six nodes of the graph to each other without crossing. The sphere is essentially the same as a plane with respect to graph theory; the plane is topologically equivalent to a sphere with a single point removed. --RDBury (talk) 19:09, 22 October 2021 (UTC)

If the cottages are not modelled as points but as planar regions, the problem is solvable if a connection between some utility provider and some cottage may run through another cottage.^[2]  --Lambiam 22:08, 22 October 2021 (UTC)

PS. I finally got around to watching the video. (It features all my favorite mathie youtubers except Vihart.) Anyway, Mathologer's solution is the one where you draw though one of the buildings. The Euler characteristic of the projective plane is 1 and that of the torus is 0. The proof in the video shows that the puzzle is impossible for characteristic 2 surfaces, and so it fails for the projective plane and the torus.

Btw, it's not too hard to modify the proof in the video to show that the Euler characteristic of a surface where the puzzle with m houses and n utilities is at most $2-{\biggl \lceil }{\frac {(m-2)(n-2)}{2}}{\biggr \rceil }$. Apparently it's well known that this is the minimum characteristic needed, in other words the graph can always be embedded in a surface of that characteristic or less, though I'm guessing that's harder to prove. --RDBury (talk) 01:45, 23 October 2021 (UTC)

Solution on a real projective plane

@Duomillia:@RDBury: I modded my diagram for the real projective plane. It seems soluble, though I can't find a reputable source that explicitly says so. Are page 7 (original page 488) of http://www.sfu.ca/~mohar/Reprints/1993/BM93_JA15_Mohar_ProjectivePlanarity.pdf or page 3 of https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.1102&rep=rep1&type=pdf good enough? Thanks, cmɢʟee⎆τaʟκ 01:30, 24 October 2021 (UTC)

(pinging @David Eppstein: in case he has something to add)

All Möbius ladders including $K_{3,3}$ can be embedded in the projective plane. Just draw them as an even regular polygon with its long diagonals and put a cross-cap in the middle. For a reference, it's probably somewhere in MR2124859 but that link's just a bibliographic database entry; the paper itself is offline. I don't know whether it has been specifically connected to the three utilities puzzle in any publications, or whether the embedding of $K_{3,3}$ has any important properties that are different from other Möbius ladders, though. —David Eppstein (talk) 01:49, 24 October 2021 (UTC)

I found a reference that specifically discusses the three utilities puzzle on a Möbius strip (more or less the same as a projective plane for the purposes of the puzzle, in the same way that the plane is more or less the same as a sphere). Note that the strip has to be transparent for this to work: if it's made of opaque paper, and you can draw different things on each side of the paper, then really what you have is a double-covering of the strip by an annulus, on which the puzzle has no solution. Anyway, for the reference (which I added to the article on the puzzle), see Figure 7, p. 292 of: Larsen, Mogens Esrom (1994), "Misunderstanding my mazy mazes may make me miserable", in Guy, Richard K.; Woodrow, Robert E. (eds.), Proceedings of the Eugène Strens Memorial Conference on Recreational Mathematics and its History held at the University of Calgary, Calgary, Alberta, August 1986, MAA Spectrum, Washington, DC: Mathematical Association of America, pp. 289–293, ISBN 0-88385-516-X, MR 1303141. —David Eppstein (talk) 00:20, 25 October 2021 (UTC)

According this paper the genus (which would imply the characteristic) of complete bipartite graphs were determined by G. Ringel, To visualize K₆ in the projective plane, embed the graph of the icosohedron on a sphere and then identify antipodal points; this avoids crosscuts. You can similarly embed K_3,4 in the projective plane using the graph of the Tetrakis hexahedron embedded in the sphere. It's an interesting puzzle to find embeddings of K_3,6 and K_4,4 in the torus. One can do this using periodic tilings to avoid dealing with handles and bridges. The "next" characteristic is -1 and theoretically there should be embeddings of K_3,8 and K_4,5 in a surface with three crosscuts, but that's where I stopped. --RDBury (talk) 16:07, 25 October 2021 (UTC)

Correction, the Tetrakis hexahedron is (obviously) wrong; I should have said the Rhombic dodecahedron. --RDBury (talk) 16:36, 25 October 2021 (UTC)