• Welcome to the Cricket Web forums, one of the biggest forums in the world dedicated to cricket.

    You are currently viewing our boards as a guest which gives you limited access to view most discussions and access our other features. By joining our free community you will have access to post topics, respond to polls, upload content and access many other special features. Registration is fast, simple and absolutely free so please, join the Cricket Web community today!

    If you have any problems with the registration process or your account login, please contact us.

The Maths Thread

Magrat Garlick

Magrat Garlick

Global Moderator
Spark said:
Incidentally, algebraic geometry - particular EGA and SGA and what it led to, since I already know enough of the classical stuff to move on to that - is high on my list of "things to teach myself when I have time".
Click to expand...
i heard all the relevant papers were written by Grothendieck in impenetrable French
 
Spark

Spark

Global Moderator
Magrat Garlick said:
i heard all the relevant papers were written by Grothendieck in impenetrable French
Click to expand...
I've read part of EGA 1 - it's actually very readable and easy to understand, even in French (you can basically guess what most of the important words mean, and equations need no translation), but to an excess, as hard as that is to fathom. The way both EGA and SGA are structured is that it's a seemingly endless series of seemingly utterly trivial statements, so much so that you can't quite see how, or even if, any progress is being made, and then suddenly out of nowhere some utterly amazing result will pop out of you, presented again as a near-triviality, and you quickly backup to work out how the **** that happened seemingly by magic. That was Grothendieck's entire schtick ofc, and a big part of the reason he's probably the greatest mathematician of the 20th century by a margin. Aside from comprehensively teeing up the entire framework under which most of 20th century algebraic geometry and closely related fields (number theory etc) would proceed ofc.
 
vcs

vcs

Well-known member
*Puzzle:*

Steve is taking a bus to the Central Park. Steve tells Alice the hour of his bus departure and he tells Annie at which minute it leaves. He also tells them both that the bus leaves between 0600 and 1000.

Alice & Annie consult the timetable and find the following services between those two time: 0632 0643 0650 0717 0746 0819 0832 0917 0919 0950.

Alice then says “I don’t know when Steve’s bus leaves but I am sure that neither does Annie”

Annie Replies “I didn’t know his bus, but now i do”

Alice responds “Now I do as well!”

When is Steve’s bus?
Click to expand...
Not very difficult TBH.
 
vcs

vcs

Well-known member
Spark said:
pay attention to the wording
Click to expand...
Yeah I got the solution that enters room 13 twice (the problem doesn't prohibit that).

But what's the general theory you would use to prove or disprove the existence of such paths in an N x M grid? Hamiltonian paths is NP complete. I am sure we can make some clever argument to show when a solution exists in this special case. For example, if both N and M are even, you cannot start at one corner and exit at the diagonally opposite corner. But you can do it for adjacent corners. All this seems intuitive and comes out clearly with a bit of trial and error but I'd like a cleverer argument. Let's just stick to rectangular grid type of graphs and entering at one corner and exiting at another.
 
Spark

Spark

Global Moderator
vcs said:
Yeah I got the solution that enters room 13 twice (the problem doesn't prohibit that).

But what's the general theory you would use to prove or disprove the existence of such paths in an N x M grid? Hamiltonian paths is NP complete. I am sure we can make some clever argument to show when a solution exists in this special case. For example, if both N and M are even, you cannot start at one corner and exit at the diagonally opposite corner. But you can do it for adjacent corners. All this seems intuitive and comes out clearly with a bit of trial and error but I'd like a cleverer argument. Let's just stick to rectangular grid type of graphs and entering at one corner and exiting at another.
Click to expand...
you can. just not for a 4x4 grid (hilbert curve requires adjacent corners if you restrict yourself to vertical/horizontal lines). a 9x9 grid would work fine, then you just draw a peano curve.

the problem is clearly designed to be a trick question emphasising that you have to be absolutely precise with your language in maths (a lesson worth taking to heart tbf), rather than an interesting analysis of space filling curves.

e: error
 
Last edited:
vcs

vcs

Well-known member
Interesting, though I don't know much about space filling curves. Will read up.

I'm thinking something simpler, like pigeon hole principle, or some clever argument exploiting the odd/even nature of the degree of the vertices. Or a bijection showing the problem to be equivalent to something else.
 
vcs

vcs

Well-known member
Hmm, but bridges of Konigsberg requires that each bridge be crossed exactly once. We don't require that here. Do we take the dual of the graph and treat the cells of the grid as edges instead?
 
vcs

vcs

Well-known member
The idea of using A and B as terminal nodes is a good one. Let me think further along those lines.
 
Spark

Spark

Global Moderator
vcs said:
Hmm, but bridges of Konigsberg requires that each bridge be crossed exactly once. We don't require that here. Do we take the dual of the graph and treat the cells of the grid as edges instead?
Click to expand...
yeah i mixed up hamiltonian and eulerian paths. unfortunately it seems like there's a lot less theory on hamiltonian paths beyond brute force.
 
You must log in or register to reply here.
Top