Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

First off, I'm brand new to algorithms.

I thought of the problem and had no idea how to solve it, so to gain better understanding of algorithmic techniques, I thought I'd ask it here.

I was thinking of comets, and how people knew how many comets passed by Earth and such before modern technology.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
1  
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. –  HCBPshenanigans 4 hours ago
1  
If numComets was known, would this make the resulting calculations possible? –  HCBPshenanigans 4 hours ago
1  
@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$.) –  Raphael 2 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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