Results 1 to 14 of 14

Math Help - [SOLVED] Tough Combinations Problem

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    56

    [SOLVED] Tough Combinations Problem

    EDIT: solved.
    Last edited by chickeneaterguy; May 4th 2010 at 06:29 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by chickeneaterguy View Post
    I may be missing something very obvious but this problem seems a bit tough to me. Help?

    Find as many odd integers n less than 200 as you can for which C(n,floor(n/2)) is not divisible by the square of a prime.
    I haven't solved the problem, but I think I know how to begin.

    For reference, "k is not divisible by the square of a prime" is the same as "k is squarefree." Also, the term squareful is the same as nonsquarefree.

    The discussion on this post is very relevant. We can compare prime factorisations of the numerator and denominator of \binom{n}{\lfloor n/2 \rfloor}=\frac{n!}{\lfloor n/2 \rfloor! \cdot \lceil n/2 \rceil!}. For a particular prime, we are interested in whether the exponent in the numerator minus the exponent in the denominator is greater than or equal to 2, in which case the result is squareful. If there is no prime with this property, then the result is squarefree.

    For ease of notation, let k_1=\lfloor n/2 \rfloor and k_2=\lceil n/2 \rceil.

    We can consider each prime power p^\alpha separately, in which case we are comparing the quantities \bigg\lfloor \frac{n}{p^\alpha} \bigg\rfloor and \bigg\lfloor \frac{k_1}{p^\alpha} \bigg\rfloor + \bigg\lfloor \frac{k_2}{p^\alpha} \bigg\rfloor.

    I've only done some preliminary hand calculations and pattern searching and have not proven anything so far. With more time, I'm pretty confident a pattern would emerge which could then be proven. If you're not required to write a proof and are allowed to write a computer program, a naive algorithm will run very quickly for an upper bound of 200.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    Posts
    56
    I THINK the answers are 1,3,5,7,11,17,19,23. I did it through excel. I only used primes up to 1000 though.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by chickeneaterguy View Post
    I THINK the answers are 1,3,5,7,11,17,19,23. I did it through excel. I only used primes up to 1000 though.
    It is not possible to have a prime greater than 200 in any of the calculations here.

    I wrote out a naive program, and in addition to your numbers I also got 71, but no others.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,670
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by undefined View Post
    It is not possible to have a prime greater than 200 in any of the calculations here.

    I wrote out a naive program, and in addition to your numbers I also got 71, but no others.
    71 does not work.
    \binom{71}{\left\lfloor {\frac{{71}}{2}} \right\rfloor}=221256270138418350000
    That number has four ‘trailing zeros’, so both 2^4~\&~5^4 are factors.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Feb 2010
    Posts
    56
    C(71, 35) = 221256270138418389602

    C(71,35) - Wolfram|Alpha

    Confused...
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2009
    Posts
    95
    This is a silly problem if there is no underlying pattern, its too trivial to solve with a computer and if it comes down to brute forcing by hand its just tedious.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,670
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by chickeneaterguy View Post
    C(71, 35) = 221256270138418389602

    C(71,35) - Wolfram|Alpha

    Confused...
    You are correct. And 71 does work.
    I did not set my CAS correctly.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Feb 2010
    Posts
    56
    hey...I have this spreadsheet as I did mine through excel. Can someone explain to me(or maybe just look) at what's wrong with this since I'm not getting 71 as an answer?
    Last edited by chickeneaterguy; May 4th 2010 at 06:29 PM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,670
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by chickeneaterguy View Post
    hey...I have this spreadsheet as I did mine through excel. Can someone explain to me(or maybe just look) at what's wrong with this since I'm not getting 71 as an answer?
    That is most likely the same problem I had with my computer algebra system.
    Excel is not a symbolic algebra system.
    Wolfram|alpha is.
    Ask it to factor that number.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Feb 2010
    Posts
    56
    Quote Originally Posted by Plato View Post
    That is most likely the same problem I had with my computer algebra system.
    Excel is not a symbolic algebra system.
    Wolfram|alpha is.
    Ask it to factor that number.
    Okay, thanks.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by chickeneaterguy View Post
    hey...I have this spreadsheet as I did mine through excel. Can someone explain to me(or maybe just look) at what's wrong with this since I'm not getting 71 as an answer?
    Confirming what Plato said, when I highlighted the cell with C(71,35) and changed the number format to remove scientific notation, I got

    221256270138418000000

    instead of

    221256270138418389602

    So it is a precision issue.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Feb 2010
    Posts
    56
    Quote Originally Posted by undefined View Post
    Confirming what Plato said, when I highlighted the cell with C(71,35) and changed the number format to remove scientific notation, I got

    221256270138418000000

    instead of

    221256270138418389602

    So it is a precision issue.
    Okay, quite apparent now. thanks
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Feb 2010
    Posts
    56
    EDIT: nvm
    Last edited by chickeneaterguy; May 4th 2010 at 06:29 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Help with tough Combinations Question
    Posted in the Statistics Forum
    Replies: 5
    Last Post: October 7th 2009, 02:49 PM
  2. [SOLVED] tough limit problem.
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: May 12th 2009, 05:19 AM
  3. [SOLVED] credit card combinations problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 23rd 2009, 05:22 PM
  4. [SOLVED] Permutations and Combinations problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 13th 2009, 04:13 AM
  5. [SOLVED] two (tough?) limit proofs
    Posted in the Calculus Forum
    Replies: 1
    Last Post: March 13th 2008, 01:11 PM

Search Tags


/mathhelpforum @mathhelpforum