Oh, hi everyone. Yes, this is a warm-up question. So, there are 223 red buttons, 117 white buttons and 28 blue buttons. Each student is asked to take out and keep a button from the box without looking. How many students have to take out a button to be sure that at least three buttons of the same color are taken out of the box? And yes, this is for those who came early. And I got the answer as 7C, which is the correct answer. Because the big numbers got confused us, like all these big numbers. But we think clearly, then we have three choices. And in the worst case scenario, if we are really unlucky, we would take two red, two white and two blue. The first six ones, if we are really unlucky, we're going to take two of each color. But then the seventh one, we're going to be sure to take one of the three colors. And for the seventh one, we're going to be sure to have three buttons of the same color. And that's today's topic, logical reasoning. We're going to deal with these types of questions. OK, so let's get started. So logical reasoning is not something like this type of logical questions, that's something that we deal with on a daily basis, like algebra. But they are very common, especially in math kangaroo competitions. So just quickly go through the types of logic problems, the most common types of logic problems. You've probably seen this before, the pigeonhole principles, right? If we have more pigeons than holes, then we are be sure to have at least two pigeons in the same hole. And lots of problems that use the pigeonhole principles usually ask for a minimum quantity of something, right? To make sure that a certain event will happen. Then probably the most popular types of parsers that you see a lot in lower grade logic reparsers, in which you have to match two list items to item, right? In this case, four people have to match with four animals. Sometimes maybe one person can speak two languages out of four, things like that. And for questions like these, actually they turn out to be quite straightforward, right? The matching table most of the time helps you solve the problem. Then we also have types of problems that have a list of statements, describe a specific situation and give a list of statements. And based on the statement description, we have to determine whether certain statements are true or false. And then we have one very popular type of problems and maybe quite unique in math kangaroo compared to other competitions, are the nice and liars problems. So you always have a nice who always tell the truth, while the liars always lie. Sometimes we have tourists like us, right, who sometimes will tell lies, sometimes tell the truth. And we usually do not know who are which. And based on what they say, we have to find out who are nice and who are liars. So in terms of problem solving strategies, you pretty much expect anything. But one common tactic is prove by contradiction. We assume a particular statement is true and then go through from that starting point and use logical reasoning and to see if that leads to any contradictions. So we are looking for either contradictions or consistencies. And then we use casework as well to list out all different possibilities. And these are often used in conjunction with proving by contradictions. For example, if we are asked to show that in an island of nice and liars, no one will say that he's a liar. So we can just go to two simple cases. Case one, if he's a knight, but a knight cannot say I am a liar. So that's a contradiction. So he's not a knight. And case two, suppose that he's a liar. But then the statement I am a liar is true. Again, contradictions. Therefore, no one in this island would say that he is a liar. Then other problem solving strategies that we talked before are super helpful for logic problems as well. So a smaller version of the same problem where people have a thousand knights and liars, we don't know what to do. Then we might as well just assume smaller numbers. Number parity, odd and even, these are some of the hardest problems required using number parity and without explicit thinking, so we just have to figure it out ourselves. Then the way we represent, we summarize and represent our information as well as present our reasoning is also very important in logical questions. And drawing a table, a diagram, such as a Venn diagram or graph to organize information is also a very common strategy. Then sometimes we just have to construct a solution and show that it is the only solution that satisfies all of the given conditions. And since Math Kangaroo is MCQ exam, then definitely eliminate the obvious wrong choices is also a very useful strategy. Okay, so let's get started. More like a warm up questions. There are 17 balls in a bag. Each ball has a number from 1 to 17 on it. We randomly pick a ball from the bag. What is the smallest number of balls we have to pick in order to be sure that we have at least one pair of balls with a sum of the numbers equal to 18? So 1 to 17. So the sum of two balls has to be equal to 18. So it seems like similar to the warm-up question, we have to think about the worst case scenario. We describe what's the worst, and then we prove that if we do one more balls than that, we would definitely get a pair whose sum is equal to 18. So first, let's do a trial and error. First, find that critical number and increase one more. Oh, it looks like most people already figured out. So I just started by listing all the number, right? One, two. Oh, that's where we list in the way that the sum are equal to 18. So one plus 17. So we have a 117 unit in pairs and 216, right? We want to listen this way and all the way to what would be eight and 10. So we have eight pairs and number nine that stick out, right? So in the worst case, we would get one from each pair. We don't know, it could be here. If we get two from each pair, then we are all set, right? But suppose we are lucky. We've got one from each pair. I don't know which, but it could be 116 and then could be another one here. So we get eight numbers, one from each pair. And then suppose we're even more lucky then that we got nine as well. So that's nine numbers. Yeah, so, but if we got nine numbers, then the next one, the 10th one, we are be sure to hit one of these, right? The left over from one of the pairs. So we're gonna be sure to get the sum of 18. So the answer is C. So this is another application of the Dixon-Ho principle, right? Okay, good, let's go to another one. There are some squares and triangles on the table. Some of them are blue and the rest are red. Some of these figures are large and the rest are small. We know the following two facts are true. First, if the figure is large, then it is square. And second, if the figure is blue, then it is a triangle. And now we have to determine which of the statements A to E must be true. So let me, so the balls have two, the figures are squares and triangles, blue and red, right? And large and small. So it's like lots of information and this question really tests on how we can organize information in a neat way. By the way, today David went to the Caltech math meet for high school students in Pasadena and he got caught up in the road so he couldn't make it on time back to San Diego. You can either go through each statement or you can just forget about the statement. Just draw a table of diagrams to represent information and from there make the conclusions and don't bother about the statement first because sometimes it might be confusing. So choose a strategy for yourself. Good that I had only A and E as the answers, I don't have B, D, C. So for example, if you look at this, right, large, if the figure is large and it's square, then we know that large is a subset of square, right? Okay, so a Venn diagram like this is helpful. Large is subset of square, and then when you say that all square are large, then you see the other way around, square is actually a subset of large, right? So then we know right away B is not true, and same D, for two, blue is subset of triangle, and here triangle is subset of blue, right? So sometimes you can use elimination and eliminate obviously wrong choices, but the others are not as obvious. What is that, you could hear like set and subset, also important concepts that come up a lot in law sheet questions. OK, so let's do it together. So we have two objects, the squares and triangles, and they both have two properties, colors and size. And then I would say, oh, maybe I use tables. They have rows and columns, and maybe that would help me organize information better. So let's try it. Like we can have, after we have a blue and red and large and small, we go to, what do you know? If the figure is large, then it is square, right? So that means over here, I'm on this rows of large. I can only have square. I cannot, I'm not allowed to have triangles, right? So that's one way to do it. It's not the only way, but it's sort of a very neat way to summarize the problem statement. And similarly, you look at the column, they say that if the figure is blue, then it is a triangle. That means if I go in this column over here, I can only have triangles. And I have triangles here, but then that means this one is out. I'm not allowed to have squares in the blue column, right? So this one is out. And that's it. So this table, very simple table, but it captures everything we have in the question. And it says nothing about the cell. So in the cell, we are allowed to have both of them. We don't know, right? We don't know what we have. So in general, there might be both. And once you have this table here, that would be easy to go through the choices. All red figures are squares, so I go to red. No, we could have triangles, right? So A is not correct. B, all squares are blue, so I go here. All squares are blues. But no, I can have a square that are red. As we said earlier, B cannot be true. All small figures are blue, then I go to blue here. And oh, I have a small triangle, so C is not correct. And similarly, D, not correct. And the only things that are all blue figures, as we can see here, are small. So the answer is E. Great, some of you figured it out, yes. So that's great. I mean, this question really, there are many different ways. As you can see, B and D, you can do by elimination. ICs are not so, but really just drawing a diagram, a very simple diagram, right, and captures all the information needed. Let's go to the next one. Now, a question with liars and lies. An underwater kingdom is inhabited by creatures with either six, seven, or eight arms. Those with an odd number of arms always lie. Those with an even number of arms always tell the truth. One day, four creatures met. The blue creature said, together we have 28 arms. The green one said, together we have 27. The yellow said, 26 arms. And the red said, together we have 25 arms. How many arms did the red creature have? So you can call it nice and nice, liar and truth, I usually just stick with one notation. So over here, they say that the odd one also lies, so seven, we label him as L, and six and eight are even, so this is another way that we want to summarize the information like this. Since these are two and two. And then. So that's what I do, I do six, seven, eight, two truth liars and these four statements. So, I have B and E as the answer. Be careful with E because when you say it's impossible to determine easily, that statement is actually a very strong statement like, oh, this question cannot be solved or this result cannot be proved. In Maths Big X, it's a very strong statement, so it could be, but actually it's pretty hard to show that something is impossible. So usually for logic question, like some observation, I mean, you can do it the long way, but some observations we have cut down the amount of computation, right? Oh, it's good. I have more and more answers coming in. So the first observation that these answers are all different, you notice that, right? 28, 27, 26, 25, they're all different. That means they cannot be all true, right? They could all be the one liars, so we would have cases. So we could have case one, four liars, right? Or case two, three liars and one suit tellers, right? Because we cannot have two suit tellers. So if it's a four liars, then four liars, we know that the liars have seven arms, right? So if there's four liars, that means 28 arms, but 28 arms means blue is true because he's telling, he's saying true. So this is an example when we run into what contradiction, right? So contradiction, so basically it's just not correct, so this case is not correct. And then we are settled with case three, case two, three liars and one suit tellers. We don't know who is whom, but because we know that each liar has three arms, so when we know for sure that three liars, then we know that there are 21 arms over here, right? And then the suit liars, we can either plus six or eight, right? So it could be 27 or 29, right? And one of them is a suit teller, so one of them have to say these results. If you look at over here, then green is going to be one who telling the suit and everyone else is a liar, right? And from here, the answer is B, red has seven arms, he's a liar. That's the contradiction casework and some observations that makes us find the solution faster. Okay, good. Let's go to another question with one more, because these are really representative. So we do two questions on liar and liars. There are 2014 people standing in a row, each of them is a liar or a knight. Each person says, there are more liars to my left than knights to my right. How many liars are there in the row? Very vocal, right? Everyone has their statement. Everyone says exactly the same thing. pay special attention to the word, like there are more lines to my left than to my right, right, so that has something to do with directions. So as you can see that example, a very big number, 2014. That's a lot, right? So don't worry about the numbers. It's bigger, smaller numbers. And we are talking about the standing in a row. So you can check like one person at a time from the beginning of the row. Just work with a few numbers, few specific cases to see if you can find any patterns. And the nice thing about the question is that once you get one of the answer you can sort of easily check whether I have B, C, D at the end, so let's start with the first person, let's apply our strategy like small numbers and see if we can figure out anything. So suppose we do case work, right, so suppose the first person is T. If the first person is T, then there's zero layers on his left, and there might be something, right, to tell on the right, the T bigger or smaller than zero, right. So the statement, there are more layers to my left than layers to my right, is a false statement, but he is a knight, right, so this is contradiction. So that means the first person in line has to be a liar, right. So this is the first person in line, going like this, left to right. And similarly, so if I have the first person is liar, I go to the second one. Suppose he's a truth teller, then there are more persons, there's one liar here, that means there's zero T on the right, right, so everyone here has to be liars. So everyone has to be liars, and we go to this person here, he says that he has one liar on the left and zero truth teller on the right, so this statement is actually true, but he is a liar. So again, we run into contradiction, so not possible, and that means the second person in line has to be a liar. And we haven't done anything complicated, we just check the first two cases, but already we see some sort of patterns, just liar, liar, liars. I don't know when this will continue to how many of them, so a very common thing in mathematics is that like, well, let's assume that I have a certain number of liars here, and maybe I consider the first person who is a truth teller. What's so special about this person, what makes the switch between L to T, right, given that in the beginning I have only L, so that also like, you know, like phase transitions or certain change, that's also something that are common. So suppose you have this, and then let's call this is M, now over here we have M, L, and maybe I have on the right have an NT, right, of this person, and we know that M must be bigger than N, right, that's because he's telling the truth. But as we go, as we go to the right of this person over here, then M doesn't decrease, M can stay the same, or it can only increase, there could be more liars, and N, it doesn't increase, right, it can stay the same, or it decreases. So that means this statement, M bigger than N, more liars to my left and N to my right, it's always true. Once it's true for a person, it's gonna be true for everyone behind him, right. So that means we would have a pattern of this, we just have a liar, liar, liar, liar, and two teller, two teller, two teller, they're standing like this, and now we are only left with the task to determine how many of them here and how many of them here, right. I think some of you got it correctly, you could go from the end of the line as well, from right to left, and then you could also find the same patterns, and the majority you big C, which is correct answer, one of you pick D, which I think probably you should off by one, right, because it's D here, it's 100, 1008, and 1006 here, then for this person, there would be 107 liars, bigger than 1000, and two tellers, so that must not be the case, and the correct answer is 1007. And for some of you who chose B, the first answer, you can, you can, you can check, right, I mean, over here, you can check B and E, you can, A, B and E, you can sort of eliminate, and we really just were wondering between C and D. Okay, good, let's go to the next one, change to different types of logic questions, there's this one. In a tennis knockout tournament, six of the results of the quarterfinals, the semi-finals, and the final were not necessarily in this order. Bella beat Anna, Celine beat Donna, Gina beat Holly, Gina beat Celine, Celine beat Bella, and Emma beat Farah. Which result is missing? So many names, but we can really see that it's A, B, C, D, right? So, A, B, C, D, E, F, G, H. So, we know that's eight names. And we have... So, when you read questions like that, it just takes some time to, you know, just to check if everything makes sense. And seven matches, or eight people, seven matches. And since that means the quarterfinal has four, the semi has two, and the final has one. It just takes some time to check, double-check the information. Some people already got their answers. Everyone else just continue working. So we have a six matches here. And I think we just summarize it using initials. And you see, you may come up with some sort of nice reasoning or one way to try to see if you can put these matches in these three routes, sort of more like construct the solution. Oh, good. So I think we can finish up here. So we see that we have a B, A, C, D, and then we have a C, B here. So it looks like the first quarter finals would be B and A, C and D, and then we have G and H, and E and F, right? And then, because B and C are winners, they go to the next round in which C beats B, and we don't know about G and H, right? G and H are winners, but the last one we have G and C. You see that here, G and C, so that's the final, so the winners are C, and that means G has to beat E in the, this is our missing one, G has to beat E in the semi-finals. Yes. Correct, yeah, so most of you got the correct answer. The last one here. Anyone has a different ways of reasoning, you can send me to the chat. We have another way we can think about it, it's like, I would say that this problem is the most straightforward way to solve this problem, but we know that we have 7 matches, and 7 matches, that means we have 7 losers, right, because the loser cannot continue, and over here, we have A, we have A, D, H, C, D, F, they are the losers, right, and we have no mentioning about Emma, then we can just check these two cases, Emma and Gina, right, they are missing from the list of losers, so we can just check, that's another way. So yeah, all kinds of different, very non-standard methods to solve logic questions, but I think it's very refreshing to have these types of questions in the exam, in addition to all the number of questions. Another one, looks like we have a lot of time today. Emma has 8 coins whose weights in grams are different positive integers. When Christina puts any two coins on one side of a balance, and any two on the other side of the balance, the side containing the heaviest of the four coins is always the heaviest side. So what is the smallest possible weight of the heaviest coin? So what we do here, we put, he has 8, she has 8, and she puts any two, and any two on one side, and the heaviest of the four is always on the heavier side. And smallest possible, so this is another very common thing, like smallest number, biggest possible values, things like that. These are some very common quantities, questions that arise in logic problems. You have eight coins, but you can just initially take four, play with the four, see if you can find any properties. You can play with specific numbers. That's also a very useful strategy. And another thing that I forgot to underline that these coins, they have different positive weights, they have different positive integers, right? Yeah, very important, and I forgot to underline it. So for example, you can start with four coins. You can start with four coins, first A, just like you A, A, B, C, D, but because they are of different values, then I can order them, right? So just consider four of them, A is smaller than D, and see what you can figure out, what property you can find out about A, B, C, D, because you know that once you put any two of them on one side, any two on the other side, the heaviest coin is always on the heavier side. That statement will help you to determine some certain properties about A, B, C, D, and it's hard for you to find it out in general. Take four numbers, take four numbers, that would be very helpful. Yes, so I already got one correct answer. Some students send me a list of eight coins that work, but remember, we are looking for the smallest possible weight, right? Not just any weights that work. Okay, so it looks like we make some progress here, so let's get started. So I start with A, B, C, D, then if I take D and C, right, then definitely it's going to be on the other side. The only thing, when I consider these four coins, the only thing that I have to consider is A, D plus A. That has to be bigger than B plus C, right, so that I can be sure that D is always on the right side of the balance sheet, right? Once this is satisfied, then D plus B or D plus C is always on the other side, right? That's the only thing that means, and to make it small, then I make B plus A just like one bigger than B plus C. So we can take some small numbers, right? We can check, for example, I want to do one, two, three. We do one, two, and three, then we realize that the fourth number cannot be four, right? Because four plus one is five, which is two plus three, so the fourth number has to be five. That's smallest, right? And this is just a specific example, but right away, it's sort of really leading us to the right path, right? Because they say, what is the smallest possible weight of the heaviest coins? So we are free to choose the first three, which we have three degrees of freedom, right? One, two, three. It really doesn't matter. We can start with the smallest and work our way up from there. And once these three are fixed, then I can just build it up using the smallest numbers that satisfy the conditions, so I know that five is good. What about the next number? I may think that three and five is eight, and so I have a six here, right? Because six or seven, I may think it's a seven, because seven and two is nine, and three by five is eight. But we got to be careful, because the question says it's any four coins, right? So that means I have to don't forget about the lightest of all, which is one. So I have to take three and five, which is the second heaviest one, and that has to be smaller than seven plus one. So I take this one, and then it's eight, right? So this number here cannot be seven, it has to be eight, because the plus one. So you can see the pattern, right? So now I have a five, eight is 13, and this number has to be 13, so that when you add one, it's going to outweigh these two. And by now, have you recognized what sequence it is? Yes, yeah, I think you recognize it, it's the Fibonacci sequence, right? So this is 21, and the next one is 34. Yes, it's the Fibonacci. So, you know, that's a nice thing with logic questions, you get a number, you don't even know where to start, and you always think that maybe there's a trick there. But all our problem strategy, like start with small examples, specific, and things like that, you'd actually work most of the most of the times. Yeah, so don't give up, just come back to the basic, go through the list to see if anything you can use to solve the problems. Let's go to another one with, oh, sorry. We have two more to go. No, we already did two questions with Taos, Lai, and I, so I think we are good with this. Let's go to this one. There are some necklaces in a safe deposit box. All the necklaces have the same number of diamonds, and there are at least two diamonds in each necklace. If the number of diamonds in the safe deposit would be known, then the number of necklaces would also be known without doubt. The number of diamonds in more than 200, but less than 300. How many necklaces are there in the safe deposit box? It's more like a detective case with the Sherlock Holmes flavor here. So if the number of diamonds is known, then the number of necklaces would be known without doubt. So what does it mean? So, we have two unknowns, the number of necklaces and the number of diamonds. And we talked about last time, we could use algebra in any situation that involves unknowns. Maybe that would be a good use of algebra if we want to give variables to each of these two unknowns to see what we can figure out from that. So we can, yes, let's try algebra. Let's call the number of necklaces, and the number of diamonds in each necklace, right? And in each necklaces. See what we can get from these numbers. Oh, good, I've already started having answers. And we know the constraints that the number of diamonds, which is n times d, is smallest than 200 and bigger than 300. The number is bounded in this range, right? 200 and 200. And from here, we have to figure out what n is. And the thing that we know is that if this product is known, then n would be known without doubt. And what does it mean? So we know the product of two numbers, right? So suppose the product, suppose that n times d is 250. If we only know this, can we figure out n and d uniquely? Right? So that top, if we have, then we say, oh, I don't know, I could have n equal to five, or I could have n equal to 10. I don't know, right? And the only thing, then d in both case bigger than two, so I have no trouble. So in this case, it's not unique, right? It's not unique. Because I have two choices. So I hope that provides enough hints by now for you to get to the answer. So it looks like this number should not have, you know, too many factors, right? And we kind of sort of guess it, that the numbers, the product must be some, must be a product of two prime numbers. So we cannot factorize too much. It would be a prime times a prime, right? And then in this case, because we cannot, we don't use the one, the number two, and the prime numbers times the prime numbers. But even with this, if I have prime number p, it will have a p times q, right? P times q, then we also have two choices. n could be p or n could be q, right? And the question say that the number is uniquely determined. So from here, we actually have a stronger statement. It must be the two prime numbers actually has to be the same, right? So that product is gonna be just equal to p squared, when p is a prime numbers, and it's bounded between 200 and 300. Yes, I think most of you got it by this term. And then the only numbers that satisfy this condition is 17. And that would be our answer, 17 is 289, yes. So that would be our answer, yeah, 17, which majority would guess. So as you see, like logic questions come in all different shapes and size. We have some typical questions like liars, nice, but it could be anything, but don't be discouraged. Sometimes you think that, oh, there's a bottleneck that I have to get through. But most of the time, as you can see, if we can just do it systematically, go through all the problem-solving strategies that we discussed, then you would believe that you could find the answer. And read the question carefully, it's very important, underline important information Some of you got the correct answer, but like off by a bit because you didn't read the question carefully. And I myself didn't underline important points and use the graph tables and how to summarize information, how to organize is also extremely important in lengthy questions as in logics. Okay, so thank you everyone. And we look forward to seeing you next week when we will be working on numbers.

logical reasoning

pigeonhole principle

math competitions

problem-solving strategies

worst-case scenario

knight and liar puzzles

tennis tournament

logical deductions

Fibonacci sequences

methodical approach