Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

Impossible scores identity?

Short version: I found an unexpected identity,

Floor(a/b)+Floor(2a/b)+...+Floor((b-1)a/b)

= Floor(b/a)+Floor(2b/a)+...+Floor((a-1)b/a)

where a, b>0 are integers. Is there a "nicer" way to write this sum? I'm particularly interested in the case when a and b are relatively prime. For example, restricting to such pairs and letting a=2^k, these sums are (a-1)(b-1)/2.

For context, with the Super Bowl today, I was wondering what scores were theoretically possible. You can score 2 or 3 points (among others), which is sufficient to score any non-negative integer except 1. If a, b>0 are relatively prime, the sums above represent the number of exceptions, i.e. the number of scores that are not theoretically possible in a game where you can score a or b points at a time. (If they are not relatively prime, a similar interpretation works, but it's complicated by the fact that infinitely many scores are unobtainable.)

Update:

...sigh. Y!A's horrible typesetting strikes again. The formulas are:

Floor(a/b) + Floor(2a/b) + ... + Floor((b-1)a/b)

= Floor(b/a) + Floor(2b/a) + ... + Floor((a-1)b/a)

Update 2:

Ah cool, thanks Pauley Morph. It follows roughly from your picture that my sum in general is (a-1)(b-1)/2 + (gcd(a,b)-1)/2, which is (a-1)(b-1)/2 when they are relatively prime. Much nicer than I expected.

1 Answer

Relevance
  • 7 years ago
    Favorite Answer

    I hope this picture explains things enough.

    Attachment image
Still have questions? Get your answers by asking now.