Lesson Nice recreational problems of Combinatorics

Source code of 'Nice recreational problems of Combinatorics'

This Lesson (Nice recreational problems of Combinatorics) was created by by ikleyn(52908)

: View Source, Show
About ikleyn:

<H2>Nice recreational problems of Combinatorics</H2>

The problems in this lesson have unexpected and beautiful solutions.

<H3>Problem 1</H3>A class of &nbsp;30 &nbsp;students took two quizzes. &nbsp;Sixteen passed the first quiz and &nbsp;20 &nbsp;passed the second. 
If &nbsp;4 &nbsp;students failed both quizzes, &nbsp;how many passed both?

<B>Solution</B>

<pre>
From the condition, 30-16 = 14 failed the first quiz, and

30-20 = 10 failed the second quiz,

while           4 failed both quizzes.

Hence,  the number of those who failed at least one quiz is  14 + 10 - 4 = 20.

It means that 30-20 = 10 students passed both quizzes.    <U>ANSWER</U>
</pre>

<H3>Problem 2</H3>Tom &nbsp;and &nbsp;Jerry and five other people get on a bus one at a time. 
How many ways can the seven get on the bus if &nbsp;Tom gets on the bus after &nbsp;Jerry ?

<B>Solution</B>

<pre>
The total number of different arrangements in which the 7 people can board the bus is 7! = 5040.

For every arrangement, where Jerry is before Tom, there is an arrangement, where Tom is before Jerry.

It is obtained by internal permutation inside the group of these two persons.

Therefore, by symmetry, in exactly half of those arrangements Tom gets on after Jerry.

<U>ANSWER</U>.  2520 ways.
</pre>

<H3>Problem 3</H3>In how many ways can &nbsp;4 &nbsp;pennies, &nbsp;5 &nbsp;nickels and &nbsp;3 &nbsp;dimes be distributed among &nbsp;12 &nbsp;children, &nbsp;if each is to receive one coin ?

<B>Solution</B>

<pre>
It is the same as to ask

How many 12-letter words could be written using 4 letters P, 5 letters N and 3 letters D ?

(using letters P, N and D to code the pennies, nickels and dimes, respectively).

The answer is  {{{12!/(4!*5!*3!)}}} = 27720, using our knowledge about arranging indistinguishable elements.
</pre>

<H3>Problem 4</H3>Donald has a pair of blue shoes, a pair of red shoes, and a pair of white shoes. 
He wants to put these six shoes side by side in a row. However, Donald wants the left shoe of each pair 
to be somewhere to the left of the corresponding right shoe. How many ways are there to do this?

<B>Solution</B>

<pre>
The total number of permutations of 6 items is  6! = 720.

In this set of all permutations,  S(6), exactly HALF of all permutations has the "leftBLUE" item on the left from "rightBLUE" item.

So, regarding blue shoes, we have the subset in  S(6)  of  {{{720/2}}} permutations, 
where red shoes are in the right order.

Let denote this subset as  S(6,B).

In the subset  S(6,B),  exactly HALF of its permutations has the "leftRED" item on the left from "rightRED" item.

So, regarding red AND blue shoes, we have the subset in  S(6,R)  of  {{{360/2}}} = 180 permutations, 
where BOTH  <U>red AND blue</U> shoes are in the right order.

Let denote this subset as  S(6,B,R).

In the subset  S(6,R,B),   exactly HALF of its permutations has the "leftWHITE" item on the left from "rightWHITE" item.

So, regarding red, blue and white shoes, we have the subset in  S(6,R,B)  of  {{{180/2}}} = 90 permutations, 
where all  <U>red AND blue AND white</U> shoes are in the right order.

It gives the final answer.
</pre>

<H3>Problem 5</H3>How many integer numbers from &nbsp;0 &nbsp;to &nbsp;999 &nbsp;inclusive have exactly two &nbsp;6s in their records ?

<B>Solution</B>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;This problem has a brilliant, &nbsp;elegant and unexpectedly simple solution.

<pre>
Consider all integer numbers from 0 to 999, inclusive.

In all, there are exactly 1000 such numbers.

Will consider one-digit numbers, like 3, 7 as three digit numbers with leading zeroes  003, 007.

Will consider two digit numbers, like 37 as three digit numbers with leading zero 037.

It will change NOTHING in the solution.

All such three-digit numbers, that have only two digits "6", are in the following three categories:

- having "6" in the first  and the second positions, only;

- having "6" in the first  and the third  positions, only;

- having "6" in the second and the third positions, only.

Now, let's consider all three-digit numbers with the digits 6 in "hundreds" and "tens" position.

The amount of such numbers is 9, obviously, because there are 9 such thre-digit numbers that have 9 possible digits 
    (all excepting 6)  in the "ones" position.

Next, consider all three-digit numbers with the digits 6 in "hundreds" and "ones" position.

The amount of such numbers is 9, obviously, because there are 9 such thre-digit numbers that have 9 possible digits 
    (all excepting 6) in the "tens" position.

Finally, consider all three-digit numbers with the digits 6 in "tens" and "ones" position.

The amount of such numbers is 9, obviously, because there are 9 such thre-digit numbers that have 9 possible digits 
    (all excepting 6) in the "ones" position.

<U>ANSWER</U>.  In all, there are 9+9+9 = 27 three-digit numbers, having only two digits "6" in their records.
</pre>

<H3>Problem 6</H3>In &nbsp;MBA &nbsp;45th batch, &nbsp;40% &nbsp;of the girls are fair and the remainder is brown. &nbsp;Half of the girl are beautiful and half are moderate. 
If &nbsp;10% &nbsp;of the girls are fair and beautiful, &nbsp;and &nbsp;40 &nbsp;girls are brown and moderates, &nbsp;how many girls are fair and moderate?

<B>Solution</B>

<pre>
In the set of all girls in MBA 45th batch, we have 4 subsets:

- F (fair, 40%);

- R (brown, 60%);

- B (beautiful, 50%);

- M (moderate, 50%).

We also are given in-pair intersections

- FB (fair and beautiful, 10%);

- RM (brown and moderate, 40 girls).

From it, the union

F U B = 40% + 50% - 10% = 80%  (fair or beautiful).

The complement for (F U B) is the set RM = (R and M) = (brown and moderate); so it contains 100%-80% = 20%.

From the other side, the set (brown and moderate) is 40 girls;

So, the total girls in MBA 45th batch is  40/0.2 = 200.

+-----------------------------------------------+
    |    OK.  Half of the problem is just solved.   |
    |          Now let' solve the rest.             |
    +-----------------------------------------------+

Notice, that the sought set FM = (fair and moderate)  is the complement 
of the set FB (fair and beautiful) to F (fair).

In other words,  FM = F \ FB.

Hence,  FM is 40% minus 10% :  FM = 40% - 10% = 30%.

30% of 200 is 0.3*200 = 60.

<U>ANSWER</U>.  In MBA 45th batch, there are 60 girls fair and moderate.
</pre>

<H3>Problem 7</H3>There are six available colors. &nbsp;Find the number of ways to color the unit cells of a &nbsp;2x2-grid 
such that no two adjacent cells are of the same color.

<B>Solution</B>

<pre>
Imagine that the cells of the 2x2 grid are denoted in this way

A1  A2

B1  B2

There are 2 basic cases: (a) A2 and B1 are of different colors (and different from A1 and B2),

and
                         (b) A2 and B1 are of the same colors (and different from A1 and B2)

Consider case (a) first.

(a)  For A1, I can use any of 6 colors;

then for A2 I can use any of remaining 5 colors;
          for B1 I can use any of remaining 4 colors;
          for B2 I can use (and I must use) one of remaining 3 colors OR the same color as A1.

In all, I have 6*5*4*(3+1) = 6*5*4*4 = 480 different colorings in case (a).

Consider case (b) next.

(b)  For A1, I can use any of 6 colors;

then for A2 I can use any of remaining 5 colors;
          for B1 I use the same color as A2, so I have no choice;
          for B2 I can use (and I must use) one of remaining 4 colors OR the same color as A1.

In all, I have 6*5*1*(4+1) = 6*5*1*5 = 150 different colorings in case (b).

Cases (a) and (b) are DISJOINT, so the <U>ANSWER</U> to the problems' question is this sum

480 + 150 = 630.

<U>ANSWER</U>.  630 different colorings.
</pre>

<H3>Problem 8</H3>A big cube with the edge size of &nbsp;10 &nbsp;inches, &nbsp;painted throughout, &nbsp;is cut into &nbsp;{{{10^3}}} &nbsp;small cubes each of one inch. 
One cube is drawn at random from the collection of thousand cubes. 
What is the probability that the cube drawn has, 
&nbsp;&nbsp;&nbsp;&nbsp;(a) &nbsp;&nbsp;exactly one side painted 
&nbsp;&nbsp;&nbsp;&nbsp;(b) &nbsp;&nbsp;exactly two sides painted, 
&nbsp;&nbsp;&nbsp;&nbsp;(c) &nbsp;&nbsp;exactly three sides painted, and 
&nbsp;&nbsp;&nbsp;&nbsp;(d) &nbsp;&nbsp;either of the &nbsp;(a), &nbsp;(b) &nbsp;and &nbsp;(c) ?

<B>Solution</B>

<pre>
The number of interior small cubes is  {{{(10-2)^3}}} = {{{8^3}}} = 512.

Hence, the number of exterior cubes is  {{{10^3}}} - {{{8^3}}} = 1000 - 512 = 488.

Of them, 8 cubes are exactly three-sides painted (at the corners);

8*12 = 96 cubes are exactly two-sides painted (along the 12 edges, but not the corner cubes);

and the rest cubes,  488 - 8 - 96 = 384 = {{{6*8^2}}} = 6*64  are one-side painted.

THEREFORE,

(a)  P = {{{384/1000}}} = 0.384;

(b)  P = {{{96/1000}}} = 0.096;

(d)  P = {{{488/1000}}} = 0.488.
</pre>

<H3>Problem 9</H3>I run a book club with &nbsp;n &nbsp;people, &nbsp;not including myself. &nbsp;Every day, &nbsp;for &nbsp;400 &nbsp;days, 
I invite &nbsp;2 &nbsp;members in the club to review a book. &nbsp;What is the smallest positive integer &nbsp;n 
so that I can avoid ever having the exact same group of &nbsp;2 &nbsp;members over all &nbsp;400 &nbsp;days?

<B>Solution</B>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;It looks to be complicated.

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;But in reality, &nbsp;it is as simple as a cucumber, &nbsp;and, &nbsp;in addition, &nbsp;it is charming.

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;When you learn it out, &nbsp;you will gasp . . .

<pre>
Let the number of the members be n.

Then the number of pairs is  {{{(n(n-1))/2}}}.

They want you find the minimum possible n such that

{{{(n*(n-1))/2}}} >= 400.    (1)

So, all you need is to solve this inequality.

Multiply both sides by 2

n*(n-1) >= 2*400 = 800.    (2)

Square root of 800 is  28.2842...

So, your number n is the first integer positive number 
which satisfies (2), and it is somewhere close to 28.

Check n= 28: 28*(28-1) = 28*27 = 756  <<<---=== not enough

Check n= 29: 29*(29-1) = 29*28 = 812  <<<---=== just enough

<U>ANSWER</U>.  You should have at least 29 members in the club to make it possible.
</pre>

My lessons on Permutations and Combinations in this site are

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/Introduction-to-Permutations.lesson>Introduction to Permutations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/PROOF-of-the-formula-on-the-number-of-permutations.lesson>PROOF of the formula on the number of Permutations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/Problems-on-Permutations.lesson>Simple and simplest problems on permutations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Special-type-permutations-problems.lesson>Special type permutations problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/How-many-different-permutations-may-exist-ubder-given-restrictions.lesson>Problems on Permutations with restrictions</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Math-circle-level-problem-on-Permutations.lesson>Math circle level problem on Permutations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/Introduction-to-Combinations-.lesson>Introduction to Combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/PROOF-of-the-formula-on-the-number-of-combinations.lesson>PROOF of the formula on the number of Combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =http://www.algebra.com/algebra/homework/Permutations/Problems-on-Combinations.lesson>Problems on Combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Combinations-problems-with-restrictions.lesson>Problems on Combinations with restrictions</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Math-circle-level-problem-on-Combinations.lesson>Math circle level problem on Combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Arranging-elements-of-sets-containing-undistinguishable-elements.lesson>Arranging elements of sets containing indistinguishable elements</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Persons-sitting-around-a-circular-table.lesson>Persons sitting around a cicular table</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Combinatoric-problems-for-entities-other-than-permutations-and-combinations.lesson>Combinatoric problems for entities other than permutations and combinations</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Fundamental-counting-principle-problems.lesson>Fundamental counting principle problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Miscellaneous-problems-on-permutations-combinations-and-other-combinatoric-entities.lesson>Miscellaneous problems on permutations, combinations and other combinatoric entities</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Some-twisted-combinatorics-problem.lesson>Some twisted combinatorics problem</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Inclusion-Exclusion-principle.lesson>Inclusion-Exclusion principle problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/DERANGEMENT-problems.lesson>Derangement problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/In-how-many-ways-N-distinguishable-objects--can-be-distributed-among-n-different-boxes.lesson>In how many ways N distinguishable objects can be distributed among n different boxes ?</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Stars-and-bars-method-for-Combinatorics-problems-2.lesson>Stars and bars method for Combinatorics problems</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/Men-and-women-standing-in-line-.lesson>Men and women standing in line</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/One-combinatorial-Geometry-problem-solved-using-the-Euler-formula.lesson>One combinatorial Geometry problem solved using the Euler formula</A>

&nbsp;&nbsp;&nbsp;&nbsp;- <A HREF =https://www.algebra.com/algebra/homework/Permutations/OVERVIEW-the-lessons-on-Permutations-and-Combinations.lesson>OVERVIEW of lessons on Permutations and Combinations</A>

Use this file/link &nbsp;<A HREF=https://www.algebra.com/algebra/homework/complex/ALGEBRA-II-YOUR-ONLINE-TEXTBOOK.lesson>ALGEBRA-II - YOUR ONLINE TEXTBOOK</A>&nbsp; to navigate over all topics and lessons of the online textbook &nbsp;ALGEBRA-II.