Basic Combinatorics

Hello people its Rishad again. Yes I'm still alive. Now I am back here with another post (after an eternity). 

This post is just about very fun questions from combinatorics. This post is not going to have really "high level" content. For some this might be just fun puzzle solving (experienced olympiad people) while for those who are starting off and who have little exposure to olympiad combinatorics will have exposition to some really fun mathematics. The questions are just sort of puzzles and not much mathematical knowledge is required to solve them. 

Some warmup before we go to solving the main set of questions. I will just be providing the answers to these questions you have to do these questions on your own. 

Q1. A number of bacteria are placed in a glass. One second later each

bacterium divides in two, the next second each of the resulting bacteria divides

in two again, et cetera. After one minute the glass is full. When was the glass

half-full?

ANSWER: 59 SECONDS. 

Q2. Jack tore out several successive pages from a book. The number of

the first page he tore out was 183, and it is known that the number of the last page

is written with the same digits in some order. How many pages did Jack tear out

of the book?

ANSWER: 136 pages were torn. A page has two sides this implies that if the first page he tore off was odd then that would imply that the last page he would tear off will have an even number written on it. The only possible number that can be formed is hence 318. So the total pages he tore are 318-183+1=136. 

Q3. In a certain year there were exactly four Fridays and exactly four

Mondays in January. On what day of the week did the 20th of January fall that

year?

ANSWER: Sunday 

Q4.Pete's cat always sneezes before it rains. She sneezed today. "This

means it will be raining," Pete thinks. Is he right?

ANSWER: NO. The occurrence of rain is in no way related to the sneezing of Pete's cat. 

Q5. Three scholars are riding in a railway car. The train passes through a

tunnel for several minutes, and they are plunged into darkness. When they emerge,

each of them sees that the faces of her colleagues are black with the soot that flew in

through the open window. They start laughing at each other, but, all of a sudden,

the smartest of them realizes that her face must be soiled too. How does she arrive

at this conclusion?

Solution: Let P_1, P_2, P_3 be the three scholars and let P_1 be the person who understood that her face was black with soot. If that would not have been the case then P_2 would realize that her face was soiled in black soot. But since they never stopped laughing hence P_1's face should be black as well. 

 Some other Problems:

Q1.  Is it true that every positive integer can be multiplied by one of integers 1, 2, 3, 4 or 5 so that the resulting number starts with 1?

Motivation: The question tells us about the significance of the first letter of the number. So we can safely assume it (also the first digit of some number has only limited values $\in$ {1,2,3,4,5,6,7,8,9}.

Note as the numbers start getting bigger the choice of integers reduces from 1,2,3,4,5 to a smaller set because if we multiply bigger numbers to the positive number then it will be increase in size and there will be a carry over of 2 which means that the first digit after multiplication won't be 1. 

Solution: Assume that the first digit is x. Clearly x=1 $\implies$ we can take the integer 1 to get 1 in the first digit of the number when we multiply both numbers. For x=2 , the integer 5 works, For x=3, the integers 4 and 5 both work. For x=4 ,the integers 3,4,5 work. Notice that for all bigger numbers i.e. x=5,6,7,8,9 the integer 2 works well. 

Pigeonhole principle: 

It might seem like a joke when I state this thing but it's not. It's a fairly obvious principle yet has extensive applications. In fact the beauty of this principle lies in its simplicity. It goes like:

If there are N+1 pigeons and N pigeonholes then one of the pigeonhole has "at least" 2 pigeons.

Note: Instead of N we can have any multiple of N. Think why??

Problem solving tip: Think of categories and think of things to put in those categories when you do the questions. I hope this makes more sense as we proceed with the problems. 

Q2. Show that in any group of five people, there are two who have an

identical number of friends within the group.

Motivation: Pigeonhole principle: if there are n+1 pigeons who have to be kept in n pigeonholes then there are at least 2 pigeons in one hole.  The category here can be the number of friends a person has. Basically, number of friends a person has is the defining property of a person in this group. 

Solution : A person can have a maximum of 4 friends and a minimum of 0 friends but that is a contradiction hence there are only 4 options for 1 person( the person can have 1 friend 2 friends 3 friends or 4 friends or person has 1 friend 2 friends 3 friends and 0 friends) however there are 5 people so by pigeonhole principle( I could've written PHP but I generally don't prefer writing shorthands).

Q3. Given twelve integers., show that two of them can be chosen whose

difference is divisible by 11.

Motivation: "Divisible by n" this phrase is  kind of suggestive for the use of remainders modulo n(=11, here) 

Solution: Clearly we have 11 possible remainders when we divide any number by 11. Now since we choose any two of them $\implies$ there will atleast be 2 numbers which have the same remainder and when we take their difference the remainders get cancelled hence the difference becomes divisible by 11. 

Q4. The city of Leningrad has five million inhabitants. Show that two of

these must have the same number of hairs on their heads, if it is known that no

person has more than one million hairs on his or her head.

Motivation: We have done questions from only pigeonhole principle so far. Just think of pigeonhole again. 

Solution: So see now it's possible for a person to have zero hairs to 1 million hairs. Now since there are much more people than 1000001 hence by pigeonhole principle we can easily get that there are more than 2 people in one category. 

Coloring Argument: 

Again a very simple thing but the solutions we can get out of coloring arguments are beautiful. Chessboard is colored right. In black and white similarly its a very common technique to introduce coloring onto the board we are working with. 

Q5.Can a 5 x 5 square checkerboard be covered by 1 x 2 dominoes?

Motivation: Color the board white and black(neighboring squares are of opposite color ,neighboring means those which are sharing a a side). Checker board, chessboards these are a hint that we might want to give coloring arguments a try ( along with dominos and all). 

Solution: No matter what happens 1×2 domino will always cover 1 black and 1 white square. But WLOG(Without loss of generality).Say number of black squares will be 1 more than white squares (this is going to happen because there are odd number of total squares)

Hence, it is not possible to lay down 1×2 dominos which cover 5×5 checkerboard.( The number of square should be even because domino will always cover squares of different colors in pairs). 

Q6. Can an ordinary 8 x 8 chessboard be covered with 1 x 2 dominoes

so that only squares A1 and H8 remain uncovered?

Motivation: Coloring has to be done as has been done in the question above. The question asks us about particular squares and since we have done coloring it makes sense to find out the colors of the the squares A1 and H8. Clearly they will be of the same color. 

Solution: NO this situation is not possible since there are equal number of white and black colored squares hence if two squares of same color ( without loss of generality we can say white ) are left at the end then that would mean that we colored more black squares than white which is not possible with a 1 x 2 domino. 

Q7.Two children take turns breaking up a rectangular chocolate bar 6

squares wide by 8 squares long. They may break the bar only along the divisions

between the squares. If the bar breaks into several pieces, they keep breaking the

pieces up until only the individual squares remain. The player who cannot make a

break loses the game. Who will win?

Motivation: The above mentioned game is asking the players to do something repeatedly i.e. there is some kind of process going on. All you have to do is to extract information out of this process. If possible try to visualize the process going on here in your head. 

Solution: The person who starts the game is going to win always. Notice that there are 48 squares. Suppose that one person starts with breaking off the first square. Then in 47 steps we can see that the process has to stop because no more breaking will be possible after that. Since we know that every odd step will be taken by the first person we can say that since the second person will not be able to break off the last piece hence the second person must always lose. 

Here are two other puzzles which are veryyyyyy cool. I personally like them a lot. 

Q1. (The Census Taker Problem ) A census-taker knocks on a door, and asks the woman inside how many children she

has and how old they are.

“I have three daughters, their ages are whole numbers, and the product of the ages is 36,” says the

mother.

“That’s not enough information,” responds the census-taker.

“I’d tell you the sum of their ages, but you’d still be stumped.”

“I wish you’d tell me something more.”

“Okay, my oldest daughter Annie likes dogs.”

What are the ages of the three daughters?

Hint: Read the dialogues carefully. 

Answer: 2,2,9 are the ages of the daughters. 

Q2. A monk climbs a mountain. He starts at 8 AM and reaches the summit at noon. He

spends the night on the summit. The next morning, he leaves the summit at 8 AM and descends by the

same route that he used the day before, reaching the bottom at noon. Prove that there is a time between

8 AM and noon at which the monk was at exactly the same spot on the mountain on both days. (Notice

that we do not specify anything about the speed that the monk travels. For example, he could race at

1000 miles per hour for the first few minutes, then sit still for hours, then travel backward, etc. Nor

does the monk have to travel at the same speeds going up as going down.)

HINT: What if this monk has a friend ?????

Answer: Assume that there is a second monk which walks in the exact same way as the first monk did and this monk has to start when the first monk starts the descent. Clearly they should meet at some point and that is point we are looking for right?? This is like adding a dummy variable in the problem whose only aim is to solve the problem and does not play any role directly in the answer. 

P.S. Now I am planning to write the next few posts on real analysis( starting from sequences) and calculus. So Yayyy!!