EDIT: solved.

Printable View

- May 4th 2010, 12:11 PMchickeneaterguy[SOLVED] Tough Combinations Problem
EDIT: solved.

- May 4th 2010, 02:16 PMundefined
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 $\displaystyle \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 $\displaystyle k_1=\lfloor n/2 \rfloor$ and $\displaystyle k_2=\lceil n/2 \rceil$.

We can consider each prime power $\displaystyle p^\alpha$ separately, in which case we are comparing the quantities $\displaystyle \bigg\lfloor \frac{n}{p^\alpha} \bigg\rfloor$ and $\displaystyle \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. - May 4th 2010, 02:18 PMchickeneaterguy
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.

- May 4th 2010, 03:00 PMundefined
- May 4th 2010, 03:12 PMPlato
- May 4th 2010, 03:16 PMchickeneaterguy
C(71, 35) = 221256270138418389602

C(71,35) - Wolfram|Alpha

Confused...(Wondering) - May 4th 2010, 03:28 PMgmatt
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.

- May 4th 2010, 03:31 PMPlato
- May 4th 2010, 03:44 PMchickeneaterguy
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?

- May 4th 2010, 04:07 PMPlato
- May 4th 2010, 04:13 PMchickeneaterguy
- May 4th 2010, 04:17 PMundefined
- May 4th 2010, 04:23 PMchickeneaterguy
- May 4th 2010, 05:41 PMchickeneaterguy
EDIT: nvm