Lesson In the worst case

In the worst case

Problem 1

3 + 1 = 4.    ANSWER



In the worst case,  your first 3 socks will be of three different colors;


but then any taken fourth sock will match with some of the three previous socks and will create a pair.

Problem 2

In the worst case, you will take 1 red, 1 blue, 1 green, 1 yellow and 1 purple marble.


After that, whichever other marble you will take from the box, you will have at least 2 marbles of the same color.


ANSWER.  6 marbles.

Problem 3

In the worst case, we should take all blue cards (2) and all green cards (3).


    2 + 3 = 5.


After taking the 6-th card we inevitably will have at least one red card,

and after taking the 7-th card we inevitably will have at least two red cards.


ANSWER.  After taking 7 (seven) cards we inevitably will have at least two red cards.

Problem 4

In the worst case, you draw 2 blue and 3 green cards (in any order).


Then, whichever 2 cards you draw after that, you INEVITABLY will draw 2 red cards.


So, after drawing (2+3) + 2 = 7 cards you are GUARANTEED to have 2 red cards.


ANSWER.  Whatever (2 + 3) + 2 = 7 card you take from the box, at least 2 of them will be red.

Problem 5

In the worst case scenario,  Toni will pull out 4 identical red socks,  7 identical blue socks and 7 identical green socks,

but still will not have 4 pairs of the same color.


Notice that         4 + 7 + 7 = 18   socks.


But then,  had Toni pull out anyone of remaining socks from the drawer,

this  19-th sock will create four pairs of identical socks,  either blue or green.


Therefore,  the least number of socks that Toni needs to pull out to be sure of having  4  pairs of the same color is  19.

Problem 6

The answer to the first question is  3 songs.

Among any 3 songs from the given set, at least two INEVITABLY will be of the same genre.



The answer to the second question is 30 songs.

It is because in the worst case I will be forced to listen 29 R&B songs, in a row.

Problem 7

It is a nice entertainment problem, and if you solve it for the first time in your life,
it is better do it step by step.


1) How many socks should he take to be sure that there is at least one good pair of the same color ?            

                                                                                                          
       In the worst  case, he will take 5 socks of different color,
                                                                                                          
       but any 6-th sock will match with one of 5, just taken.

       So, 6 socks is enough in this case.



2)   How many socks should he take to be sure that there are at least two good pairs of the same color ? 


       In the previous case, worst case was 5 socks of different colors.

       After adding any 6-th sock, we have one good pair and match,

             but still may have 4 remaining socks of different colors.


       So, we should add the sock #7 to create possible worst case, and then add #8 to have a match guaranteed.

       So, the answer in this case is 8,  which is  "add 2 to 6".


3)   After that, the pattern is clear: to provide next match, we should add 2 socks from the drawer after every previous match.



4)  Following this pattern, I create the table below


        # of matching pairs    1    2     3    4     5     6     7     8     9     10     11

        # of socks to take     6    8    10   12    14    16    18    20    22     24     26


5)   ANSWER.  26 socks.

Problem 8

Let the points on the circle are numbered consequently from 1 to 18, inclusive.

Let call them  , , , . . . , .


Notice that if a rectangle is inscribed in a circle, then its diagonals are DIAMETERS
of the circle. So, the opposite vertices of the rectangle are the opposite points on the circle.


Thus, diagonals of our rectangle connect opposite points on the circle.


Of 18 points , , , . . . , , we have 9 pairs with opposite points
(,), (,), . . . , (,).


Now my statement is that the ANSWER to the problem's question is 11 points of 18.


Indeed, among these 11 points, there is at least one pair of opposite points.
Removing this pair, you have remaining 16 points and 11-2 = 9 selected points.
Among these 9 selected points, there is at least one another pair of opposite points.

So, 11 points are ENOUGH, even in the WORST CASE.


From the other side, taking 10 points , , , . . . , , it is clear, that
among them, there is ONLY ONE pair (,) of opposite points to make a diameter/(=a diagonal),
and there are NO points to make another pair/(=another diagonal).



ANSWER.  11 points are needed to choose to GUARANTEE 
         that you will have the four corners of at least one rectangle.