This problem is an easy application of the basic algorithmic ideas to approach a combinatorics problem using permutation and combination and basic counting principles. Enjoy this problem 3 from ISI MStat 2018 PSB.
Problem
Consider all permutations of the integers \(1,2, \ldots, 100\) . In how many of these permutations will the \(25^{th}\) number be the minimum of the first 25 numbers and the \(50^{th}\) number be the minimum of the first 50 numbers?
Whenever you are counting, think in terms of algorithms or steps in which you will do the task given in the problem and count each of the steps. Now the conjunction in between the steps ( and \(\cap\) , or \(\cup\) ) will show you the way.
Steps
Select the first 50 numbers. Fix the minimum element. Out of the 49 other elements, select the first 25 numbers. Fix the minimum element of these 25 numbers. Then permute the rest.
AND for each of these selections of two sets (Multiplication Principle),
Step 2
Once you select the three sets, the minimum of each of these sets is already fixed. So, for each of these sets, you have to permute the other first 24 numbers (1 - 24) and the next 24 numbers (from 26 - 49) and the other 50 numbers (50 - 100).
You can do that in \(24! \times 24! \times 50! \) ways.
Therefore, you can do the whole task in \( {100 \choose 50} \times { 49 \choose 25 } \times 24! \times 24! \times 50!\) ways.
Food for Thought
Do the problem for \(2n\) numbers.
Do the problem if you want to fix the minimum \(k\) numbers in each set out of \(2n\) numbers.
Do the problem if you want to fix the minimum \(n\) numbers in each set out of \(2n\) numbers. Does it match your expectation?
Generalize and Degeneralize and make your own problem out of this. Comment it below. We will update it here if we think the problem is appropriate.
Let \(a_1, a_2, ....,a_{11}\) be an arbitrary arrangement (ie permutation) of the integers 1,2,....,11. Then the numbers \((a_1-1)(a_2-2)....(a_{11}-{11})\) is
necessarily \(\leq\) 0
necessarily even
necessarily 0
none of these
Key Concepts
Permutation
Numbers
Even and Odd
Check the Answer
But try the problem first...
Answer: necessarily even.
Source
Suggested Reading
B.Stat Objective Problem 119
Challenges and Thrills of Pre-College Mathematics by University Press
x red balls, y black balls and z white balls are to be arranged in a row. Suppose that any two balls of the same color are indistinguishable. Given that x+y+z=30, show that the number of possible arrangements is the largest for x=y=z=10.
Solution: The total number of ways of arranging the 30 balls are . Thus we can maximize the number of arrangements by minimizing the denominator. Our claim is that the denominator is least when x=y=z=10.
Suppose otherwise. Let x=10+m , y=10-n, z=10-r minimize the denominator (since all are not equal there will be at least one which is larger than 10; without loss of generality we assume that to be
[/et_pb_text][et_pb_image src="https://www.cheenta.com/wp-content/uploads/2020/02/p1.png" alt="calculation of mean and median- AMC 8 2013 Problem" title_text=" mean and median- AMC 8 2013 Problem" align="center" force_fullwidth="on" _builder_version="4.2.2" min_height="429px" height="189px" max_height="198px" custom_padding="10px|10px|10px|10px|false|false"][/et_pb_image][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" inline_fonts="Aclonica"]
Next understand the problem
[/et_pb_text][et_pb_text _builder_version="4.2.2" text_font="Raleway||||||||" text_font_size="20px" text_letter_spacing="1px" text_line_height="1.5em" background_color="#f4f4f4" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" box_shadow_style="preset2"]1. How many three-digit numbers of distinct digits can be formed by using the digits 1, 2, 3, 4, 5, 9 such that the sum of the digits is at least 12? (A) 61 (B) 66 (C) 60 (D) 11[/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.3.1" 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.3.1"]B.Stat. (Hons.) Admission Test 2005 – Objective problem 1[/et_pb_accordion_item][et_pb_accordion_item title="Key Competency" _builder_version="4.3.1" inline_fonts="Abhaya Libre" open="on"]
[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="4.1" open="off"]4/10[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" _builder_version="4.0.9" open="off"]Challenges and Thrills in Pre College Mathematics Excursion Of Mathematics [/et_pb_accordion_item][/et_pb_accordion][et_pb_text _builder_version="4.0.9" 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|0px|20px||" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3" inline_fonts="Aclonica"]
Start with hints
[/et_pb_text][et_pb_tabs _builder_version="4.2.2"][et_pb_tab title="HINT 0" _builder_version="4.0.9"]Do you really need a hint? Try it first![/et_pb_tab][et_pb_tab title="HINT 1" _builder_version="4.2.2"]Out of \(n\) things we can select \(r\) thing ins in \left( \begin{array}{c} n \\ r \end{array}\right) ways. Similarly we can select \(3\) integers out of \(6\) in \left( \begin{array}{c} 6 \\ 3 \end{array}\right) ways.[/et_pb_tab][et_pb_tab title="HINT 2" _builder_version="4.2.2"]We want to count the cases that do not work (That means sum becomes less than 12). Note that if 9 is one of the three digits then the sum of the digits will be 12 or more (least case is 9+1+2 =12). an similarly you can thing next posibiily. [/et_pb_tab][et_pb_tab title="HINT 3" _builder_version="4.2.2"]Note that if we want get the numbers whose sum is equal to or greater than 12 then from the digits 1,2,3,4 and 5 (but not 9), then there is only one posibility and that is \(5+4+3\).[/et_pb_tab][et_pb_tab title="HINT 4" _builder_version="4.2.2"]Therefore we select 3 distinct digits from the five digits and delete the one selection of {5, 4, 3}. This gives us the total number of bad cases. \(\left( \begin{array}{c} n \\ r \end{array}\right)–1=9\).[/et_pb_tab][et_pb_tab title="HINT 5" _builder_version="4.2.2"]Now we have total 20 posibilities out of which 9 are non-working solutions for our question. So total orking solutions is \(20-9=11\). Further we can arrange this 3 letters in \(3! =6\) ways. Hence the total number of required ways = \( 11 * 6=66 \).[/et_pb_tab][/et_pb_tabs][/et_pb_column][/et_pb_row][/et_pb_section][et_pb_section fb_built="1" fullwidth="on" _builder_version="4.2.2" custom_margin="20px||20px||false|false" global_module="50753" saved_tabs="all" locked="off"][et_pb_fullwidth_header title="I.S.I. & C.M.I. Program" button_one_text="Learn more" button_one_url="https://www.cheenta.com/isicmientrance/" header_image_url="https://www.cheenta.com/wp-content/uploads/2018/03/ISI.png" _builder_version="4.2.2" title_level="h2" title_font="Acme||||||||" background_color="#220e58" custom_button_one="on" button_one_text_color="#1a0052" button_one_bg_color="#ffffff" button_one_border_color="#ffffff" button_one_border_radius="5px"]
Indian Statistical Institute and Chennai Mathematical Institute offer challenging bachelor’s program for gifted students. These courses are: B.Stat and B.Math program in I.S.I., B.Sc. Math in C.M.I. The entrances to these programs are far more challenging than usual engineering entrances. Cheenta offers an intense, problem-driven program for these two entrances.
[/et_pb_text][et_pb_text _builder_version="4.1" text_font="Raleway||||||||" text_font_size="20px" text_letter_spacing="1px" text_line_height="1.5em" background_color="#f4f4f4" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" box_shadow_style="preset2"]How many 4-digit numbers greater than 1000 are there that use the four digits of 2012?[/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.1" 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.1"]American Mathematical Contest 2012, AMC 8 Problem 10[/et_pb_accordion_item][et_pb_accordion_item title="Key Competency" _builder_version="4.1" open="off"]Permutation and basic counting principle[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="4.1" open="off"]4/10[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" _builder_version="4.0.9" open="off"]Challenges and Thrills in Pre College Mathematics Excursion Of Mathematics [/et_pb_accordion_item][/et_pb_accordion][et_pb_text _builder_version="4.0.9" 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|0px|20px||" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]
Start with hints
[/et_pb_text][et_pb_tabs _builder_version="4.1"][et_pb_tab title="HINT 0" _builder_version="4.0.9"]Do you really need a hint? Try it first![/et_pb_tab][et_pb_tab title="HINT 1" _builder_version="4.1"]For this problem, all we need to do is find the amount of valid 4-digit numbers that can be made from the digits of , since all of the valid 4-digit number will always be greater than . [/et_pb_tab][et_pb_tab title="HINT 2" _builder_version="4.1"]The best way to solve this problem is by using casework. Now think what are the cases? [/et_pb_tab][et_pb_tab title="HINT 3" _builder_version="4.1"]It has two cases , as there can be only two leading digits, namely or .[/et_pb_tab][et_pb_tab title="HINT 4" _builder_version="4.1"]We know that number of ways of arranging ‘n’ items, out of which ‘p’ are alike, ‘q’ are alike and ‘r’ are alike given that p + q + r = n Number of ways of distributing ‘n’ distinct items, in groups of size ‘p’, ‘q’ and ‘r’ given that p + q + r = n . . Now try to calculate the the two cases .[/et_pb_tab][et_pb_tab title="HINT 5" _builder_version="4.1"]CASE 1:As 2012 consits of two 2's , one 1, 0 so if we set 1 as the leading digit then we have two twos and one 0 such numbers then we have such numbers. [/et_pb_tab][et_pb_tab title="HINT 6" _builder_version="4.1"]When the leading digit is then we have one 2, one 1 and one 0 then we can arrange them in ways and as such we have 6 such numbers.[/et_pb_tab][et_pb_tab title="HINT 7" _builder_version="4.1"]By addition principle we find that there are 9 such numbers.[/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="50px||50px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]
Similar Problems
[/et_pb_text][et_pb_post_nav in_same_term="off" _builder_version="4.0.9"][/et_pb_post_nav][et_pb_divider _builder_version="3.22.4" background_color="#0c71c3"][/et_pb_divider][/et_pb_column][/et_pb_row][/et_pb_section][et_pb_section fb_built="1" fullwidth="on" _builder_version="4.2.2" global_module="50833" saved_tabs="all"][et_pb_fullwidth_header title="AMC - AIME Program" button_one_text="Learn More" _builder_version="4.2.2" button_one_url="https://www.cheenta.com/amc-aime-usamo-math-olympiad-program/" hover_enabled="0" custom_button_one="on" button_one_bg_color="#ffffff" button_one_bg_enable_color="on" button_one_border_color="#ffffff" button_one_text_color="#44580e" button_one_border_radius="5px" background_color="#00457a" header_image_url="https://www.cheenta.com/wp-content/uploads/2018/03/matholympiad.png"]AMC - AIME - USAMO Boot Camp for brilliant students. Use our exclusive one-on-one plus group class system to prepare for Math Olympiad
[/et_pb_fullwidth_header][/et_pb_section]
. Thus we can maximize the number of arrangements by minimizing the denominator. Our claim is that the denominator is least when x=y=z=10.
such numbers. [/et_pb_tab][et_pb_tab title="HINT 6" _builder_version="4.1"]When the leading digit is