Calvinball!

Update: Now that everyone has had time to work on this problem by themselves, let's open up the floodgates and post your solution as a reply (or edit) to your comment. Let's see how many different ways the creative brains at Brilliant can approach this problem.


The following problem is a slight variant of Score!. Keep your answers to yourself, and only post how long (in minutes) it took you to do this problem.


In Calvinball, a player can score points in 3 different ways: 1 point for hitting your opponent with the ball, 5 points for capturing the flag, and 13 points for hitting Susie with the ball.

If Hobbes scored 3121 points in a game, how many different ways can this be achieved?
The order of the points scored doesn't matter, just the ways in which it is scored.

#Combinatorics #MathProblem #Math

Note by Calvin Lin
7 years, 6 months ago

No vote yet
28 votes

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Update: Now that everyone has had time to work on this problem by themselves, let's open up the floodgates and post your solution as a reply (or edit) to your comment. Let's see how many different ways the creative brains at Brilliant can approach this problem.

Calvin Lin Staff - 7 years, 6 months ago

Log in to reply

Done :D

jatin yadav - 7 years, 6 months ago

I used the Pick's Theorem, which states that in a Cartesian plane: P(A)=i+b21P(A) = i + \frac{b}{2} -1, where P(A)P(A) represents the area of the polygon, ii represents the number of interior points in the polygon and bb represents the number of boundary points.

First, notice that the 11 pointer is determined by the number of 55 and 1313 pointers. Then, I let there be xx 13-pointers and yy 5-pointers Then, draw lines x=0x=0 and y=0y=0 to form a triangle. The maximum number of 1313 pointers is 240240, while the max. number of 55 pointers is 624624, hence, the vertices of the triangle are (240,0)(240,0) and (0,624)(0,624). [ The triangle is formed by drawing a best-fit line connecting(240,0)(240,0) and (0,624)(0,624)]. See here that b+ib+i equal to the number of (x,y)(x,y) that satisfies our question. [plus some exceptions as we see later]

Here, we can easily derive the number of points lying on our best-fit line, which has a gradient of 135\frac{13}{5}. Notice that every xx-coordinate which is a multiple of 55 lies on the best-fit line. Hence, there are 2405=48\frac{240}{5}=48 points lying on the best-fit line [not counting the point (0,624)(0,624). Then, b=48+624+240=912b = 48 + 624 + 240 = 912.

Next, the area of the triangle is simply 12baseheight=12624240=74880\frac{1}{2} \cdot base \cdot height = \frac{1}{2}\cdot 624\cdot 240 = 74880

Fitting the values of b=912b=912 and P(A)=74880P(A) = 74880 into Pick's theorem, we will get: 74880=i+9122174880 = i + \frac{912}{2} -1 Here, it is clear that i=74425i = 74425. So, b+i=75337b+i = 75337. But we're not done yet!

As mentioned earlier, we still have to add some exceptions! Notice that NOT ALL of the points (x,y)(x,y) is under the best-fit line! Some of them are above the line but still fulfills the conditions, and the Picks' Theorem fails to consider these points because they are not within the triangle.

Notice that the points with xx-coordinates 22 more than the xx-coordinates of the point on the best-fit line has gradient more than 135\frac{13}{5}, which means they lie outside the triangle. For example, since (0,624)(0,624) lies on the lie, (2,619)(2,619) is above the line. (you can check it out) Since the cycle repeats itself in multiples of 55, this is true for all points lying on the best-fit line. Since there are 4848 points (not including (240,0)(240,0) as it is the maximum number of 1313 pointers) on the best-fit line, there will be 4848 points that lie above the best-fit line that satisfies the question.

Hence, answer is 75337+48=7538575337 + 48 = \boxed{75385}.

P.S. Sigh... This is very tedious I think... Anyone has ideas to shorten this method?

Happy Melodies - 7 years, 6 months ago

Log in to reply

Great!

This is the approach that I would have used. The main disturbance is that the shape isn't easily dealt with. The problem is much easier if the total number of points is 65n 65n, in which case we are looking at the triangle with vertices (0,0),(5n,0),(0,13n) (0,0), (5n, 0), (0, 13n) . We could use this triangle, to account for the points from 0 to 48×65=3120 48 \times 65 = 3120, and separately deal with getting exactly 3121 points using the floor method presented in other solutions. (And yes, 3121 was specially chosen)

The point is that when you learn a good method (the bijection to lattice points and Pick's Theorem), you shouldn't forget the elementary methods that you initially used (slowly counting according to cases). At times, the best approaches uses a combination of both methods. This is similar to coding, where you use a sledgehammer for most of the cases, and then deal with the edge cases with other tools.

Calvin Lin Staff - 7 years, 6 months ago

Very innovative solution! Kudos to you.

Daniel Liu - 7 years, 6 months ago

Log in to reply

Thank you! Oh, I have got the idea from Score!

Happy Melodies - 7 years, 6 months ago

This is the most elegant approach submitted till now! :)

Sreejato Bhattacharya - 7 years, 6 months ago

Log in to reply

Thank you!

Happy Melodies - 7 years, 6 months ago

Here's my solution:

The number of ways to score 31213121 is essentially the number of non-negative integral solutions to the Diophantine equation a+5b+13c=3121a + 5b + 13c= 3121. We note that any valid choice of (b,c)(b, c) determines a unique non-negative aa, so we can simply afford to find the number of solutions to 5b+13c31215b+13c \leq 3121. Rearranging this gives b312113c5b \leq \frac{3121-13c}{5} The number of solutions of bb for a fixed cc, thus, is 312113c5+1\left \lfloor \dfrac{3121-13c}{5} \right \rfloor + 1 . We need to sum this up from c=0c=0 to c=312113=240c= \left \lfloor \dfrac{3121}{13} \right \rfloor = 240 , which gives our desired answer: c=0240(312113c5+1)=75385\sum \limits_{c=0}^{240} \left ( \left \lfloor \frac{3121-13c}{5} \right \rfloor + 1 \right ) = \boxed{75385}

Sreejato Bhattacharya - 7 years, 6 months ago

Log in to reply

Hey,you have stolen my solution! just kidding,mine is the same. :D

Kishan k - 7 years, 6 months ago

Does order matter?

Sreejato Bhattacharya - 7 years, 6 months ago

Log in to reply

Nope, just added that in.

Calvin Lin Staff - 7 years, 6 months ago

In your status X could be any number from 0 to 999.

Tan Li Xuan - 7 years, 6 months ago

Log in to reply

Did you really expect me to give a hint to a live challenge?

Sreejato Bhattacharya - 7 years, 6 months ago

About 40 mins, Without revealing too much, is there a faster way to perform discrete integration to find the number of points within an section of the cartesian plane?

Jamie Coombes - 7 years, 6 months ago

Log in to reply

I'll post a more complete solution later but a rough outline runs as follows:

Same as Sreejato's up to 13x+5y<=312113x+5y <= 3121 then I graphed this inequality in the xy plane. Finding the root, y intercept etc. (624.2,0) (0,240+1/13)

If this problem is continuous, then I'd integrate the area between the line 13x+5y=3121 and x=0, but since it's discrete, we find the number of points beneath the line.

I broke the area into smaller rectangles and triangles, each triangle is 13*5 and contains 37 points. The rectangles look like the right Riemann Sum, they have a length of (624-k) and width 5. There are 48 triangles atop 48 rectangles. We get something like k=1485×(624k)\sum_{k=1}^{48}5 \times (624-k) for the rectangles, and 37×4837 \times 48 for the triangles.

Total number of points = number of points in triangles + number of points in rectangles. I'll check the numbers properly later.

Jamie Coombes - 7 years, 6 months ago

Log in to reply

To find the number of integer points, we use Pick's Theorem.

Sadly, there is no higher dimension analogue of Pick's Theorem (in it's simplicity).

Calvin Lin Staff - 7 years, 6 months ago

I have the feeling that I shouldn't have listed them all out... 2 hours, though. Hehe...

Finn Hulse - 7 years, 6 months ago

Log in to reply

Ohhhh... I just re-did it. Actually very simple! (kind of). It's a pretty awesome problem.

Finn Hulse - 7 years, 6 months ago

Not sure if I did correctly... applied the method I have learnt from Score!... Took around 6.5mins...

Happy Melodies - 7 years, 6 months ago

It's simple... Its not very lengthy and tedious.So can we all share our solutions?

Kishan k - 7 years, 6 months ago

Log in to reply

Maybe... Not sure if everyone has seen this discussion though... they may want to solve the question too...

Happy Melodies - 7 years, 6 months ago

Well, i guess it could have been made much better if the possible points were 2,52, 5 and 1313, now, since most of people have seen this post , are we allowed to post our solutions.

_Edit - _ Here is how i did:

Say we have aa number of 13- pointers, bb number of 5- pointers and cc number of q-pointers.

For a given aa,

5b+c=312113a5b + c = 3121 - 13a,

Every value of bb gives one way, and bb varies from 00 to 312113a5\lfloor \frac{3121 - 13a}{5} \rfloor

Also , no. of ways for a given aa is 312113a5+1\bigg\lfloor \frac{3121 - 13a}{5} \bigg\rfloor + 1, and aa varies from 00 to 240240

Hence, total required number of ways = a=0240(312113a5+1)\displaystyle \sum_{a=0}^{240} \Big(\bigg \lfloor \frac{3121 - 13a}{5} \bigg \rfloor + 1\Big)

= 75385\fbox{75385}

jatin yadav - 7 years, 6 months ago

Log in to reply

Hi Jatin!

Can you please explain the following?

Also , no. of ways for a given aa is 312113a5+1\bigg\lfloor \frac{3121 - 13a}{5} \bigg\rfloor + 1, and aa varies from 00 to 240240

Thanks!

Pranav Arora - 7 years, 6 months ago

Log in to reply

Clearly, maximum value of aa would be 240240 when, b=0,c=1b=0, c=1

Also, 5b+c=312113a5b + c = 3121 - 13a, Hence, max. value of bb will be obviously312113a5\bigg\lfloor \frac{3121-13a}{5} \bigg \rfloor, and hence b can be 0,1,2,312113a50,1,2, \dots \bigg\lfloor \frac{3121-13a}{5} \bigg \rfloor, and hence a total of 312113a5 +1\bigg\lfloor \frac{3121-13a}{5} \bigg \rfloor\ + 1 values of bb are possibe.

jatin yadav - 7 years, 6 months ago

Log in to reply

@Jatin Yadav You have made a couple of misprints at the end. The maximum value of bb for a fixed aa is 312113a5\left \lfloor \dfrac{3121-13a}{5} \right \rfloor , not 31215a5\left \lfloor \dfrac{3121-5a}{5} \right \rfloor (that was a typo, I guess :) ).

Sreejato Bhattacharya - 7 years, 6 months ago

Log in to reply

@Sreejato Bhattacharya Yes,indeed, it was, edited. Thanks.

jatin yadav - 7 years, 6 months ago

@Jatin Yadav Thanks Jatin! I think I understand it now. :)

Pranav Arora - 7 years, 6 months ago

However, in calvinball, the rules can be changed .....on the spot...

Daniel Wang - 7 years, 6 months ago

Log in to reply

But only by Calvin and Hobbes, and you are neither.

Calvin Lin Staff - 7 years, 6 months ago

Log in to reply

Rosalyn made a rule change throwing the water balloon at Calvin

William Wang - 7 years, 6 months ago

Can I use a computer to calculate it? I found out how to find the answer, just can't calculate it by hand. :\

EDIT: oh yea, almost forgot. Took 4 minutes to find how to get the answer. Writing a computer program to find the actual numerical answer right now.

Daniel Liu - 7 years, 6 months ago

Log in to reply

The point is to figure it out mathematically, not to use a computer program.

Ahaan Rungta - 7 years, 6 months ago

Around 4 minutes.I'm not sure I got the right answer though.

Tan Li Xuan - 7 years, 6 months ago

About 6 minutes, but I had to use a calculator at the end.

Sean Elliott - 7 years, 6 months ago

Around 11 minutes.

Shendy Marcello Yuniar - 7 years, 6 months ago

Log in to reply

...and I got it wrong.

Shendy Marcello Yuniar - 7 years, 6 months ago

It took not more than 9-10 minutes. I'd developed the logic only in few seconds but manually computing the final value (which was a tedious task) took the whole time.

Kishlaya Jaiswal - 7 years, 6 months ago

About 7-8 min.

Nitin Jain - 7 years, 6 months ago

it took me 10 minutes, but it was simple

ayush chowdhury - 7 years, 6 months ago

Took 13 minutes.

Bhargav Das - 7 years, 6 months ago

4 minutes.but my ans is not within the range [0,999] :/

Adeeb Zaman - 7 years, 6 months ago

Log in to reply

The correct answer is not in that range.

Ahaan Rungta - 7 years, 6 months ago

Log in to reply

Yup :)

Adeeb Zaman - 7 years, 6 months ago

Can you explain how you did the calculations in 4 minutes?

Calvin Lin Staff - 7 years, 6 months ago

Log in to reply

Sir, I first formed the diophantine equation x+5y+13z=3121. From the experience of the similar problem named 'score', I discarded x from the equation and all I had to calculate was the number of integer solutions of the inequality 5y+13z<=3121. I used a c program to find it. In case of 'score', computer program was not needed though. But seeing others solution, I feel that using computer programming was not an encouraging idea. I didnt have any idea about pick's theorem before and it was a very nice opportunity for me to learn the theorem :)

Adeeb Zaman - 7 years, 6 months ago

I also got not on that range so.. how next?

Hafizh Ahsan Permana - 7 years, 6 months ago

Log in to reply

As mentioned by Ahaan R., the answer is not restricted to the range. It can be any number.

Happy Melodies - 7 years, 6 months ago
×

Problem Loading...

Note Loading...

Set Loading...