Let's Permute | ISI MStat 2018 PSB Problem 3

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?

Prerequisites

Solution

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

Arbitrary Arrangement | TOMATO B.Stat Objective 119

Try this problem from I.S.I. B.Stat Entrance Objective Problem based on Arbitrary Arrangement.

Arbitrary Arrangement ( B.Stat Objective Question )


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


Answer: necessarily even.

B.Stat Objective Problem 119

Challenges and Thrills of Pre-College Mathematics by University Press

Try with Hints


necessarily \(\leq\) 0 case

taking values (2-1)(3-2)(4-3).....(10-9)(1-10)(10-11)

here all the terms except last two terms are positive and there are 2 negetive terms whose product will be even

then product > 0

then not necessarily < 0 or = 0

necessarily even case

by contradiction

we assume that the product is not necessarily even

that is each of the factor have to be odd

then the arrangement look like

(even-1)(odd-2)(even-3)(odd-4)....(even-9)(odd-10)

but only one odd number left which will pair with 11 that a contradiction

\(\Rightarrow\) product is even

\(\Rightarrow\) necessarily even.

Subscribe to Cheenta at Youtube


Cubes and Rectangles | Math Olympiad Hanoi 2018

Cubes and Rectangles - Math Olympiad Hanoi 2018


Try this beautiful problem from Math Olympiad Hanoi, 2018 based on Cubes and Rectangles.

Find the number of rectangles can be formed by the vertices of a cube.

  • 6
  • 8
  • 18
  • 12

Key Concepts


Geometry

Permutation

Combination

Check the Answer


Answer: 12.

Math Olympiad Hanoi 2018

Geometry Vol I to IV by Hall and Stevens

Try with Hints


First hint

There are 6 squares on 6 faces on the cube.

Second Hint

There are 4 diagonals of the cube that have the same length

and pass through the center of the cube. Every two diagonals intersect at the midpoint and form a rectangle.

Final Step

Then there are 6+ $(\frac{4!}{2!2!})$ =12 rectangles.

Subscribe to Cheenta at Youtube


Maximizing Arrangements

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 frac {(x+y+z)!}{x! y! z!} = frac {30!}{x! y! z!} . 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

Other useful links:-

Combinatorics - B.Stat. (Hons.) Admission Test 2005 – Objective Problem 1

[et_pb_section fb_built="1" _builder_version="4.3.1" hover_enabled="0"][et_pb_row _builder_version="4.2.2" width="100%"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||"][et_pb_text _builder_version="4.2.2" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_padding="10px|10px|10px|10px|false|false" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3" inline_fonts="Aclonica"]

What are we learning ?

[/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||20px||false|false" custom_padding="10px|20px|10px|20px" box_shadow_style="preset2"]

Competency in Focus: combinatorics

This problem from B.Stat. (Hons.) Admission Test 2005 – Objective Problem 1  is based on arranging integers to get particular results. 

[/et_pb_text][et_pb_text _builder_version="4.2.2" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="10px||10px||false|false" custom_padding="10px|10px|10px|10px|false|false" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3" inline_fonts="Aclonica"]

First look at the knowledge graph:-

[/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"]

Combinatorics 

[/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_fullwidth_header][/et_pb_section][et_pb_section fb_built="1" fullwidth="on" _builder_version="4.2.2" custom_margin="||||false|false" custom_padding="||||false|false" global_module="50860" saved_tabs="all"][et_pb_fullwidth_post_slider include_categories="10,870" show_meta="off" image_placement="left" _builder_version="4.2.2" custom_margin="20px||20px||false|false" custom_padding="||||false|false"][/et_pb_fullwidth_post_slider][/et_pb_section]

Permutation and basic counting principle AMC 8 2012, problem 10

[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"]

What are we learning ?

[/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"]Competency in Focus: Basic counting principle and permutation   This problem from American Mathematics contest (AMC 8, 2012) [/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_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3"]

First look at the knowledge graph.

[/et_pb_text][et_pb_image src="https://www.cheenta.com/wp-content/uploads/2020/01/AMC-8-2012-problem-10-1.png" align="center" force_fullwidth="on" _builder_version="4.1" min_height="252px" height="284px" max_height="411px"][/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"]

Next understand the problem

[/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 $2012$, since all of the valid 4-digit number will always be greater than $1000$.  [/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 $1$ or $2$.[/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 5. . 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  $\frac{3!}{2!1!} \implies 3$ such numbers.  [/et_pb_tab][et_pb_tab title="HINT 6" _builder_version="4.1"]When the leading digit is $2$ then we have one 2, one 1 and one 0 then we can arrange them in  $3! \implies 6$ 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]