/sci/ - Science & Math

I've seen psistar one or two weeks ago. He posted a putnam problem. Can't remember if we solved it, I remember made a few fail observations about the problem :/

>>5668793
(cont)

The ratio between the furthest distance from A to B and the smallest distance from A to B during B's orbit can be written as <span class="math">\frac{1+e}{1-e}[/spoiler]. Solving for a ratio of 1.05 (meaning that A would be 1.05 times closer to B when B is at its lowest orbit), and considering A is the sun and B is Earth, we get <span class="math">T=1.38[/spoiler] days (assuming Earth's orbit is almost circular before the fuck-up).

Therefore, 10 seconds wouldn't affect Earth distance to the Sun at all. However, a few days would make Earth's orbit an ellipsis with a distance to the Sun that would vary a lot during the year, most likely implying very cold winters and very hot summers, potentially with UV burns etc.

Let's consider a two-body (A and B) system where gravity breaks, starting from a situation where B's orbit around A is circular, if we stop gravity during a certain amount of time.

Let P be the period of an orbit and <span class="math">r_0[/spoiler] be its radius before gravity fucks up. Let T be the duration of the fuck-up. The distance traveled during the fuck-up is <span class="math">T\frac{2\pi r_0}{P}[/spoiler], where <span class="math">\frac{2\pi r_0}{P}[/spoiler] is the (constant) velocity of B around A before the fuck-up (which remains constant during the fuck-up because no force implies no acceleration).

Let's call <span class="math">B_0[/spoiler] the position of B right at the beginning of the fuck-up, and <span class="math">B_T[/spoiler] its position right after. The line segment <span class="math">B_0B_T[/spoiler] is orthogonal to <span class="math">AB_0[/spoiler], and its length is <span class="math">T\frac{2\pi r_0}{P}[/spoiler], therefore using the Pythagorean theorem, the length of <span class="math">AB_T[/spoiler] is <span class="math">r_T=r_0\sqrt{1+4\pi^2\left(\frac{T}{P}\right)^2}[/spoiler].

The eccentricity <span class="math">e_0[/spoiler] before the fuck-up is <div class="math">e_0=\sqrt{1+ \frac{2r_0^4 \dot{\theta}^2 }{G^2M^2m} \left(K -G\frac{Mm}{r_0}\right)}</div> where K is a constant so that <span class="math">e_0=0[/spoiler], thus <div class="math">K=G\frac{Mm}{r_0}-\frac{G^2M^2m}{2r_0^4 \dot{\theta}^2 }</div>.

The eccentricity after the fuck-up therefore becomes <div class="math">e_T=\sqrt{1+ \frac{2r_0^4 \dot{\theta}^2 }{G^2M^2m} \left(K -G\frac{Mm}{r_T}\right)}= \sqrt{2r_0^4 \dot{\theta}^2 \left(\frac{1}{GMr_0} -\frac{1}{GMr_T}\right)} = \dot{\theta}\sqrt{\frac{2r_0^3}{GM}\frac{r_T-r_0}{r_T}}</div>
<div class="math">= \dot{\theta}\sqrt{\frac{2r_0^3}{GM} \left(1-\frac{1}{\sqrt{1+4\pi^2 \left(\frac{T}{P}\right)^2}} \right )}</div>

Let's consider a two-body (A and B) system where gravity breaks, starting from a situation where B's orbit around A is circular, if we stop gravity during a certain amount of time.

Let P be the period of an orbit and <span class="math">r_0[/spoiler] be its radius before gravity fucks up. Let T be the duration of the fuck-up. The distance traveled during the fuck-up is <span class="math">T\frac{2\pi r_0}{P}[/spoiler], where <span class="math">\frac{2\pi r_0}{P}[/spoiler] is the (constant) velocity of B around A before the fuck-up (which remains constant during the fuck-up because no force implies no acceleration).

Let's call <span class="math">B_0[/spoiler] the position of B right at the beginning of the fuck-up, and <span class="math">B_T[/spoiler] its position right after. The line segment <span class="math">B_0B_T[/spoiler] is orthogonal to <span class="math">AB_0[/spoiler], and its length is <span class="math">T\frac{2\pi r_0}{P}[/spoiler], therefore using the Pythagorean theorem, the length of <span class="math">AB_T[/spoiler] is <span class="math">r_T=r_0\sqrt{1+4\pi^2\left(\frac{T}{P}\right)^2}[/spoiler].

The eccentricity <span class="math">e_0[/spoiler] before the fuck-up is <div class="math">e_0=\sqrt{1+ \frac{2r_0^4 \dot{\theta}^2 }{G^2M^2m} \left(K -G\frac{Mm}{r_0}\right)}</div> where K is a constant so that <span class="math">e_0=0[/spoiler], thus <div class="math">K=G\frac{Mm}{r_0}-\frac{G^2M^2m}{2r_0^4 \dot{\theta}^2 }</div>.

The eccentricity after the fuck-up therefore becomes <div class="math">e_T=\sqrt{1+ \frac{2r_0^4 \dot{\theta}^2 }{G^2M^2m} \left(K -G\frac{Mm}{r_T}\right)}= \sqrt{2r_0^4 \dot{\theta}^2 \left(\frac{1}{GMr_0} -\frac{1}{GMr_T}\right)} = \dot{\theta}\sqrt{\frac{2r_0^3}{GM}\frac{r_T-r_0}{r_T}}</div>
<div class="math">= \dot{\theta}\sqrt{\frac{2r_0^3}{GM} \left(1-\frac{1}{\sqrt{1+4\pi^2\ left(\frac{T}{P}\right)^2}} \right )}</div>

Let's consider a two-body (A and B) system where gravity breaks, starting from a situation where B's orbit around A is circular, if we stop gravity during a certain amount of time.

Let P be the period of an orbit and <span class="math">r_0[/spoiler] be its radius before gravity fucks up. Let T be the duration of the fuck-up. The distance traveled during the fuck-up is <span class="math">T\frac{2\pi r_0}{P}[/spoiler], where <span class="math">\frac{2\pi r_0}{P}[/spoiler] is the (constant) velocity of B around A before the fuck-up (which remains constant during the fuck-up because no force implies no acceleration).

Let's call <span class="math">B_0[/spoiler] the position of B right at the beginning of the fuck-up, and <span class="math">B_T[/spoiler] its position right after. The line segment <span class="math">B_0B_T[/spoiler] is orthogonal to <span class="math">AB_0[/spoiler], and its length is <span class="math">T\frac{2\pi r_0}{P}[/spoiler], therefore using the Pythagorean theorem, the length of <span class="math">AB_T[/spoiler] is <span class="math">r_T=r_0\sqrt{1+4\pi^2\left(\frac{T}{P}\right)^2}[/spoiler].

The eccentricity <span class="math">e_0[/spoiler] before the fuck-up is <div class="math">e_0=\sqrt{1+ \frac{2r_0^4 \dot{\theta}^2 }{G^2M^2m} \left(K -G\frac{Mm}{r_0}\right)}</div> where K is a constant so that <span class="math">e_0=0[/spoiler], thus <div class="math">K=G\frac{Mm}{r_0}-\frac{G^2M^2m}{2r_0^4 \dot{\theta}^2 }</div>.

The eccentricity after the fuck-up therefore becomes <div class="math">e_T=\sqrt{1+ \frac{2r_0^4 \dot{\theta}^2 }{G^2M^2m} \left(K -G\frac{Mm}{r_T}\right)}= \sqrt{2r_0^4 \dot{\theta}^2 \left(\frac{1}{GMr_0} -\frac{1}{GMr_T}\right)} = \dot{\theta}\sqrt{\frac{2r_0^3}{GM}\frac{r_T-r_0}{r_T}}</div><div class="math">= \dot{\theta}\sqrt{\frac{2r_0^3}{GM}\left(1-\frac{1}{\sqrt{1+4\pi^2\left(\frac{T}{P}\right)^2}} \right )}</div>

>>5664609
I've got a hunch that looking at the signatures of permutations might be a good way to encode information, since basically we always need to identify one out of two numbers, and there are two possible signatures for each permutation, and local changes on permutations usually change the signature. It looks like it has good properties, I'm just not sure exactly how to put it in action.

>>5664579
LaTeX-fail. Reporsting.

>>5664547
Okay, so the reason that works is because there is a function f with the following properties:

<span class="math">f: D\to \{1,2,3,4\}[/spoiler] where <span class="math">D =\{(a,b)\in \{1,2,3,4\}^2 | a\neq b\}[/spoiler]

<span class="math">\forall (a,b)\in D,\ f(a,b)\not\in \{a,b\}[/spoiler]

<span class="math">\forall ((a_1,b_1), (a_2,b_2)) \in D^2[/spoiler], <span class="math">if b_1=b_2[/spoiler] and <span class="math">f(a_1,b_1)=f(a_2,b_2)[/spoiler] then <span class="math">a_1=a_2[/spoiler].

<span class="math">\forall ((a_1,b_1), (a_2,b_2)) \in D^2[/spoiler], if <span class="math">a_1=a_2[/spoiler] and <span class="math">f(a_1,b_1)=f(a_2,b_2)[/spoiler] then <span class="math">b_1=b_2[/spoiler].

f is the function I will use for the 1st wizard, where a and b are the two hats he sees. Because of the last property, whatever the configuration, using what the 1st wizard said (f(a,b)) and what the 3rd wizard wears (b), the 2nd wizard can recover and say a.

Similarly, because of the 4th property, using what the 1st and 2nd wizard said (respectively f(a,b) and a), the 2nd wizard can recover and say b.

I think these functions are easy to find and to generalize to most wizards (promoting all except for one). I'll be trying for a while.

>>5664547
Okay, so the reason that works is because there is a function f with the following properties:

<span class="math">f: D\to \{1,2,3,4\}[/spoiler] where <span class="math">D =\{(a,b)\in \{1,2,3,4\}^2 | a\neq b\}[/spoiler]

<span class="math">\forall (a,b)\in D,\ f(a,b)\not\in \{a,b\}<span class="math">

\forall ((a_1,b_1), (a_2,b_2)) \in D^2, if b_1=b_2 and f(a_1,b_1)=f(a_2,b_2) then a_1=a_2.

\forall ((a_1,b_1), (a_2,b_2)) \in D^2, if a_1=a_2 and f(a_1,b_1)=f(a_2,b_2) then b_1=b_2.

f is the function I will use for the 1st wizard, where a and b are the two hats he sees. Because of the last property, whatever the configuration, using what the 1st wizard said (f(a,b)) and what the 3rd wizard wears (b), the 2nd wizard can recover and say a. Similarly, because of the 4th property, using what the 1st and 2nd wizard said (respectively f(a,b) and a), the 2nd wizard can recover and say b.

I think these functions are easy to find and to generalize to most wizards (promoting all except for one). I'll be trying for a while.[/spoiler][/spoiler]

>>5664541
Actually you can. The rational number 1/(100*k) + 0.23 contains the decimals of 1/k. It just starts with 0.23, the rest is the decimals of 1/k exactly.

>>5664432
Oh, no, I was on the simple case.

I gave a try at the 3,4 problem (3 wizards, 4 hats), trying to guarantee that 2 wizards are promoted at least.

Cheating a little bit with some brute-forcing (which wasn't so trivial to implement, actually), I found a few solutions that I haven't started to try and understand. I'll write one down here and if someone wants to see if they can make some sense out of it and generalize it to save 999 wizards, go ahead.

I list every possible configuration of the hats, and what wizards say. You can manually check that in two configurations in which a wizard sees and hears the same, he also says the same thing (obviously). The format is the following:
a,b,c|d => e f g (h)
where
- a is the hat of the 1st wizard,
- b is the hat of the 2nd wizard,
- c is the hat of the 3rd wizard,
- d is the unused hat,
- e is what the 1st wizard says,
- f is what the 2nd wizard says,
- g is what the 3rd wizard says,
- h is how many wizards were correct (at least 2 here).
Hopefully my code was correct. Let me know if it doesn't work.

1,2,3|4 => 1 2 3 (3)
2,1,3|4 => 4 1 3 (2)
1,3,2|4 => 4 3 2 (2)
3,1,2|4 => 3 1 2 (3)
2,3,1|4 => 2 3 1 (3)
3,2,1|4 => 4 2 1 (2)
1,2,4|3 => 3 2 4 (2)
2,1,4|3 => 2 1 4 (3)
1,4,2|3 => 1 4 2 (3)
4,1,2|3 => 3 1 2 (2)
2,4,1|3 => 3 4 1 (2)
4,2,1|3 => 4 2 1 (3)
1,3,4|2 => 1 3 4 (3)
3,1,4|2 => 2 1 4 (2)
1,4,3|2 => 2 4 3 (2)
4,1,3|2 => 4 1 3 (3)
3,4,1|2 => 3 4 1 (3)
4,3,1|2 => 2 3 1 (2)
2,3,4|1 => 1 3 4 (2)
3,2,4|1 => 3 2 4 (3)
2,4,3|1 => 2 4 3 (3)
4,2,3|1 => 1 2 3 (2)
3,4,2|1 => 1 4 2 (2)
4,3,2|1 => 4 3 2 (3)

>>5664425
Well, not specifically to you. Hopefully even if you knew all about it, OP learned something anyway :)

>>5664405
(cont)

The computational complexity of that algorithm isn't that much:
- last_n is at most the number of vertices in the graph (because we add at last one to w(n) each time we increment n, otherwise we stop).
- for each n, we have a number of operations to do which is at most linear in the number of vertices in the graph (assuming the number of possible moves from a given position is small compared to the number of vertices in the graph).

Therefore if there are N states in the graph, the complexity is in O(N^2). However in fact, by tweaking the algorithm a bit, you can make sure you don't process the same node too many times uselessly, and have run times that are roughly O(N).

For our example, N is at most 2*64*63*62*61 (some possibilities can most likely be excluded). That's roughly 30 million. Easy.

>>5664017
Ups, actually it's hypergeometric functions, not incomplete gamme functions. Whatever, I meant that it's complicated shit.

Look up multinomial coefficients. There are formulas for them a bit like in the binomial coefficients case, but they are in general harder to manipulate, and their sums usually involve incomplete gamma functions, which are not elementary.

>>5657763
You do. You have to use each edge exactly one, but you can go several times through the same vertex.

>>5657573
Also I just realized I wrote Euclidean for Eulerian everywhere in this post. Damn...

>>5657745
It is indeed Eulerian. I'm assuming that you are referring to the one called "pentatope graph" in http://mathworld.wolfram.com/EulerianGraph.html

The pentagon is a cycle, and the star is a cycle too, just start from any vertex, draw the pentagon and you'll end up where you started, then draw the star, you'll end up where you started again, and all vertices will be on that cycle.

>>5657521
Yeah, graph theory is also a few years back for me, I can't think about it properly without writing down a lot of stuff anymore.

Anyway, I've been trying on my own and I think that basically I end up with the same idea as yours. I'd present it by induction on the number of those maximum cycles:

If you can partition E into a single cycle, then you're done.

Assume that any graph such that can be decomposed into exactly n maximum cycles is Euclidean. Consider a graph G whose set of edges E can be decomposed into n+1 maximum cycles.

Consider a subgraph G' of G composed of n of its n+1 maximum cycles. That subgraph, restricted to the vertices that it visits, is Euclidean by induction hypothesis, let's call <span class="math">C_e[/spoiler] one of that graph's Euclidean cycles. By connectivity, it must have at least one vertex v in common with the leftover cycle C. Because <span class="math">C_e[/spoiler] and C are cycles, you can make them at vertex v, so that <span class="math">C_e=v\to v_1\to v_2\to v_3\to \dots\to v_k\to v[/spoiler] and <span class="math">C=v\to v_1'\to v_2'\to v_3'\to \dots\to v_l'\to v[/spoiler], where the edges of C and <span class="math">C_e[/spoiler] are disjoint. Therefore G admits the Euclidean cycles <span class="math">v\to v_1\to v_2\to v_3\to \dots\to v_k\to v\to v_1'\to v_2'\to v_3'\to \dots\to v_l'\to v[/spoiler].

Sounds good to you?

>>5657508
Oh, so basically you mean you should consider "maximum" cycles C, somehow (cycles that are not included into larger cycles)? Then yeah, you're probably right.

>>5657505
Yeah, by 1<->2 I meant that there is a connection from 1 to 2 and a connection from 2 to 1. I think that's the context in which Eulerian graphs are usually defined (directed graphs in which it is possible to have symmetrical connections).

>>5657480
>Then each component (cycle) of G' had a vertex in the C by connectedness.

No. Say that G is:
1<->2<->3<->4

G is connected and decomposable into the cycles 1<->2, 2<->3 and 3<->4. If you remove C=1<->2, you get G'=2<->3<->4, and the cycle 3<->4 from G' has no vertex in C.

I agree that it must be something like that, trying to translate connectivity on cycles instead of just vertices and removing edges from the cycles that we used, but it's not that direct.

>>5654717
(cont)

Anyway, if you want a few examples, give me 3 foci and a radius and I'll post the 3-ellipse. My algo is awfully slow because I'm not formally solving systems of equations for each point and only the numerically approximating the result. I could make the algorithm faster but I didn't bother. It also only works with 3 foci, I don't think I can make it work for more foci without considerably slowing down the already slow algorithm.

>>5654667
Damn, I'm late. I gave it a fast try anyway, here's what I built if you're interested. Black points are the 3-ellipse, red points are the foci, radius is R=5.

Maple is shit but did the job.

>>5652537
Cause it's fun.

I've coded a small test to see if the list from my previous post is enough. It's not :/

Here are how many entries I have to read in the table for r(n) to get to 1,2,3,4,5,... It's not linear after all:

r(n)=2 for 2 entries read (n has 1 digits)
r(n)=3 for 5 entries read (n has 3 digits)
r(n)=4 for 9 entries read (n has 5 digits)
r(n)=5 for 14 entries read (n has 9 digits)
r(n)=6 for 19 entries read (n has 15 digits)
r(n)=7 for 27 entries read (n has 25 digits)
r(n)=8 for 40 entries read (n has 44 digits)
r(n)=9 for 56 entries read (n has 74 digits)
r(n)=10 for 82 entries read (n has 127 digits)
r(n)=11 for 119 entries read (n has 218 digits)
r(n)=12 for 180 entries read (n has 379 digits)
r(n)=13 for 275 entries read (n has 659 digits)
r(n)=14 for 426 entries read (n has 1147 digits)
r(n)=15 for 673 entries read (n has 2001 digits)
r(n)=16 for 1072 entries read (n has 3495 digits)
r(n)=17 for 1728 entries read (n has 6113 digits)
r(n)=18 for 2807 entries read (n has 10700 digits)

I didn't wait for r(n)=19/20, they can probably be reached within the table, but 100 definitely cannot.

I can give you the roughly hundred digits of an n that has r(n)=10 if you want.