jack

Question 1

You have a graph on an even number P people where each node has E=3 edges connected to it. You colour in one edge. Then you colour in another edge such that each person has at most one coloured edge, aka not touching a previous coloured edge (without planning ahead). You keep doing this as long as you can.

I think for some graphs (e.g. 4 people, or 6 people each connected to the adjacent people and the opposite person) you are guaranteed to be able to colour P/2 edges so that each person touches exactly one coloured edge, whatever your early choices were. Whereas for other graphs (e.g. the corners of a triangular prism?) you can end up in a "dead end" where you've coloured two edges and then the two people left over with no coloured edge have no edge between them to colour.

Is there a description of which graphs guarantee and which don't? What about if E=2 (probably usually not guaranteed?). Or E=4?

Question 2

You have a graph with even P nodes each with E=3 edges. There are A=3 acts. In the first, you colour P/2 non-touching edges. In the second you colour P/2 non-touching edges, not colouring edges that were coloured in act 1 (without planning ahead to act 3). In the third act, you also try to colour P/2 non-touching edges that weren't coloured in acts 1 or 2. Are there graphs where if you colour the edges one at a time you're guaranteed to fill in all the edges without discovering you need to backtrack?

What about for different values of E and A? If E is greater than A? If E is ALL the possible edges then it's always possible, but for values less than that?

Question 3

You have a graph with even P nodes each with E=3 edges. There are A=3 acts. In the first, you colour P/2 non-touching edges with +1, 0 or -1. In the second you colour P/2 non-touching edges, not colouring edges that were coloured in act 1, with +1, 0 or -1 (without planning ahead to act 3). In the third act, you also try to colour P/2 non-touching edges that weren't coloured in acts 1 or 2, also with +1, 0 or -1, but try to ensure that three values each node touches sum to 0. Are there graphs that guarantee that's possible in act 3, regardless of what you did in acts 1 and 2?

What if you had E=4 and coloured +1 or -1?

Three men go to stay in a motel in a single room (their personal relationship is irrelevant to the problem). They are charged £300 and split it £100 each. Then the manager realises that they were massively overcharged, and the actual cost should only have been £25 total. The manager gives £275 to bellboy (so, not as much of a dive as I was imagining?).

But the bellboy, noticing 275 doesn't divide evenly into three, pockets £272, returning £1 to each of the men.

Now each man has paid £99 to stay in the room and 3 x £99 = £297. The bellboy has pocketed £272. £297 + £272 = £569 - so where is the missing £269?

When you put it like that, the maths is clearly screwed up. But when the original cost is £30, apparently it's easy to add the stolen money again instead of subtracting it.

Crossposts: https://cartesiandaemon.livejournal.com/1056436.html

http://cartesiandaemon.livejournal.com/1030046.html

OK, I'm going to assume everyone who wanted to think about the original problem unspoiled has probably done so, and assume comments have rot26 spoilers from here on.

( Read more... )

Crossposts: http://cartesiandaemon.livejournal.com/1030153.html

For a plot bunny (yes, really :)):

You have a multivalued function from a sphere onto "some surface", continuous everywhere except two points. (Or, equivalently, a function from "some surface" to the sphere, I guess?)

If you look at points on the surface which map onto the same point on the sphere, and connections between them of "paths" on the sphere (up to continuous deformation), I feel like they end up acting like the integers, where "+1" and "-1" correspond to a clockwise of anticlockwise circumnavigation. Or possibly some subset, a cyclic group of some finite order, if there are repeats. Is that right?

If you have *three* points, what can the relationship between the points look like? What about more?

I remember doing something like that but not what it's called.

I'm trying to put something like the shadows of amber onto a more concrete mathematical footing :)

Crossposts: http://cartesiandaemon.livejournal.com/1005836.html

Do all numbers have a multiple which you can write (in base 10) solely with 0s and 1s?

Spoiler in the comments. And probably maths.

Crossposts: http://cartesiandaemon.livejournal.com/1005152.html

As best as I can tell, the pokemon go scanner reports whether a pokemon is within 200m or not. It updates about every 15s (?) When a pokemon is within about 50m (?) it appears.

My current strategy is, when I see a pokemon appear, continue in the same direction, assuming it's more likely I've walked into its radius than that it just spawned, and that it's more likely I've entered its radius closer to head on that obliquely. Mathmos, does that sound true?

If I walk about 200m and it isn't there, I try to curve round sideways. If it disappears again, I backtrack, and knowing two points approx 200m away from it, head for one of the points of those triangles.

But I'm wondering, would it be better that when I see it appear, I immediately turn sideways in the hope of finding two nearby points on the edge of its radius, and then extrapolate a point perpendicular to a line between them? That's harder, because it means I deliberately walk away from it. But maybe it would be quicker to narrow down where it is?

If there weren't a noisy gps and periodic updates, and those numbers were all precise, what would be the best strategy? It reminds me a little of Dr Leader's "you are trapped in a gladiatorial arena with someone who runs at exactly the same speed as you" puzzles, but hopefully simpler :)

Crossposts: http://cartesiandaemon.livejournal.com/998114.html

A friend on facebook linked to a variant of the 100 hats puzzle I talked about at: http://cartesiandaemon.livejournal.com/232415.html?nc=21

Suppose there are 100 scientists (or logicians, or philosophers...) and 101 hats. As in the other puzzle, the scientists are told the rules, allowed to confer, and then not allowed to speak. They're lined up all facing the same way, so the one at the back can see everyone else's hats, and the one at the front can see no-one's hats. And no-one can see their own hat.

The hats are numbered "1" to "101". The hats are placed randomly on the heads of the scientists, with one unknown hat left over. In any order the scientists can guess what hat they're wearing. But can't guess a number that was previously guessed.

What's the maximum number of scientists you can get to guess right?

If you have that, can you do it if there are 102 hats and two are left over? I genuinely don't know the answer to that one.

Hints in the comments.

Crossposts: http://cartesiandaemon.livejournal.com/939976.html

I think I realised why I don't naturally get on with statistics as much as you'd expect.

I think it's because in statistics it's more likely that you'll do a bunch of calculation, and at the end, it's not obvious to everyone that you got it right. I'm not sufficiently confident that I've done all the hard stuff right, I still like the external validation of it being obvious.

Crossposts: http://cartesiandaemon.livejournal.com/881703.html

Simont: Is there a set of players each of whom plays a single win-or-lose game against each other player, where every pair of players has a third player who beat both?
Jack: *thinks*
Jack: Yes.
Simont: Not that one.

Crossposts: http://cartesiandaemon.livejournal.com/862748.html

Poll #14435 Aleph-1 green bottles

Open to: Registered Users, detailed results viewable to: All, participants: 12

View Respondents

How long is the song 'aleph-1 green bottles, hanging on the wall'

View Answers

omega-0, songs are inherently sequential
1 (8.3%)

omega-1, one verse per bottle
3 (25.0%)

omega-3, because... fish?
1 (8.3%)

Something else
4 (33.3%)

What?
3 (25.0%)

Crossposts: http://cartesiandaemon.livejournal.com/861706.html

Tonight is the monthly mathsjam, recreational maths pubmeet (at the castle from 7 onwards)

Does anyone remember any good puzzles we've previously talked about I should take along, preferably that you don't absolutely need a maths degree to understand the problem? (Most people will, in fact, have maths degrees, but puzzles unrelated to set theory are more traditional :))

Crossposts: http://cartesiandaemon.livejournal.com/835428.html

An ArXiv-only journal

The process for publishing an acadmic paper goes something like:

1. Do lots of hard thinking no-one in the history of the world has ever done before
2. Write it up neatly
3. Submit it to a journal, which will have someone check it's (a) new and (b) interesting
4. Wait a long, long time
5. Profit.

OK, I was lying about step 5. The point is, mathematicians, possibly even more nerdy than most academics, having got through step 1 and some of step 2, sort of get fed up at the point where they have to talk to someone and don't want to bother with it any more.

A sort-of short-circuit in the process is arXiv, an online repository where, when your paper is going to be published, you can post a preliminary copy, so people can see roughly what's going to be in it without having to wait for the journal to be actually printed.

At this point, a cynic might start asking, do we actually have to do steps 3-4?

In fact, one of the recent big breakthroughs in mathematics, Grigori Perelman's outline proof of the Poincare conjecture, one of the Millennium problems, for which he was awarded (and rejected) a Fields Medal, was published entirely on arXiv. There's some controversy whether the "proof" owes to Perelman's outline, to the people who published a complete proof, or some combination, but everyone accepts that Perelman's contribution was very important.

However, Perelman's proof was clearly an important and serious effort. For other papers, there's still a value in peer-reviewing, editing, sorting, collating, etc.

http://gowers.wordpress.com/2013/01/16/why-ive-also-joined-the-good-guys/

Gowers is also involved with a completely free journal which has done what many people wonder about, doing the bit of collating unpublished papers into a "journal", but leaving off all the other bits, so you just get a list of "these papers on arXiv are true and useful," but they're just as available to read as anything else on arXiv.

It remains to be seen how successful this will be. We'll probably end up with some compromise with different sorts of journal for different purposes, but hopefully a further improvement over the current system. But its good to see a fairly high-profile attempt.

I think PLOS in biology is something similar, but I don't know how similar?

Crossposts: http://cartesiandaemon.livejournal.com/820376.html

http://gowers.wordpress.com/2013/01/14/why-ive-joined-the-bad-guys/
http://gowers.wordpress.com/2013/01/16/why-ive-also-joined-the-good-guys/

Prof Tim Gowers recently posted about two new open-access maths journals he's involved with.

History

There was recently an ongoing fuss about academic journals. The general sentiment seemed to be, that academics did a lot of the significant work in preparing journals, in refereeing papers for technical accuracy, sitting on editorial boards, etc, and the remainder, of copyediting, formatting, physically printing and distributing, while valuable, wasn't worth as much as it had come to cost.

Fingers were pointed especially at Elsevier, who many people claim to represent the end of the publishing industry who have bought the most small journals, and squeezed the most money for them with the least commitment to actually supporting the acadmic community. Especially by charging inflated prices for necessary journals, spuriously justified by bundling them with a lot of other less-necessary journals. And by forbidding academic libraries from discussing what they have to pay to subscribe to the journals, which isn't inherently bad, but is generally a pretty clear indication that you're doing something dodgy.

In fact, comparisons to smallpox were thrown around. Even if Elsevier's capitalism wasn't evil, it was stupid, in that if you kill of the host, your parasitic infection is inherently doomed. I don't know if this was justified (but I assume that Tim Gowers was right).

Journals are not funded by people who buy individual issues. They're funded by university libraries who subscribe. And universities all do have to subscribe, since you can't do much research without reading other people's research. So lots of people said, "since almost everyone pays for them and almost everyone can read them, why can't we cut out the middle men, fund the journals directly without the fiction of subscribing, and just throw them open to everyone?"

The trouble is, what do the existing journals have? They have a reputation. Academics all know that if you're published in Nature, that's good. Going begging asking for money to set up a new journal less famous than nature doesn't get very far, if everyone ALSO still has to pay subscription fees to the existing journals.

The only way to break the deadlock is to make a sufficiently high-profile break with the previous system that at least one new journal instantly acquires enough reputation to be unignorable. Which is why people have been making a fuss about it.

I only know about maths, because I read Tim Gowers' blog. Maths is a bit of a weird edge case because mathematicians have to pay pretty much only for journals: otherwise, you just need an office, a pen, a wastepaper basket, and some grad students, and those generally turn up in universities.

Forum of Mathematics

There is a new author-pays open-access family of mathematics journals set up by Cambridge University Press. The idea is, instead of being charged to read a journal, you're charged to publish in a journal (since both are equally necessary to an academic career). And anyone at all can just read it.

And that institutions will set aside a pot of money to pay for the publication, just as they previously set aside a pot of money for journal subscriptions. I think some other subjects already work like this?

The controversy is, Tim Gowers says the journal will continue to accept anyone's submissions if they're good enough, and won't be rejected if the applicant can't pay. And that any sufficiently prestigious university will just automatically pay the fees.

Which sounds reasonable to me -- presumably most publications come from big universities, which will automatically do the done thing.

However, detractors assume any author-pays model will be like more vanity publishing, and automatically deter authors who can't pay and don't work for a big university, or people from smaller or less rich institutions.

The comments section

Prof Gowers' post, and the detracting blog post he linked to are obviously sensible. I sort of assume Gowers is right, but I don't actually know.

But the comments section is so depressing. People going out of their way to comment on a the blog of a high-profile research mathematician are better formatted, but just as puerile, as those of many other blogs. Everyone talks past each other, saying, author-pays WILL AUTOMATICALLY be vanity publishing, or author-pays will just be business as usual for large institutions, and assume the other is being wilfully evil by deliberately ignoring the obvious truth, while never actually proposing any evidence for what it will actually be like.

Next time

Next time: the ArXiv-only journal.

Crossposts: http://cartesiandaemon.livejournal.com/820101.html

Many people have observed that, given the volume of a sphere radius r is V(r)=(4/3).pi.r³ and its surface area is S(r)=4.pi.r², that, very conveniently:

dV(r)/dr = 3.(4/3).pi.r² = 4.pi.r² = S(r)

In fact, I use it to remember the surface area, since I only usually remember the volume. It seems to make sense sort of, but many people are not quite sure why.

Today someone pointed out, that the same thing works for a cube, if you take the side length as the diameter and half the side length as the radius.

V = (2r)³
S = 6.(2r)²
dV/dr = 2.3.(2r)² = 6.(2r)² = S

In fact, if you do the trigonometry, it turns out the same thing works for the tetrahedron and other platonic solids, although if you take the side length as d, r is no longer half d.

In fact, if you take d = ar for some unknown constant a, so long as the volume is something times r cubed, and the surface area is something times r squared, there's always some value of a that makes the derivative dV/dr = S exact.

It may or may not be immediately obvious what that value is, but in fact, it's the distance from the centre to the middle of one of the faces aka the radius of the largest sphere which fits inside.

At this point we were puzzled why, and it wasn't until I was at home that I saw the obvious way of thinking about it.

What does dV/dr mean? It means [V(r+δr)-V(r)]/δr (as δr->0).

That is, "imagine a solid with a slightly larger r, and subtract the original r" and ask what's left. What's left is thin slab covering each face, plus some neglible rods at each edge which have an extra factor of δr in so effectively vanish to zero. What's the volume of all those thin slabs? The areas of the faces, times the width of the slab. What's the width? The distance from one side to the other perpendicular to the face, ie. parallel with a line through the centre only at the centre of the face, ie. it is δr, so the volume of the slab is S.δr, and [V(r+δr)-V(r)]/δr is approximately S.

The same diagram apparently works for a sphere, if you imagine δV to be a thin shell covering the original sphere. What's the volume of the shell? Well, it's approximately "surface area times width", but the inner or outer surface area? Well, one's too small and one's too big, so the goldilocks answer is somewhere between S(r).δr <= δV <= S(r+δr).δr. But all the extra terms in the second one all have δr^2 in so they all vanish, and δV ~ S(r).δr.

I think I've probably seen that before but forgotten.

Crossposts: http://cartesiandaemon.livejournal.com/798176.html

If you're playing twenty questions (say on something simple like "numbers from 1 to a 1000") the best strategy is to divide the output into two with each guess[1]. Eg. Higher than 500? Yes. Higher than 750? No. Higher than 625? Yes. Etc. Etc. This will take log(N) questions to find the exact answer. (Guessing randomly may produce the answer quicker, but on average will take mcuh longer.)

However, suppose when you ask a question, you're given the answer, but it's right only 90% of the time. (For simplicity, assume you can find out if you've got the right single answer at the end.) What's the right strategy? Is it to ask "Higher than 500" twice or more until you're sure? Or to follow the normal strategy until it gives a unique answer, and if that's wrong, start again?

The second game feels like what I often end up feeling like in real life... :)

[1] I remember reading a book that said learning to "gain information" from a guess rather than "make a right guess" was quite difficult for children to learn -- a teacher reported many children guess "higher than X" when they already knew it true, because they'd been so conditioned by class to expect a "yes, that's right" to be a good thing and "no, that's wrong" to be a bad thing.

Crossposts: http://cartesiandaemon.livejournal.com/720847.html

( Project )

( Project )

Crossposts: http://cartesiandaemon.livejournal.com/716104.html

The university has decided that a maths fourth year is now officially equivalent to a taught masters, and allowed people who graduated from it to graduate retrospectively with an MMath, even though it generally regards any degree other than a Bachelor of Arts[1] to be a bizarre newfangled fad :)

The first available date is Sat 30th Apr (the Saturday of the royal wedding weekend), and the maths building and Trinity have both decided to put on a lunch or some talks.

And after some procrastination, I'm going to apply to go, as are a couple of other friends (as atreic suggested ages ago). If anyone else did part three and wants the letters after their name to have "maths" in, you may not be quite too late to apply (although Trinity says, by the 12th at the latest, and I assume I was too late already by the time I got round to it).

Links:

http://www.trin.cam.ac.uk/index.php?pageid=1051
http://www.maths.cam.ac.uk/postgrad/mathiii/retrospective/

There is an old puzzle which goes "Two cyclists start out 50 miles apart, and head towards each other, each one going 10 mph. At the same instant, a fly leaves the first bike and flies at 30 mph towards the second. When it gets there, it immediately turns around and heads back to the first. Then it repeats, going back and forth between the two bikers. By the time they reach each other, how far will the fly have travelled?"

( Spoilers, )

http://www.scottaaronson.com/democritus/lec19.html
ETA: http://scottaaronson.com/blog/?p=368

What I thought

If I live in world A and go back in time and alter things, then I leave a new world A'. What if the new me in world A' ALSO goes back in time to alter things, leaving world A''? If me' changes them back again, you have some kind of grandfather paradox.

I had always had an idea that the obvious resolution is that it will "settle down" to some steady state A'''''''''''''''' which leads to the same A''''''''''''''''. I envisaged this as moving through the possible states until you find a stable world to stop in even though "moving through" would not be relative to the normal timeline.

A proper formulation

However, I was enchanted to read that very nearly this was seriously investigated by someone. Specifically, if you ask "what happens in quantum mechanics, if there is a loop in space where the future leads back round to the past"? Well, then it's obvious: you solve the differential equation of how the world evolves over time, with the constraint the state at the start and end of the loop have to match up. QM (and any theory where you solve differential equations) is full of that sort of thing anyway. A priori "satisfying the differential equation" means a ball doesn't suddenly stop in mid-air abandoning all its momentum -- you just can't imagine the world different -- and just as much, a world where trajectories of objects/probabilities are consistent over the loop.

( Read more... )

Assume we are drawing down and to the right again, and that our grid is numbered thusly:

 0 1 2 3 4
  1 # X #
   2 # # #
    3 # # #

The numbers along the top represent the x coordinates. The numbers along the left represent the y-coordinates. Notice that it's not symmetric any more. All the numbers down the left have coordinates x=0, but in real life, are further across. However, this does let us number each hex in a nice, easy, systematic way.

A hex down-and-to-the-right is offset by (+0,+1). A hex down-and-to-the-left is offset by (-1,+1). Fixing up this algorithm to work in any direction will be a bit more fiddly, and I won't bore you with it.

For now we'll assume that our line is from (0,0) to the right and down, and further right than it is down. Eg. from (0,0) to (2,1) or to (4,1).

( Read more... )

Active Recent Entries

1: (no subject)
2: (no subject)

Entries tagged with maths

Graph theory question

Bell Boy Problem

Bags of Holding :Logic Puzzle, Continued

Topology / complex analysis / what

Brainteaser (from Simont?)

Pokemon scanner maths puzzle

More hat-wearing problems

Why I don't get on with statistics

Mathematical humour

How long is the song 'aleph-1 green bottles, hanging on the wall'?

Recreational Maths Pubmeet

Open-access maths journals #2

Open-access maths journals

Mathematiques d'Escalier

Twenty questions with uncertain answers

Back to project euler

Cashing in my CASM for an MMath on 30th apr

Von Neumann, even cleverer than that

Probabalistic resolution of time-travel paradoxes

The sequel: Bressenham's line algorithm on hexagonal grids

Active Recent Entries