3

My son (a third grader) was given this problem to solve. Is states that:

In a basketball game, one of the teams scored 67 points. If baskets can be worth 1 point for a free throw, 2 points for a field shot or 3 points for a 3 pointer, how did the team reach 67 points? How can you know that you have found all possibilities.

We can easily start out by doing 1 x 67 times, and then adding a 2 into the mix until we had mostly 2 and then starting with 3 and rounding that pattern back to introducing 1. We got up to 77 possible combinations when applying this simple pattern based solution. But that doesn't account for all the other combinations where any of the 3 numbers could be used which still equal 67.

It seems stars and bars may be a good way to deal with this problem, but I'm unclear on how to apply it. Would anyone be able to explain this? I'm not looking for the answer, but keen to understand how to calculate how many combinations there could be for any 3 sets of numbers to equal any given number.

Much appreciated!

John Car
  • 31
  • 1
    There are lots of ways of doing this, some more technical than others, and there are more details that affect the answer: in particular does order matter? For example would one free throw followed by $33$ two-pointers count as the same as $33$ two-pointers followed by one free-throw? – Henry Mar 04 '21 at 22:24
  • I do not believe the order in which the points occur matter (in this case). So it wouldn't matter if that one free throw happened before or after the 33 two pointers. Just as long as that particular instance was counted. – John Car Mar 04 '21 at 22:36
  • Were the students truly meant to solve this? Or were they just meant to play with it a bit, maybe solve it for a more manageable number? – lulu Mar 04 '21 at 22:58
  • What I'd do: for $a\in {0,22}$ I'd consider having $a$ $3's$. Then you are left with writing $67-3a=2b+c$ for suitable $b,c$. There are $1+\big \lfloor \frac {67-3a}2\big \rfloor$ ways to do that, so now you just have to sum (Note: check that. it's a bit error prone). Then sum over $a$. Easy enough in one sense. I would not, however, expect any third grader to do it. – lulu Mar 04 '21 at 23:01
  • Note; the method I just sketched gives $408$, I also did it with generating functions (presumably not the intended method) to confirm $408$ as the result. – lulu Mar 04 '21 at 23:07
  • @ lulu. As third graders (7-8 year olds), I doubt they were meant to solve it entirely. Simply trying to engage them and see how they might start. As a parent, I want to be able to understand how it should be done. If i'm not clear in explaining it, I'm just going to confuse the situation even more. – John Car Mar 04 '21 at 23:08
  • Well, I sure wouldn't mention generating functions. I just did it that way to confirm the answer I got with the method I sketched earlier. – lulu Mar 04 '21 at 23:09
  • Should say: I think it is a better question if order does matter. Wouldn't surprise me if kids could spot the recursion, $a_n=a_{n-1}+a_{n-2}+a_{n-3}$. Of course the numbers grow too fast to be sensible, but maybe that's part of the point. Had they just been talking about Fibonacci numbers by any chance? If so, this is a natural next step. – lulu Mar 04 '21 at 23:11
  • We started by dealing with it as a pattern, which is something I know they deal with a lot at this age. But after that we were both stuck lol. I wish I understood your solution. I'm feeling as lost as a primary student with it. Wondering how in the world I'd write a formula in Excel to make such calculations and then altering the number of variable (like adding a fourth point) and a different total score just to test the method. https://docs.google.com/spreadsheets/d/1aDorJNobCmJXCOXTqE_2yU3O_CbnAbFcvF7WDo-b3gQ/edit?usp=sharing – John Car Mar 04 '21 at 23:17
  • In Excel: create a column for the $a's$, from $0$ to $22$. Then create a column next to it containing $67-3a$. Then a column next to that containing $1+\big \lfloor \frac{67-3a}{2}\big \rfloor$. If $B$ is the column containing $67-3A$ then the syntax you want is "C[i]=Floor(B[i]/2,1)+1" Then sum the entries in that column. – lulu Mar 04 '21 at 23:20
  • Note: there's nothing weird about that formula. If $a=1$, say, then $67-3a=64$. We know then that the number of $1's$ must be even (why?). Hence it is any one of ${0,2, 4 \cdots, 64}$ so there are $33$ possible patterns with $a=1$. That's all. – lulu Mar 04 '21 at 23:22

2 Answers2

1

To summarize part of the discussion in the comments:

Personally, I think it is more tractable if the order does matter. In that case we can work recursively. Letting $a_n$ denote the answer with a total of $n$ we remark that, for $n>3$, we must have $$a_n=a_{n-1}+a_{n-2}+a_{n-3}$$ since the last score must be one of $1,2$ or $3$. This resembles one standard interpretation of the Fibonacci numbers, where $F_n$ is defined as the number of ways to get a sum of $n$ using an ordered sequence of $1's$ and $2's$. That is to say, the same problem only without the $3$ point shot.

That recursion is easily implemented in Excel, or whatever (you'll have to work out $a_1, a_2, a_3$ but that is not hard). Of course, the terms grow very rapidly.

If order does not matter:

Then we are counting triples of non-negative integers $(a,b,c)$ with $3a+2b+c=67$. We remark that $a\in \{0,\cdots, 22\}$. For a fixed $a$ we are now trying to write $67-3a$ as $2b+c$. How many ways are there for that? Well, since $67-3a-c$ is even we can work out the parity of $c$ from that of $a$. Indeed, they must have opposite parities. It follows that the number of possible $c's$ is given by $$1+\Big \lfloor \frac{67-3a}2\Big \rfloor$$

Note: I suggest that out by hand for several values of $a$ to convince yourself that it is correct.

That gives us the number of good triples for a fixed value $a$. We get the answer by summing $$\sum_{a=0}^{22} \left(1+\Big \lfloor \frac{67-3a}2\Big \rfloor\right)=408$$

Should say, that is all a bit error prone. To check, I did the computation using generating functions, here which confirms the result. (you can read off the coefficient of $x^{67}$ is $408$ If you are not used to Wolfram Alpha, you need to click "more terms" often enough to get to $x^{67}$). Obviously that's not a useful method given the context, but I thought it was worth checking the result.

lulu
  • 70,402
0

Here's an start (assuming order doesn’t matter).

Imagine that you want to know how many ways there are to buy a $67 candy bar from a vending machine that only accepts \$3, \$2, and \$1 coins. Since order doesn’t matter, you can count the ways you can pay using \$3 coins first, then \$2, then \$1 coins. (It’s the same problem, but sometimes making a problem involve money makes it easier to think about.)

You can use anywhere from $0$ and $22$ \$3 coins. If you use, say, exactly $7$ \$3 coins, then you have to pay the remaining \$67 - \$21 = \$46 dollars with \$2 and \$1 coins. You can do this using $0$, $1$, $2$, ... or $23$ \$2 coins (and the rest \$1 coins), for $24$ possible ways.

Can you figure out how many ways there are to finish paying after using a given number of \$3 coins, say $c$ of them (not necessarily $7$), and then (by hand is fine) add up your answers for $c=0$ through $c=22$?

Steve Kass
  • 14,881
  • We basically applied that approach when we started looking into it. We colour coded the values since we were dealing with it as a pattern. As you say, finding how many of the 1, 2 or 3 values could be used in total (and then adding any additional values to bring it to the correct total. That looked like this: https://docs.google.com/spreadsheets/d/1aDorJNobCmJXCOXTqE_2yU3O_CbnAbFcvF7WDo-b3gQ/edit?usp=sharing – John Car Mar 04 '21 at 23:01
  • You'll see column A has all the 1s, AH has all the 2s and BD has all the 3s. And then it staggers back to the 1s to make it loop around. But would we clearly calculate all the other possibilities that aren't as pattern driven? – John Car Mar 04 '21 at 23:04
  • Well, it's pattern-driven, but not in a way that fits on a two-dimensional spreadsheet. Note that column AI and column BY both have one $3$, but they only show the most extreme choices of how many $2$s and $1$s (In AI, $3+32\times2$, and in BY, $3+64\times1$). Imagine all the other possibilities ($3+31\times2+2\times1,3+30\times2+4\times1$, etc.) with one $3$ connecting those extremes in a big semicircular sheet behind the main spreadsheet. Then connect AJ and BX with a smaller concentric sheet, and so on. It's not hard to count how many columns each of the concentric semicircles includes. – Steve Kass Mar 05 '21 at 01:45