6
$\begingroup$

Can we algorithmically infer the number of comets that orbit the Earth, based upon periodic observations of them, if we cannot tell the comets apart? In more detail:

The problem

  • There is an unknown, fixed number of comets, numComets that pass by Earth and are visible from the ground.

  • Each comet takes a fixed number of years to orbit Earth.

  • Based only on this knowledge and the dates recorded that a comet was sighted in the night sky, determine numComets, AND determine the orbital period of each comet. You can use an unlimited amount of observation data (time), but the solution in the shortest amount of
    time is preferable.

Assumptions you can make

  • All comets look identical from the ground; there is no way to visually identify them.

  • No other object will be mistaken for a comet, and all comets will be seen.

  • No comet takes more than 100 years to orbit Earth, and no new comets will be introduced.

As current answers have pointed out, the problem as it lay now is unsolvable. Would a solution be possible if numComets is known? (Even roughly get the right answer?) What modifications to the problem would have to be made otherwise, to still encasulate the spirit of the problem, and make it solvable? (or is it dead with no hope of solving accurately?)

Further assumption

All comets start at a different point in their orbit. I.e. They do not all start their orbit at the same place like racehorses coming out of a gate.

Clarification

Comets are only recorded once per year. So there is no difference between a comet that passes at the beginning of a year and at the end. The problem could just as easily have been worded as days.

|cite|improve this question
$\endgroup$
  • $\begingroup$ It seems clear from your last sentence that you would not recognize an answer if you saw one. You state your problem as involving only integers, and that has consequences. $\endgroup$ – babou Aug 2 '14 at 16:30
  • $\begingroup$ Could be you more specific, rather than just plain rude? $\endgroup$ – Bassinator Aug 2 '14 at 16:46
  • $\begingroup$ @HCBPshenanigans babou's comment it not rude, it's merely an estimation of your level of knowledge/skill and concludes that he thinks we can't help you. (I won't comment on whether he's right). $\endgroup$ – Raphael♦ Aug 2 '14 at 16:55
  • 1
    $\begingroup$ Regarding your edit, please don't shout. Emphasising formatting should be used sparlingly. Also, posts should always be "wholesome"; please integrate changes into the original post as opposed to keep adding material at the bottom. $\endgroup$ – Raphael♦ Aug 2 '14 at 16:56
  • 1
    $\begingroup$ Actually, the horse race gate situation is unavoidable when obital times are prime to each other, not if two of them have a common divider. For example if 2 comets have periods 2 years and 6 years, and appear once at a one year interval, then they will never appear the same year. $\endgroup$ – babou Aug 2 '14 at 18:49
10
$\begingroup$

Based on the restriction you gave, that you cannot identify one comet from another, there is no difinative method of calculation. Here is a proposed situation, There are 2 comets following the same trajectory, they each orbit at exactly ten year orbit durations, so each one is seen every ten years, they are however exactly 5 years apart in their orbits. From the ground if we cannot differentiate between these two comets we only see a comet appear overhead regularly every 5 years, there is no way to tell if this is one comet appearing ever 5 years, or two comets appearing every ten years, but 5 years apart. From this it is impossible to deterministically say how many comets there are, so no algorithm can give you numComets with the assumptions that you have specified.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ D'oh! Although this answer is actually useful. It is just as useful to know the types of problems that cannot be solved as the ones that can. What if we said that an error of this sort was allowable? We are just looking for general correctness. $\endgroup$ – Bassinator Jul 31 '14 at 15:12
  • 1
    $\begingroup$ If numComets was known, would this make the resulting calculations possible? $\endgroup$ – Bassinator Jul 31 '14 at 15:13
  • 3
    $\begingroup$ @HCBPshenanigans I think yes, assuming all comets start at year 0 (wlog; at some point, namely the smallest common multiple of their orbits, their observations coincide), via solving the system of equations like $\sum_{i=1}^C [o_i \mod y = 0] = c_y$ (sum a one for each comet that visits in year $y$; has to equal count of comets in that year $c_y$.) $\endgroup$ – Raphael♦ Jul 31 '14 at 17:20
  • $\begingroup$ Addendum: time zero is not attainable in the way I claimed; comets with the same orbit time miss each other forever. I think you can add this to the equation system, though. $\endgroup$ – Raphael♦ Jul 31 '14 at 21:22
1
$\begingroup$

Observations begin with year 0.

Let $c_{i,j}$ the number of comets sighted the first time on year $j$ that have an $i$ years orbit, with $i\in[1,100]$ and $j\in [0,i-1]$. Let $n_k$ be the number of comets sighted on year $k$.

Each year of observation gives an equation: $$\sum_{i=1}^{100}c_{i,k\bmod i}=n_k$$

The total number of comets is $$\sum_{i=1}^{100}\sum_{j=0}^{i-1}c_{i,j}$$

There are $100\times 101/2=5050\; $ variables, so one could think that this number of years of observation would give enough equations. But it is likely that many equations will turn out to be linear conbinations of others. On the other hand, this will be a system of linear Diophantine equations (i.e. using only integers). In this case, resolution may not require as many equations as there are variables.

To be sure to observe everything, it is better to do it until the set of comets return to its initial configuration, which is after a number of years that is the least common multiple of the first hundred integers: I have not computed it, but it seems to be somewhat longer than the current age of the universe (probably even when measured in seconds - it broke my LCM calculator). But as Tycho-Brahe taught us, astronomy is a science for the patient.

Maybe a better analysis would show that less years may be needed (I doubt it, but I am not sure). Else, we just get an approximation, or improve the precision of the solution as time goes by and more observations are available. Anyway, we know that there is some indeterminacy in the problem that prevents distinguishing an obit from its harmonics, as remarked in another answer. So we know we will not get enough linearly independent equations anyway.

Well, once we have the equations, we solve them as much as possible, and get a set of possible answers, depending on a few remaining variables that can be freely chosen.

Then we can impose a further constraint on the total number, which reduces by one the degree of freedom on the answer.

This is probably not be a complete resolution of the problem. Only integer solutions are acceptable, and it is not clear to me that resolving the equations give only integer answers.

Systems of linear equations are normally solved over a field, and integers do not form a field. So some of the solutions found will be rational numbers, as rationals do form a field. But that is not acceptable. Some integer solutions must exist, though, as it is an hypothesis of the question: parameters of the problem result from observation of a solution (except for the total number of comets which can only be given by an oracle). So integer solutions will have to be extracted from the set of rational solutions, I suppose with divisibility considerations.

But my memory of the properties of linear diophantines systems and their resolution is gone, whatever it was at an earlier age. So I leave this for someone else, unless I find enough information on the web, and the time to read it.

This calls for a few remarks.

  • It is not a problem of algorithmics but of formalization.

  • The OP obviously knew the solution before he asked

His strange behavior made me react. I am wary of technical questions supposedly naive, because the asker is often gone when I post the answer, not to come back ... and I hate it. Then the reaction of the OP gave me the clue: he knew. That was motivating.

I have an excuse: I am not a native speaker. What is the meaning of HCBP?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Haha, HCBP stands for Hard Core Battlefield Players. Stupid little video game clan I made up when I was much younger. I guess it just kinda stuck. $\endgroup$ – Bassinator Aug 4 '14 at 0:28
  • $\begingroup$ And babou, I did not know the answer to the problem when I asked. I merely thought of a possible problem that got me curious; I was thinking of how people figured this out long ago, and wanted to relate my question to programming. But I am glad to have motivated you! Honestly though, it was just a dumb question I had. $\endgroup$ – Bassinator Aug 4 '14 at 0:35
  • $\begingroup$ @HCBPshenanigans At first, it looked like many supposedly naive questions that keep changing as people try to answer them and see problems. On some occasions, I spent hours answering a question that kept changing over time, from a fellow who obviously did not know what he wanted, and did not really seem to understand his own problem and its limitations. As a reasult, we too often tend to answer too quickly, if at all, unless we find the issue catchy enough, which was not my case here. But I still find it hard to believe this was an idle question, without a further motivation. $\endgroup$ – babou Aug 4 '14 at 11:41
  • 1
    $\begingroup$ On the other hand, Diophantine equations were the first to be analyzed historically, afaik. Then it should not be too much of a surprise that a "naive" or "dumb" question would hit that subject ... even though the ancient mathematicians were neither naive nor dumb. But, of course, comets were never studied that way. Calendars were quite good pretty early in history. Ahem ... if you are so new to the issue, how did you know that @Raphael 's hypothesis did not necessarily hold, since you kept excluding it? $\endgroup$ – babou Aug 4 '14 at 11:50
  • $\begingroup$ I dunno, it just didn't make sense. It didn't seem complete. I can't really give specifics. As you said, I am quite ignorant of this topic. It took me a good 20 minutes to figure out the equation you posted, and I'm still not sure I get it; I'd like to think I'm quite good at math but this thread shows that I still have college ahead of me. $\endgroup$ – Bassinator Aug 4 '14 at 12:17
0
$\begingroup$

Let $t_1, t_2, ...$ be the times that comets were seen, in reverse chronological order (that is $t_1$ is the latest).

Start with comet $t_1$, and consider all candidates that were seen before. For example, if you assume that $t_2$ is the same comet as $t_1$, then the period is $T = t_1 - t_2$. Now all you need to do is to check whether there was a comet at times $t_1 - 2T$, $t_1 - 3T$, etc (depending on how rigorous you want to be). If not, then go to the next candidate ($t_3$, and so on). If yes, then congratulations -- you established that comet $t_1$ has period $T$. Exclude this comet together with all its previous sightings $t_1 - kT$ from your dataset. If the dataset is not empty (not all comets have been identified yet), then start from the beginning.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Except that this will not work for the reason stated above, this method can confuse 2 comets each with period $T$ orbiting $T/2$ years apart as one with period $T/2$. $\endgroup$ – lPlant Jul 31 '14 at 20:39
  • 4
    $\begingroup$ The problem is that this is arbitrarily bad, Say I have 100 comets at periods 100 years each one after the other, this gives again a result of one instead of 100. For any value $n$ I can have $n$ comets with periods $T$ orbiting with a gap of $\frac{T}{n}$ time between comets and confuse these $n$ comets for one. If a solution can be shown to be arbitrarily bad it cannot be used for approximations. $\endgroup$ – lPlant Jul 31 '14 at 21:21
  • 1
    $\begingroup$ @lPlant I just want to say, that is an exceptional justification to why this didn't work. I think I learned more from this comment than from any of the (still good) answers. Would upvote it 100 times I could. $\endgroup$ – Bassinator Jul 31 '14 at 23:15
  • 2
    $\begingroup$ @IPlant Don't mistake theoretical limitations with practical ones. The probability of having even 2 comets with EXACTLY the same period and being EXACTLY equidistant is negligible. The question was practical: "how could people in olden times have figured out the number of comets". $\endgroup$ – Pasha Aug 1 '14 at 18:21
  • 1
    $\begingroup$ @PashaS The question asks us to consider everything at a resolution of years. That's how practical it is. Also, I don't believe you can justify any probabilistic model in a rigorous fashion, or can you? In computer science, we are (unless otherwise stated) interested in absolute truth on an abstract level. And here, the answer is that the problem as modelled can not be solved. $\endgroup$ – Raphael♦ Aug 2 '14 at 16:58
-1
$\begingroup$

there are many ways to interpret this problem eg as a machine learning problem. however there is some key theory that is relevant & deserves citing, that of the "N-body" problem in physics. this is the problem of predicting motions of objects based on relative gravitational attraction and its an old problem, long studied, and there is a large amount of theory on the subject. the theory originally developed in working to determine trajectories of planets in the solar system and dates at least to Newton. there are surprising new findings also such that there are instabilities and inherent chaotic dynamics to these types of equations. in other words predictability may be somewhat like the weather, namely that weather over the short term is moderately predictable but over the long term is not deterministically predictable (because of the so-called butterfly effect etc).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ there is even some evidence for undecidability properties in the n-body problem. eg Church's thesis meets N-body problem / Smith $\endgroup$ – vzn Aug 2 '14 at 15:49
  • $\begingroup$ While I'd like to think I'm an intelligent individual, this kinda flew way over my head. I got the gist of what you're saying, but not the reasoning. $\endgroup$ – Bassinator Aug 2 '14 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.