Combinatorics - AMC 10A 2008 Problem 23 Sequential Hints

[et_pb_section fb_built="1" _builder_version="4.0"][et_pb_row _builder_version="3.25"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||"][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Understand the problem

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway||||||||" background_color="#f4f4f4" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" box_shadow_style="preset2"]Two subsets of the set $S=\lbrace a,b,c,d,e\rbrace$ are to be chosen so that their union is $S$ and their intersection contains exactly two elements. In how many ways can this be done, assuming that the order in which the subsets are chosen does not matter? $\mathrm{(A)}\ 20\qquad\mathrm{(B)}\ 40\qquad\mathrm{(C)}\ 60\qquad\mathrm{(D)}\ 160\qquad\mathrm{(E)}\ 320$

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row _builder_version="4.0"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||"][et_pb_accordion open_toggle_text_color="#0c71c3" _builder_version="4.0" toggle_font="||||||||" body_font="Raleway||||||||" text_orientation="center" custom_margin="10px||10px"][et_pb_accordion_item title="Source of the problem" _builder_version="4.0" open="on"]American Mathematics Competition [/et_pb_accordion_item][et_pb_accordion_item title="Topic" _builder_version="4.0" open="off"]

Combinatorics

[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" open="off" _builder_version="4.0"]

7/10

[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" _builder_version="3.29.2" open="off"]

Enumetarive Combinatorics - ( Problem Solving Strategies ) by Arthur Engel

[/et_pb_accordion_item][/et_pb_accordion][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="48px||117px|||" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Start with hints

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="-14px||48px|||" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Watch video

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" min_height="12px" custom_margin="50px||50px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Connected Program at Cheenta

[/et_pb_text][et_pb_tabs active_tab_background_color="#0c71c3" inactive_tab_background_color="#000000" _builder_version="4.0" tab_text_color="#ffffff" tab_font="||||||||" background_color="#ffffff" custom_padding="||153px|25px||"][et_pb_tab title="Hint 0" _builder_version="3.22.4"]You could give it a thought first...are you sure you really need a hint ?

[/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="4.0"]

First can you try finding the number of ways in which we can choose the 2 shared elements ? That would be 5C2 = 10 ways. Can you try completing this ?

[/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="4.0"]

All that remains now is to place the remaining 3 elements into the subsets. In how many ways can we do this ?

[/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="4.0"]

So basically, if we think about it a little, it is equivalent to the problem of placing 3 elements in 4 gaps. Evidently, this can be done in 4C3 = 4 ways. Now, it's pretty easy to arrive at the answer...could you do it by yourself ?

[/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="4.0"]

The final answer can be easily found out using the Multiplication Principle, which leads us to... 4 x 10 = 40 ways

And, we are done !

[/et_pb_tab][/et_pb_tabs][et_pb_blurb title="Math Olympiad Program" url="https://cheenta.com/matholympiad/" url_new_window="on" image="https://cheenta.com/wp-content/uploads/2018/03/matholympiad.png" _builder_version="3.23.3" header_font="||||||||" header_text_color="#e02b20" header_font_size="48px" link_option_url="https://cheenta.com/matholympiad/" link_option_url_new_window="on"]

Math Olympiad is the greatest and most challenging academic contest for school students. Brilliant school students from over 100 countries participate in it every year. Cheenta works with small groups of gifted students through an intense training program. It is a deeply personalized journey toward intellectual prowess and technical sophistication.[/et_pb_blurb][et_pb_button button_url="https://cheenta.com/matholympiad/" url_new_window="on" button_text="Learn More" button_alignment="center" _builder_version="3.23.3" custom_button="on" button_bg_color="#0c71c3" button_border_color="#0c71c3" button_border_radius="0px" button_font="Raleway||||||||" button_icon="%%3%%" background_layout="dark" button_text_shadow_style="preset1" box_shadow_style="preset1" box_shadow_color="#0c71c3"][/et_pb_button][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="50px||50px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Number Theory - AMC 10A 2013 Problem 21 Sequential Hints

Understand the problem

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway||||||||" background_color="#f4f4f4" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" box_shadow_style="preset2"]A group of $12$ pirates agree to divide a treasure chest of gold coins among themselves as follows. The $k^{\text{th}}$ pirate to take a share takes $\frac{k}{12}$ of the coins that remain in the chest. The number of coins initially in the chest is the smallest number for which this arrangement will allow each pirate to receive a positive whole number of coins. How many coins does the $12^{\text{th}}$ pirate receive?

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row _builder_version="4.0"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||"][et_pb_accordion open_toggle_text_color="#0c71c3" _builder_version="4.0" toggle_font="||||||||" body_font="Raleway||||||||" text_orientation="center" custom_margin="10px||10px"][et_pb_accordion_item title="Source of the problem" _builder_version="4.0" open="off"]American Mathematics Competition [/et_pb_accordion_item][et_pb_accordion_item title="Topic" _builder_version="4.0" open="off"]

Number Theory

[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="4.0" open="off"]

7/10

[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" open="on" _builder_version="3.29.2"]

Elementary Number Theory by David M. Burton

Start with hints

[/et_pb_text][et_pb_tabs active_tab_background_color="#0c71c3" inactive_tab_background_color="#000000" _builder_version="4.0" tab_text_color="#ffffff" tab_font="||||||||" background_color="#ffffff" custom_padding="||153px|18px||"][et_pb_tab title="Hint 0" _builder_version="3.22.4"]

Well, just give the problem a good read. Probably, with a little bit of thought, you can even get this done without a hint !

[/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="4.0"]

We could start this the traditional way, be assuming the number of coins to be x. Now, ask yourself after the k'th pirate has taken his share, what is the remanant number of coins ? This is ( 12-k / 12 ) of what was originally there. [ Why ? Because each pirate takes k/12 of the coins, remember ? ] Now, could you try taking things up from here...by yourself ?

[/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="4.0"]

Let's understand the next thing the problem is trying to focus on. "Each pirate receives a whole number of coins" Now, this should actually help us conclude x. ( (11.10.9.8.7.6.5.4.3.2.1) / 12 ) is supposed to be an integer. Since this actually implies divisibility. Cancellation of terms leads us to : x. ( (11.5.1.7.1.5.1.1.1.1) / ( 12.6.2.12.2.12.3.4.6.12 ) ) Can you try and approach the solution by yourself now ?

[/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="4.0"]

Now, this tells us the intuition of the problem. We make sure that the quotient should be an integer ! Also, recall that the 12'th pirate definitely takes the entirety of what is left, practically unity since it is exactly divisible.

[/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="4.0"]

So basically, we just realized that the denominator is entirely multiplied out...cancelled ! And since we know that the denominator cancels out, the number of gold coins received by the 12th pirate is just going to be the product of the numerators !!! That evaluates to : 11.5.7.5 = 1925 And that completes our solution !

[/et_pb_tab][/et_pb_tabs][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="-14px||48px|||" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Watch video

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" min_height="12px" custom_margin="50px||50px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Connected Program at Cheenta

[/et_pb_text][et_pb_blurb title="Math Olympiad Program" url="https://cheenta.com/matholympiad/" url_new_window="on" image="https://cheenta.com/wp-content/uploads/2018/03/matholympiad.png" _builder_version="3.23.3" header_font="||||||||" header_text_color="#e02b20" header_font_size="48px" link_option_url="https://cheenta.com/matholympiad/" link_option_url_new_window="on"]

Number Theory - AMC 10A 2014 Problem 24 Sequential Hints

Understand the problem

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway||||||||" background_color="#f4f4f4" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" box_shadow_style="preset2"]

A sequence of natural numbers is constructed by listing the first $4$ , then skipping one, listing the next $5$ , skipping $2$ , listing $6$ , skipping $3$ , and, on the $n$ th iteration, listing $n+3$ and skipping $n$ . The sequence begins $1,2,3,4,6,7,8,9,10,13$ . What is the $500,\!000$ th number in the sequence ?

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row _builder_version="4.0"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||"][et_pb_accordion open_toggle_text_color="#0c71c3" _builder_version="4.0" toggle_font="||||||||" body_font="Raleway||||||||" text_orientation="center" custom_margin="10px||10px"][et_pb_accordion_item title="Source of the problem" open="on" _builder_version="4.0"]American Mathematics Competition [/et_pb_accordion_item][et_pb_accordion_item title="Topic" _builder_version="4.0" open="off"]

Number Theory, Sequences

[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="4.0" open="off"]

7/10

[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" _builder_version="3.29.2" open="off"]Challenges and Thrills of Pre-College Mathematics

Start with hints

[/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="4.0"]

Stuck...? Well, don't worry. The key to solving this problem is not thinking too much about the skips. We can start with natural numbers, from 1 to 500,000. So, a useful strategy could be to find how many numbers we have actually skipped, n and then add them back accordingly. So, now could you take things on from here ?

[/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="4.0"]

If you're a tad bit doubtful of where we're heading even now, well no problem. Clearly, we can say 999.(1000) / 2 < 500,000 < 1000.(1001) / 2 So, now can you find out how many blocks of gaps we have in the sequence ?

[/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="4.0"]

Now see, finding the blocks of gaps easy ! There's just one small thing you would have to recall. We began the count from 4...so now, the number of skipped blocks in the sequence = 999 - 3 = 996. Now to find n, from the number of blocks , we have = (996.997) / 2 = 496,506 This stands for the number of numbers we skipped. Now concluding this is fairly easy...could you try that out yourself ?

[/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="4.0"]

What remains for us to do is to add back those skipped numbers to the count, 500,000 to obtain the final answer. That gives us = 500000 +496506 = 996506

And we are done !

Watch video

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" min_height="12px" custom_margin="50px||50px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Connected Program at Cheenta

Probability - AMC 10A 2015 Problem 22 Sequential Hints

Understand the problem

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway||||||||" background_color="#f4f4f4" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" box_shadow_style="preset2"]Eight people are sitting around a circular table, each holding a fair coin. All eight people flip their coins and those who flip heads stand while those who flip tails remain seated. What is the probability that no two adjacent people will stand?

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row _builder_version="4.0"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||"][et_pb_accordion open_toggle_text_color="#0c71c3" _builder_version="4.0" toggle_font="||||||||" body_font="Raleway||||||||" text_orientation="center" custom_margin="10px||10px"][et_pb_accordion_item title="Source of the problem" open="on" _builder_version="4.0"]American Mathematics Competition [/et_pb_accordion_item][et_pb_accordion_item title="Topic" _builder_version="4.0" open="off"]Probability / Combinatorics

[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="4.0" open="off"]'7/10[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" _builder_version="3.29.2" open="off"]Challenges and Thrills of Pre-College Mathematics

Start with hints

[/et_pb_text][et_pb_tabs active_tab_background_color="#0c71c3" inactive_tab_background_color="#000000" _builder_version="4.0" tab_text_color="#ffffff" tab_font="||||||||" background_color="#ffffff" custom_padding="||150px|18px||"][et_pb_tab title="Hint 0" _builder_version="3.22.4"]You could give it a thought first...are you sure you really need a hint ?

[/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="4.0"]

Let's not get worried by the idea of having to find out the probability. For, we may simply recall : Probability = Number of favorable events / Total number events in the sample space So, the denominator is easy to find out here, 8 people, all of whom are either standing or sitting. So, 2 possibilities for every person. And that makes our denominator, $2^8 = 256 $ Now, with a little bit of focus, it is not at all hard to see that the numerator, "number of favorable events" is essentially a Combinatorics arrangement problem.

So, would you like to have a go at this by yourself now ?

[/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="4.0"]

Now, as we go ahead with the solution, let us develop the idea of the strategy we could use here. You must be familiar with recursion, but let's just recall its philosophy. Recursion essentially meant that you could express a variable or a term in terms of its own parameters. As in, when a function calls itself. If you want a brief look-up, catch the short story in the paragraph below [ Much like imagine, you're eating a large cake. You won't really eat the whole thing at once, would you ? You would possibly enjoy it in parts. Imagine you'd have 1/3 rd of it, to begin with. Then if your problem initially is, EAT THE CAKE. Even, after you have had a first bite, as I just said, what's the name of your problem ? It's still EAT THE CAKE , isn't it ? Yes, you're still eating the same cake, only your problem is reduced by 1/3-rd, somewhat like a miniature version. Something we could call, ( EAT THE CAKE ) / 3...That's pretty much, an intuitive idea of recursion. ] How could we model our problem in that fashion ? Imagine we talk of 8 persons standing in the line, to begin with. Let us try to develop a recurrence relation for the problem. Let's talk of a person, N in the queue. See the catch here, if this person N is sitting, our problem size reduces by 1 - which means it is now equivalent to 7 people standing in the queue. On the other hand if this person N is standing, it is implied by the statement of the problem, that the adjacent people on his either side must be sitting ! That reduces our problem size by 2... Hey, so now that we have kind of linguistically framed it, could you try out a mathematical interpretation ?

[/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="4.0"]

Let, the answer we are looking for is a_n. ( That is, the number of ways to arrange n people in a line such that no two of them, who are adjacent, are standing ) So for a_n >= 2,
See there can be only two broad-spectrum cases : Case I : Person #1 in the line is standing If Person #1 in the line is standing, the second one is sitting. So the rest can be arranged in a_n-2 ways. Case II : Person #1 in the line is sitting
This means the rest can be arranged in a_n-1 ways. So, Case I + Case II, adds up to the relation we are looking for ? That would be something like : a_n = a_n-2 + a_n-1 Wait ! Does this, by any chance seem familiar ? Does it ? Well yes, this is nothing but the Fibonacci Recurrence Relation. The problem of rabbits in the field, if you need some off-beat reference ! [ The Fibonacci Sequence goes like :
1,1,2,3,5,8,13, 21, 34,....
It's quite easy to see that from the third time onwards, every term is numerically equal to the sum of its two previous terms ] So, do you think you could conclude this...and find the required probability ?

[/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="4.0"]

So we just saw, we can map the given problem at hand to the Fibonacci problem. Our starting cases here would be a_0 = 1 and a_1 = 2. ( By the problem ). This means our ans would be the (n+2)th Fibonacci number for a_n F_n stands for the n'th Fibonacci number, of the sequence you just came across in the last hint. So that gives us a_5 + a_7 = F_7 + F_9 = 13 + 34 = 47. So, that's our numerator ! Hence, the required probability = 47 / 256

And that's pretty much of all we need !

Watch video

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" min_height="12px" custom_margin="50px||50px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Connected Program at Cheenta

Number Theory - AMC 10A 2016 Problem 22

Understand the problem

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway||||||||" background_color="#f4f4f4" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" box_shadow_style="preset2"] For some positive integer $n$ , the number $110n^3$ has $110$ positive integer divisors, including $1$ and the number $110n^3$ . How many positive integer divisors does the number $81n^4$ have ?

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row _builder_version="3.25"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||"][et_pb_accordion open_toggle_text_color="#0c71c3" _builder_version="4.0" toggle_font="||||||||" body_font="Raleway||||||||" text_orientation="center" custom_margin="10px||10px"][et_pb_accordion_item title="Source of the problem" open="on" _builder_version="4.0"]American Mathematics Competition [/et_pb_accordion_item][et_pb_accordion_item title="Topic" _builder_version="4.0" open="off"]Number Theory

[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="4.0" open="off"]8/10

[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" _builder_version="3.29.2" open="off"]

Elementary Number Theory by David M. Burton

[/et_pb_accordion_item][/et_pb_accordion][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="48px||48px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Start with hints

[/et_pb_text][et_pb_tabs active_tab_background_color="#0c71c3" inactive_tab_background_color="#000000" _builder_version="4.0" tab_text_color="#ffffff" tab_font="||||||||" background_color="#ffffff" custom_padding="|||21px||"][et_pb_tab title="Hint 0" _builder_version="4.0"]

Check the problem out...give its statement a thorough read. Might appear a bit daunting on the first couple of reads. Think for some time, you could be on to something without any help whatsoever ![/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="4.0"]

Okay, now let's think about what our first thoughts could be, on the problem. It's definitely about the n in the problem, which acts as our unknown here. Can you somehow try finding the n ? Let's take the first step in that direction. How could we prime factorize 110 ? That's easy 110 = 2.5.11. Could you take things from hereon to find more about the n ?

[/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="4.0"]

However interestingly the problem says, the number 110. (n^3) has 110 factors. Just as we saw, 110. (n^3) = 2.5.11.(n^3) Now, let's use some basic number theoretic knowledge here. How many divisors would 110. (n^3) have then ? If n=1 Clearly it would have, (1+1). (1+1). (1+1) = 8 divisors. So see, that's the idea isn't it ? Pretty much of plug and play. We actually get to control how many divisors the number has, once we adjust (n^3). Now you could try some advances...

[/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="4.0"]

Okay, so as we just understood we need to achieve a count of 110 divisors. If we have 110.(n^3) = 2^(10). 5^(4). 11 which actually conforms to : (10+1).(4+1).(1+1) = 11.5.2 = 110 So, that implies : (n^3) = 2^(9). 5^(3), which means, n = 2^(3). 5 Now that we have found out n...the rest dosen't seem really a big deal. You could do it...try !

[/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="4.0"]

Well, it's pretty straightforward now. Let's call 81.(n^4) equal to some X. First let's prime factorize 81. That would be 81 = (3^4). So, finally X = (3^4). (2^12). (5^4) How many divisors does that make ? Yes, (4+1).(12+1). (4+1) = 13.25 = 325.

That's our answer. 325 factors.

[/et_pb_tab][/et_pb_tabs][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="48px||48px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Watch video

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" min_height="12px" custom_margin="50px||50px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Connected Program at Cheenta

Number Theory - AMC 10A 2014 Problem 20 Sequential Hints

Understand the problem

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway||||||||" background_color="#f4f4f4" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" box_shadow_style="preset2"]The product $(8)(888\dots8)$ , where the second factor has $k$ digits, is an integer whose digits have a sum of $1000$ . What is $k$ ?

[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row _builder_version="3.25"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||"][et_pb_accordion open_toggle_text_color="#0c71c3" _builder_version="4.0" toggle_font="||||||||" body_font="Raleway||||||||" text_orientation="center" custom_margin="10px||10px"][et_pb_accordion_item title="Source of the problem" open="off" _builder_version="4.0"]American Mathematics Competition [/et_pb_accordion_item][et_pb_accordion_item title="Topic" _builder_version="4.0" open="off"]Number Theory

[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="4.0" open="off"]7/10

[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" _builder_version="3.29.2" open="on"]

Elementary Number Theory by David M, Burton

[/et_pb_accordion_item][/et_pb_accordion][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="48px||48px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Start with hints

So, well have a long look at the problem. With a little bit of thought, you might even crack this without proceeding any further !

[/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="4.0"]

Think you could do with some help ? Okay let's get ourselves a headstart. As you might have guessed, sometimes the most fruitful thing to be done is to observe what's going on in these kind of problems. The intuition is clear, there are too many instances of '8'-s for someone to account for them manually. So, yes, that's something we can expect. Try working out with a few simple cases like, k=1, k=2, and so on...

[/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="4.0"]

Okay, so let's see what's happening for a few small values of k...
k=1
8 * 8 = 64 k=2
8 * 88 = 704 k=3
8 * 888 = 7104 k=4
8 * 8888 = 71104 ...
So, Wait ! Look closely...Do you see something ?

[/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="4.0"]

A really nice pattern is evolving. If you can see it, and yet find it a bit difficult to articulate it mathematically, don't worry. See for k=4, the product gives us the result 71104. That means, we have the starting digit to be 7. And the ending suffix is 04. What varies are the ones. See, for k=4, we have ( k-2 = 2 ) ones. That's it ! The generalization should be fairly simple for us to do now... For every k >=2, the product result consists of a 7 to start with, exactly k-2 1's follow, and we conclude with single occurrences of 0 and 4 each. Now, think...can you take this till the end ?

[/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="4.0"]

Once we've seen the pattern, it's easy to get this done. What we have noted, we need that to sum up to 1000. In simple mathematical terms, 7 + (k-2).1 + 0 + 4 = 1000
11 + k = 1002
k = 991

So, we need '8' to come 991 times in the multiplicand, so that the digits sum up to 1000. So, that seals the deal !

[/et_pb_tab][/et_pb_tabs][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="48px||48px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Watch video

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" min_height="12px" custom_margin="50px||50px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Connected Program at Cheenta

Enumerative Combinatorics- AMC 10A 2017 Problem 25 Sequential Hints

Understand the problem

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway||||||||" background_color="#f4f4f4" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" box_shadow_style="preset2"]How many integers between $100$ and $999$ , inclusive, have the property that some permutation of its digits is a multiple of $11$ between $100$ and $999?$ ( For example, both $121$ and $211$ have this property. )

[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="4.0" open="off"]7/10

[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" _builder_version="3.29.2" open="off"]Introductory Combinatorics by Richard Brualdi

[/et_pb_accordion_item][/et_pb_accordion][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="48px||48px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Start with hints

[/et_pb_text][et_pb_tabs active_tab_background_color="#0c71c3" inactive_tab_background_color="#000000" _builder_version="4.0" tab_text_color="#ffffff" tab_font="||||||||" background_color="#ffffff"][et_pb_tab title="Hint 0" _builder_version="3.22.4"]So, well have a long look at the problem. With a little bit of thought, you might even crack this without proceeding any further !

[/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="4.0"]

Stuck ?...No worries. Try asking yourself - How many numbers between 100-999 are exactly divisible by 11 ? This is quite easy to figure out.
What is the largest number in the range divisible by 11 ? Easy, 990.
How about the smallest such number ? Yeah, 110.
So, the number of integers in the range visible by 11 = ( ( 990 - 110 ) / 11 ) + 1 = 81.
Now, how about you try taking things ahead from here onwards ?

[/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="4.0"]

Now see, 81 numbers are divisible by 11 in the range, as we just saw. All that's left is to find out the permutations of these. Wait ! That's simple, isn't it ? Yes, 81 x 3 = 243. At this very juncture, ask yourself why. If you find out the answer to this "why", you can might as well say you've gone far enough to solve the problem...

[/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="4.0"]

Let's answer the "why" here. Say, we have a 3-digit number, abc. Now, ideally we would have had 6 permutations ( 3 ! simply ) for each such abc. But here's a catch ! If abc is divisible by 11, so is cba....!!! Yeah, that's it. So, basically if we multiply by 6, we are accounting for same kind of permutations twice. So basically, each multiple of 11 in the range has it's ( 6/2 ) = 3 permutations, that we are bothered about. This clearly justifies the fact that we can at maximum have 81 x 3 = 243 numbers in our desired solution set. But wait ? Why do I say, at maximum ? So...have we overcounted ? Yeah,we have. Why don't you think about it...?

[/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="4.0"]

Well, as you might have felt, we did overcount. We did not account for the numbers where 0 could be one of the digits. We overcounted cases where the middle digit of the number is 0 and the last digit is 0. So, what are these ? Let's find them out. In how many of the numbers is the last digit 0 ? That's easy...they have a pattern. It goes like 110, 220,....990. That makes it 9. Now, in how many of those 243 numbers that we are bothered about, does '0' occur as a middle digit ? With a little bit of insight, you'd find out they are 803, 902, 704, 605. And well their permutations too. So that makes it 4 x 2 = 8. So, in total, 9+8 = 17 elements have been overcounted.

Subtract that from 243, ( 243 - 17 ) = 226, that's your answer.

[/et_pb_tab][/et_pb_tabs][/et_pb_column][/et_pb_row][/et_pb_section][et_pb_section fb_built="1" _builder_version="4.0" global_module="40396" saved_tabs="all"][et_pb_row _builder_version="4.0"][et_pb_column type="4_4" _builder_version="4.0"][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" min_height="12px" custom_margin="50px||50px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Connected Program at Cheenta

[/et_pb_text][et_pb_blurb title="AMC Training Camp" url="https://cheenta.com/amc-10-12-training-camp-american-mathematics-competition/" url_new_window="on" image="https://cheenta.com/wp-content/uploads/2018/03/matholympiad.png" _builder_version="4.0" header_font="||||||||" header_text_color="#e02b20" header_font_size="48px" link_option_url="https://cheenta.com/amc-10-12-training-camp-american-mathematics-competition/" link_option_url_new_window="on"]

One on One class for every student. Plus group sessions on advanced problem solving.

A special training program for American Mathematics Contest.

[/et_pb_blurb][et_pb_button button_url="https://cheenta.com/amc-10-12-training-camp-american-mathematics-competition/" url_new_window="on" button_text="Learn More" button_alignment="center" _builder_version="4.0" custom_button="on" button_bg_color="#0c71c3" button_border_color="#0c71c3" button_border_radius="0px" button_font="Raleway||||||||" button_icon="%%3%%" background_layout="dark" button_text_shadow_style="preset1" box_shadow_style="preset1" box_shadow_color="#0c71c3"][/et_pb_button][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="50px||50px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

Zonal Computing Olympiad 2018 Solutions-I

Here is the part 1 of solutions of Zonal Computing Olympiad 2018 of International Informatics Olympiad held in Tsukuba, Japan.

Problem 1: BIRTHDAY-CAKES

Before going to the solution/hints, it's always good if you re-read ( assuming you've already encountered the problem ) the problem statement once. And if you aren't aware of the problem statement, then it's only logical that you read it.
In any case, if you need to see the statement of the problem, you can find it here:

Zonal Computing Olympiad 2018 Questions.

Now, let us deal with the cases that constitute the problem. They are precisely k=0 and k=1

Case-I (k=0)
This case is pretty trivial. It can be solved with a bit of thought.
The algorithm we follow for this is:

Take each pair [a,b] denoting the permissible ranges of the cakes which a child can enjoy.
If a!=b, we append elements in range (a,b) { both inclusive } to an empty array declared beforehand.
If a==b, we append only a to the array.
Then we check if the array has any duplicate elements or not.
If it does, we print "BAD" , else we print "GOOD".

Case-II (k=1)
This case can be a lot simplified, the moment we realize the fact that INTERSECTIONS of the permissible ranges in which a child enjoys cakes can occur only in TWO ways.
ONE way being when the destination ( last element ) of a permissible range, is equal to the source ( first element ) of another permissible range.
{ In terms of interpretation in code, we will have a function dupli_1(arr) that returns 1 if any two consecutive elements in an array are equal. We will check if we have dupli_1(arr) = 1 for the array that contains all pairs (a,b) appended to it. }
ANOTHER way we can have fights is when an entire permissible range of cakes for some child is CONTAINED in the permissible range of cakes for another child, that is, for eg, the string "6" is 'entirely contained' in the array "567". ( In other words "6" is a substring of "567" ).

{ We use the contiguous substring concept here, and have a function dupli_2(array) that returns 1 if a string in the array is a contiguous substring of any other string in the same array.}
Now if both of the aforementioned functions return 1, we break and output "BAD" immediately, because the question gives us the liberty to move at max one child.
If anyone of those functions return 1, we act accordingly.
If dupli_1(arr)==1, we find out the particular element ; and take the minimum of the lengths of the two strings it occurs in, Assume this length to be g. Let w be the no. of elements, which are IN [1,..9] but NOT IN arr. ( These checks take linear time ).
If w >=g : we print "GOOD" , else we print "BAD"
Alternatively, if dupli_2(array)==1, we take g to be the length of the substring. And the deciding factor stays the same.

Hence, done.

Another approach to k=1:

We find any pair which intersects and let's think them to be i and i+1 and check if we can place i+1 in vacant places without overlaps via brute-force.

Zonal Computing Olympiad 2018 Questions.

These are the Questions from Zonal Computing Olympiad 2018 Exam of International Infromatics Olympiad held in Tsukuba, Japan.

Problem 1 : BIRTHDAY-CAKES
In a birthday party, there are C cakes and N children. There is also an integer k, given.
But since eating too much of cakes can give you toothache, each of the children have been prescribed by doctors to eat cakes that fall only within a specific interval (a,b) both inclusive.

If k = 0, you have answer if any of the students' ranges clash or not.
That is print "GOOD" ( without quotes ) if ranges do not clash and "BAD" ( without quotes ) if they will fight over their share of cakes.

If k=1, then you have a chance to stop them to stop them from fighting. You are allowed to move at max 1 child from his place and allot him a different range, PROVIDED THAT HE IS STILL ABLE TO HAVE THE SAME NUMBER OF CAKES AS HE WOULD HAVE HAD IN HIS PREVIOUS RANGE.
If you can prevent all the fights among the children, by 'moving' only one child , print "GOOD" ( without quotes ) , else print "BAD" ( without quotes ).

Input Format

A single line containing an integer t, denoting the number of test cases.
For each test case, input 3 space separated integers denoting N, C and k
For each test cases, C lines follow, denoting the ranges within which the children can enjoy cakes.

Output Format
t lines.
Each line containing either "GOOD" or "BAD" , as applicable.

Sample Testcases

Input

3
5 2 0
2 2
3 5
5 2 1
2 2
2 5
5 2 1
2 3
2 5

Output
GOOD
GOOD
BAD

Explanation

In the second test case, the child at [2,2] can be moved to [1,1] so that there are no fights anymore. Also, note that the child can still enjoy 1 cake as he would have done, had his position not been 'moved'.

Problem 2: IMPORTANT STRINGS

After having cakes at the birthday, you've got to study some English.
You may feel strings are a random collection of characters, but no they are important, and this is how.
Suppose you have a string S of length N consisting of X, Y, and Z .
A string is 'good' if it starts with a 'X' , ends with a 'Z' and has a length divisible by 3. ( That is permissible lengths are 3, 6, 9....and so on )

The importance of a string is the number of good string it intersects with.

Given the string S and a length k, find a string of length exactly k and minimize it's importance.
Your job is to print the minimum importance.

Input Format

The first line contains a single integer t, denoting the number of test cases.
Each test case contains two lines.
The first line of each test case contains two space separated integers denoting N and k.
The second line of each test case contains the string S.

Output Format
t lines.
Each line contains a single integer denoting the required minimum importance.

Sample Testcases

Input
2
9 3
X Y Z Z Y X X Y Z
4 2
Y X Y Z

Output
1
1

Explanation
In the first testcase, the good strings are in the ranges [0,2] [0,8] and [6,8]. ( 0-based indexing has been used )
Now consider the string at [5,8]. It is of length k=3. It intersects with only one good string [0,8] ; ( the entire one ).
That's the best we can do. So it has importance 1, and that's our desired output.

You may visit this link to see the solutions:- https://cheenta.com/zonal-computing-olympiad-2018-solutions-i/

Understand the problem

Start with hints

Watch video

Connected Program at Cheenta

Similar Problems

Understand the problem

Start with hints

Watch video

Connected Program at Cheenta

Similar Problems

Understand the problem

Start with hints

Watch video

Connected Program at Cheenta

Similar Problems

Understand the problem

Start with hints

Watch video

Connected Program at Cheenta

Similar Problems

Understand the problem

Start with hints

Watch video

Connected Program at Cheenta

Similar Problems

Understand the problem

Start with hints

Watch video

Connected Program at Cheenta

Similar Problems

Understand the problem

Start with hints

Connected Program at Cheenta

Similar Problems

Hence, done.