[SOLVED] Tough Combinations Problem

**chickeneaterguy** · May 4th 2010, 12:11 PM

EDIT: solved.

**undefined** · May 4th 2010, 02:16 PM

Originally Posted by chickeneaterguy

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.

**chickeneaterguy** · May 4th 2010, 02:18 PM

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.

**undefined** · May 4th 2010, 03:00 PM

Originally Posted by chickeneaterguy

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.

**Plato** · May 4th 2010, 03:12 PM

Originally Posted by undefined

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.

**chickeneaterguy** · May 4th 2010, 03:16 PM

C(71, 35) = 221256270138418389602

C(71,35) - Wolfram|Alpha

Confused...

**gmatt** · May 4th 2010, 03:28 PM

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.

**Plato** · May 4th 2010, 03:31 PM

Originally Posted by chickeneaterguy

C(71, 35) = 221256270138418389602

C(71,35) - Wolfram|Alpha

Confused...

You are correct. And 71 does work.
I did not set my CAS correctly.

**chickeneaterguy** · May 4th 2010, 03:44 PM

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?

**Plato** · May 4th 2010, 04:07 PM

Originally Posted by chickeneaterguy

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.

**chickeneaterguy** · May 4th 2010, 04:13 PM

Originally Posted by Plato

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.

**undefined** · May 4th 2010, 04:17 PM

Originally Posted by chickeneaterguy

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.

**chickeneaterguy** · May 4th 2010, 04:23 PM

Originally Posted by undefined

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

**chickeneaterguy** · May 4th 2010, 05:41 PM

EDIT: nvm

Thread: [SOLVED] Tough Combinations Problem

LinkBack

Thread Tools

Display

[SOLVED] Tough Combinations Problem

Similar Math Help Forum Discussions

[SOLVED] Help with tough Combinations Question

[SOLVED] tough limit problem.

[SOLVED] credit card combinations problem

[SOLVED] Permutations and Combinations problem

[SOLVED] two (tough?) limit proofs

Search Tags