Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member royalchicken
    CHAOS GHOST!!!
    05 Jun '04 00:22
    All the numbers to follow are positive integers .

    For what n is it possible to express n/M as the sum of two fractions with numerator 1 for all M? For what M, for each n, is this decoposition unique?

    For example, it is possible for n = 1, and if M is prime the decomposition is unique (are there nonprimes for which it is)?
  2. Donation Acolyte
    Now With Added BA
    05 Jun '04 00:25
    Originally posted by royalchicken
    All the numbers to follow are positive integers .

    For what n is it possible to express n/M as the sum of two fractions with numerator 1 for all M? For what M, for each n, is this decoposition unique?

    For example, it is possible for n = 1, and if M is prime the decomposition is unique (are there nonprimes for which it is)?
    Does k/1 count as a fraction?
  3. Standard member royalchicken
    CHAOS GHOST!!!
    05 Jun '04 00:28
    Yes, but it will only help you sometimes. Since you took STEP in 2002, you've done a special case of this problem unless you're one of those silly people who even attempts the mechanics ones .
  4. Donation Acolyte
    Now With Added BA
    05 Jun '04 00:36
    Originally posted by royalchicken
    Yes, but it will only help you sometimes. Since you took STEP in 2002, you've done a special case of this problem unless you're one of those silly people who even attempts the mechanics ones .
    In that case, it doesn't work for n at least 3.

    For n=2, there's the obvious decomposition 2/M = 1/M + 1/M. Similarly 1/M = 1/2M + 1/2M.

    As for uniqueness, I'll have to think about that. (I don't remember much about STEP)
  5. Standard member royalchicken
    CHAOS GHOST!!!
    05 Jun '04 00:41 / 1 edit
    You're right; I made a mistake by saying 'two'. Take that away and you can at least get it big enough since, eg, the harmonic series diverges.

    I should also say that they go in lowest terms.

    If you leave the 'two' bit, you can still have the parts be distinct though, rather than the 'obvious' 1/m + 1/m...
  6. 06 Jun '04 01:26
    Originally posted by royalchicken
    You're right; I made a mistake by saying 'two'. Take that away and you can at least get it big enough since, eg, the harmonic series diverges.

    I should also say that they go in lowest terms.

    If you leave the 'two' bit, you can still have the parts be distinct though, rather than the 'obvious' 1/m + 1/m...
    Without the "two" bit, n=1 is a trivial solution

    1/1 = 1/1
    1/2 = 1/2
    etc
  7. Standard member royalchicken
    CHAOS GHOST!!!
    06 Jun '04 02:43
    Originally posted by iamatiger
    Without the "two" bit, n=1 is a trivial solution

    1/1 = 1/1
    1/2 = 1/2
    etc
    Okay, my bad. By removing the 'two' bit I meant to imply 'two or more', but it really isn't clear.
  8. Donation Acolyte
    Now With Added BA
    06 Jun '04 08:04
    Originally posted by royalchicken
    Okay, my bad. By removing the 'two' bit I meant to imply 'two or more', but it really isn't clear.
    As in 'two or more distinct'? Otherwise we have n/M = (1/M n times) for n>1.
  9. Standard member TheMaster37
    Kupikupopo!
    06 Jun '04 17:36
    It DOES work for some n>=3

    3/12 = 1/6 + 1/12

    7/24 = 1/4 + 1/24
  10. Standard member royalchicken
    CHAOS GHOST!!!
    07 Jun '04 02:41
    Well, I wanted lowest terms, so 3/12 is right out.
  11. 07 Jun '04 07:20
    Originally posted by royalchicken
    Okay, my bad. By removing the 'two' bit I meant to imply 'two or more', but it really isn't clear.
    42
  12. Donation Acolyte
    Now With Added BA
    08 Jun '04 08:54
    OK, I think I can do this indirectly. I'm assuming 'two or more (but finitely many) distinct' below.

    Let f(1) = 1/2, 1/3, 1/6
    f(1/(n-1)) = 1/n, 1/n(n-1) for n > 2.

    Then f decomposes 1/k into distinct fractions with numerator 1 and larger denominator.

    Let S1 = f(1).

    By applying f repeatedly to the terms in Sn and the resulting terms, we can obtain another decomposition S(n+1) of 1 that does not involve the terms of S1, ..., Sn. Hence we can decompose any natural number n by induction, by combining S1, ..., Sn. Now multiply the denominator of each term in the resulting decomposition by M, and we have a decomposition of n/M. This decomposition is not unique, as we can certainly apply f to the term with the highest denominator to get a different decomposition satisfying the conditions.
  13. Donation Acolyte
    Now With Added BA
    08 Jun '04 10:30 / 1 edit
    Now for the 'exactly two distinct' case:

    Suppose n/M = 1/ck + 1/dk, where c and d are coprime and aren't both 1
    <=> cdkn = M(c+d)

    Now cd, c+d are coprime; n, M are coprime
    <=> cd|M, (c+d)|kn, n|(c+d), M|cdk
    <=> cdp = M, nq = (c+d), k = pq

    So a decomposition is possible iff we can find coprime factors of M whose sum is a multiple of n (then we can choose k,p,q to fit).

    I can't think of a general answer right now, but two things are immediate:
    n = 1: decomposition is always possible
    M prime: decompositions, if they exist, are unique

    Come to think of it,
    n = 1: since we can choose any pair of factors, if M is composite then the decomposition is not unique.
    n = 2: decomposition is possible for M > 2, since M must have an odd factor f greater than 1, and f+1 is even. The decomposition is unique iff these are the only two odd factors of M => M is a power of 2 times a prime => M is prime.