## Tricky Counting Problem, any ideas?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

bieber
Posts: 223
Joined: Thu Mar 13, 2008 12:13 am UTC

### Tricky Counting Problem, any ideas?

So I have a two part problem, the first part of which is simple, and the second part I can't figure out. The situation is 15 toothpicks lined up next to each other, and the first part of the problem asks how many combinations of five toothpicks you can make: this is obviously C(15, 5). The problem is, the second part asks how many combinations that don't use any toothpicks next to each other. I'm sure there must be a relatively simple way to do this, but I can't find it. I've considered numbering the toothpicks and then dividing it up into cases depending on how many even and odd numbered toothpicks are in the combination, but the problem is that for anything but all even or all odd cases, the cases end up more or less impossible to compute, as once you've chosen the number of even or odd toothpicks, the number of choices for the other way depends on which ones you chose in the first step. Anyone see what I'm missing?

Charlie!
Posts: 2035
Joined: Sat Jan 12, 2008 8:20 pm UTC

### Re: Tricky Counting Problem, any ideas?

Wait, what do you mean combinations of five toothpicks for the first part? Unordered, right, since you use the choose function? Okay

Huh, that second part is hard. It looks like you have to find places to put gaps, essentially, and the gaps have to total some number (in the 15 and 5 case you have 6 gaps to distribute into the minimum pattern |.|.|.|.| ). Hmm. So so the answer may even be as simple as a choose operation, where you just need to put your gaps into however many spots you've got to stick gaps in (hint: how many spots for gaps must there be between each toothpick?). I'll let you work out the last part on your own, assuming my reasoning is fairly correct.

Of course, I might be wrong. Counting is tricky that way
Some people tell me I laugh too much. To them I say, "ha ha ha!"

bieber
Posts: 223
Joined: Thu Mar 13, 2008 12:13 am UTC

### Re: Tricky Counting Problem, any ideas?

Charlie! wrote:Wait, what do you mean combinations of five toothpicks for the first part? Unordered, right, since you use the choose function? Okay

Huh, that second part is hard. It looks like you have to find places to put gaps, essentially, and the gaps have to total some number (in the 15 and 5 case you have 6 gaps to distribute into the minimum pattern |.|.|.|.| ). Hmm. So so the answer may even be as simple as a choose operation, where you just need to put your gaps into however many spots you've got to stick gaps in (hint: how many spots for gaps must there be between each toothpick?). I'll let you work out the last part on your own, assuming my reasoning is fairly correct.

Of course, I might be wrong. Counting is tricky that way

Ohhhhhhh, that's right! If I look at it as choosing places to put gaps, then it becomes a balls-into-bins problem. Hopefully this'll get me somewhere...

Edit - Okay, so I've rephrased the original problem into distributing 10 gaps (or unchosen toothpicks) among fifteen spaces (10 balls into 15 bins), but I'm still not sure how to modify it to require a space between every toothpick

Edit again - Nevermind, I just treat the toothpicks as dividers (or 1s in a binary string), dividing the non-chosen toothpicks into six categories (ten balls into six bins) and then add the constraint that every group except the first and last must have at least one ball in it (or one separator toothpick). This _should_ yield the right answer, when I finish working it out

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

### Re: Tricky Counting Problem, any ideas?

Yeah, that's basically it. Put more simply, think of the five chosen toothpicks as dividers, then put four unchosen toothpicks into the middle bins (one in each). How many ways can you put the other 6 toothpicks into 6 bins?

(There's actually an even easier way to do this. Once you follow the above calculation the easier method will probably jump out at you, but I'm not sure how to hint at it without just giving everything away.)

bieber
Posts: 223
Joined: Thu Mar 13, 2008 12:13 am UTC

### Re: Tricky Counting Problem, any ideas?

Well, I got the answer (or at least I did if the answer is 462) by turning it into x1+x2+x3+x4+x5+x6=10, where x2-x5>=1, which turned into 6 balls into 6 bins, which was C(11,5). Now that I've got it, if you have a simpler way, feel free to throw it at me

lgonick
Posts: 17
Joined: Sun Jun 22, 2008 2:48 pm UTC

### Re: Tricky Counting Problem, any ideas?

How about finding the number of combinations in which some pair is next to each other, and subtracting from the total?

Corosis
Posts: 1
Joined: Wed Mar 12, 2008 9:42 am UTC

### Re: Tricky Counting Problem, any ideas?

Similar question, another counting problem. I didn't think it warranted a new topic.
In the spirit of Halloween we will be giving the children fruit!
In how many ways can 10 oranges, 6 apples, and 4 peaches be distributed to 3 children if each kid must receive at least 1 piece of fruit?

bieber
Posts: 223
Joined: Thu Mar 13, 2008 12:13 am UTC

### Re: Tricky Counting Problem, any ideas?

Corosis wrote:Similar question, another counting problem. I didn't think it warranted a new topic.
In the spirit of Halloween we will be giving the children fruit!
In how many ways can 10 oranges, 6 apples, and 4 peaches be distributed to 3 children if each kid must receive at least 1 piece of fruit?

Think of it as arranging balls into bins. Start with the oranges, dividing 10 balls (oranges) into 3 bins (children), with at least one ball in each bin: how many ways are there to accomplish this? Then do 6 balls into 3 bins, and 4 into 3, and multiply the steps together (when you do things in steps, you multiply them, per the product rule).

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Tricky Counting Problem, any ideas?

bieber wrote:
Corosis wrote:Similar question, another counting problem. I didn't think it warranted a new topic.
In the spirit of Halloween we will be giving the children fruit!
In how many ways can 10 oranges, 6 apples, and 4 peaches be distributed to 3 children if each kid must receive at least 1 piece of fruit?

Think of it as arranging balls into bins. Start with the oranges, dividing 10 balls (oranges) into 3 bins (children), with at least one ball in each bin: how many ways are there to accomplish this? Then do 6 balls into 3 bins, and 4 into 3, and multiply the steps together (when you do things in steps, you multiply them, per the product rule).

But you are assuming each kid gets at least one orange (or maybe even at least one of each fruit - you didn't say).
I'd do just as you said, but without the 'at least one' restriction. Then use the inclusion/exclusion principle to toss out all cases where one or more of the children didn't get any pieces of fruit.

bieber
Posts: 223
Joined: Thu Mar 13, 2008 12:13 am UTC

### Re: Tricky Counting Problem, any ideas?

jaap wrote:
bieber wrote:
Corosis wrote:Similar question, another counting problem. I didn't think it warranted a new topic.
In the spirit of Halloween we will be giving the children fruit!
In how many ways can 10 oranges, 6 apples, and 4 peaches be distributed to 3 children if each kid must receive at least 1 piece of fruit?

Think of it as arranging balls into bins. Start with the oranges, dividing 10 balls (oranges) into 3 bins (children), with at least one ball in each bin: how many ways are there to accomplish this? Then do 6 balls into 3 bins, and 4 into 3, and multiply the steps together (when you do things in steps, you multiply them, per the product rule).

But you are assuming each kid gets at least one orange (or maybe even at least one of each fruit - you didn't say).
I'd do just as you said, but without the 'at least one' restriction. Then use the inclusion/exclusion principle to toss out all cases where one or more of the children didn't get any pieces of fruit.

You could do that, but starting with a ball in each bin would have the same effect. Different strokes...

eMan2718281828
Posts: 16
Joined: Tue Jul 10, 2007 6:51 pm UTC
Location: Raleigh, NC

### Re: Tricky Counting Problem, any ideas?

Guys, I think it's simpler than you're making it. Check this out.

I think the answer is just 11C4 = 330. The reason?

Imagine choosing 5 out of 11 with no restrictions. Then, just put one more toothpick between each set of consecutive toothpicks. That is, if I choose these 5 out of 11 (x's are the ones I chose):

x|x||xx||x|

Then I add 4 more toothpicks, one between each of my chosen picks, and my corresponding selection with 15 toothpicks would be

x||x|||x|x|||x|

Note that each selection of 5 out of 11 corresponds to exactly one acceptable selection of 5 out of 15, and that each valid selection of 5 out of 15 will correspond to exactly one free selection of 5 out of 11. The sets thus have the same size, and so there are 11C4 = 330 ways to choose 5 toothpicks from a row of 15 such that no two consecutive toothpicks are chosen.

The end.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

### Re: Tricky Counting Problem, any ideas?

bieber wrote:You could do that, but starting with a ball in each bin would have the same effect. Different strokes...

Under normal circumstances, I'd agree with you. But what ball should each bins start with? Should it be an orange? Because the problem doesn't specify that each kid gets at least one orange, just that each kid gets at least one piece of fruit. Should we divide into cases, starting each of the three kids with each of the three fruits? Then we'd be double-counting cases where kids get more than one type of fruit.

Overall, I think the inclusion/exclusion thing is going to work pretty well, much better in this convoluted problem than any sort of "start them off with a fruit" approach. In fact, I can already write down the answer: it's (12 C 2)(8 C 2)(6 C 2) - 3(11 C 1)(7 C 1)(5 C 1) + 3(10 C 0)(6 C 0)(4 C 0) - 0 = 66*28*15 - 3*11*7*5 + 3 = 26568.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.