What Can We Learn from Logic Puzzles and Matching Problems
The world of logic puzzles and matching problems to enhance your problem-solving skills and delve into the intriguing connections between these puzzles, computer science, and decision problems. Unravel complex scenarios involving language proficiency and communication barriers to sharpen your analytical thinking and logical reasoning abilities.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
What can we learn from them? 3/2/2025 1
Outline Introduction What is a typical logic puzzle? How is it related to computer science? Matching Problem What languages can they speak? What are these tennis fans? Cats and Dogs. Who are my family? Boolean Logic Who is the youngest of them all? Who will be hired? McDonald s Addicts. 3/2/2025 2
3/2/2025 3
Introduction Red Ball? Blue Ball? The labels on the bags are all wrong! Can you tell what colors the balls are in each bag by taking out only one ball? 3/2/2025 4
Introduction Red Ball? Blue Ball? What can we know? The labels on the bags are all wrong! / Case 1: Case 2: Answer: Yes! Pick one ball from the first bag. 3/2/2025 5
Introduction Decision Problem A question in some formal systemwith a yes-or-no answer, depending on the values of some input parameters. Common Problem in computational complexity theory theory of computation computer science Shares similarity with logic puzzles 3/2/2025 6
3/2/2025 7
Matching Problem What languages can they speak? Four guys (A,B,C,D) meet at the lobby of a hotel. There are some communication problems when they are trying to make conversations. 3/2/2025 8
Matching Problem What languages can they speak? Among English, French, German and Italian, each of them can speak exactly two languages. However, they cannot find a language that all can speak, and there is only one language that three of them can speak. Nobody understand both French and German. A don t speak English, but B and C need him as an interpreter. C speaks German, D doesn t, but they can communicate directly. A, B and D want to talk, but cannot find a language they all can speak. Can you figure out what languages each of them can speak? 3/2/2025 9
Matching Problem What languages can they speak? Two sets: Key relation: Person & Language speaks 0-1 table can be a useful tool to solve such problems: English French German Italian A B C D 3/2/2025 10
Matching Problem What languages can they speak? Each person speaks exactly 2 languages. There is no language that all of them can speak. there is only one language that 3 of them can speak. Nobody understand both French and German. A don t speak English, but B and C need him as an interpreter. C speaks German, D doesn t, but they can communicate directly. A, B and D want to talk, but cannot find a language they all can speak. 1) ENG FRE GER ITA 2) 0 A 3) B 0 1 1 0 C 0 4) D 5) 8) B = C 6) 7) 3/2/2025 11
Matching Problem What languages can they speak? Each person speaks exactly 2 languages. There is no language that all of them can speak. there is only one language that 3 of them can speak. Nobody understand both French and German. A don t speak English, but B and C need him as an interpreter. C speaks German, D doesn t, but they can communicate directly. A, B and D want to talk, but cannot find a language they all can speak. 1) ENG FRE GER ITA 2) 0 1 0 A 1 0 3) B 0 1 1 1 0 1 C 0 0 0 4) 1 1 D 5) 8) B = C 6) Assume A and B both speak French 7) Is this answer unique? 3/2/2025 12
Matching Problem What languages can they speak? Each person speaks exactly 2 languages. There is no language that all of them can speak. there is only one language that 3 of them can speak. Nobody understand both French and German. A don t speak English, but B and C need him as an interpreter. C speaks German, D doesn t, but they can communicate directly. A, B and D want to talk, but cannot find a language they all can speak. 1) ENG FRE GER ITA 2) 0 0 1 1 A 3) B 0 0 1 1 1 1 0 0 1 0 C 0 1 4) D 5) 8) B = C 6) Assume A and B both speak Italian 7) Answer: Yes! See Previous Slide 3/2/2025 13
Matching Problem Matching Given a 0-1 table representing some relation between sets A and B: if each column and row of the table contains at most one 1 , then this relation is a matching between A and B. if each column and row of the table contains exactly one 1 , then this relation is a perfectmatching between A and B. 3/2/2025 14
Matching Problem What are these tennis fans? Adam, Brian, Chris and David are all tennis fans in a company. Their titles are VP, manager, secretary and intern (not necessarily in this order). 3/2/2025 15
Matching Problem What are these tennis fans? Although the VP always loses to the manager, he plays only with the manager. The manager and intern play better than the secretary. Adam and Brian s offices are next to each other, and they play together quite often. Chris always wins when playing with Adam. The secretary s office is only next to the VP s office. Can you figure out what title each of them has? 3/2/2025 16
Matching Problem What are these tennis fans? The VP always loses to the manager, and they only play with each other. The manager and intern play better than the secretary. Adam and Brian s offices are next to each other, and they play together quite often. Chris always wins when playing with Adam. The secretary s office is only next to the VP s office. 1) VP Man Sec Int 2) 0 1 1 0 0 0 A 0 0 B 3) 1 0 0 0 0 0 1 C 0 D 4) 5) Answer: Yes! See the table 3/2/2025 17
Matching Problem Procedure to Solve Perfect Matching Problem Step 1: find as many exist and not exist relations as possible from the conditions Step 2: fill 0 to all empty cells in the rows and columns that have 1 If there is no empty cell, then stop; If there is any row or column containing only one empty cell, then fill it with 1 , go to Step 2; otherwise, go to Step 1. 3/2/2025 18
Matching Problem Cats and Dogs Families A, B, C, D, and E have pets. Each of them has one dog and one cat. Within the family, the cat and dog get along peacefully with each other. However, every dogs would love to bite cats from other families. 3/2/2025 19
Matching Problem Cats and Dogs One day, every dog bit a cat. All cats got bitten. The cat bitten by the dog from family A is from the family whose dog bit the cat from family E. The dog from family B bit the cat from family A. The dog who bit the cat from family D is from the same family whose cat was bitten by the dog from family C. Can you figure out whose cat was bitten by the dog from family D? 3/2/2025 20
Matching Problem Cats and Dogs Dogs don t bite cats from the same family. Every dog bit a cat. All cats got bitten. The cat bitten by the dog A is from the family whose dog bit cat E. Dog B bit cat A. The dog who bit cat D is from the same family whose cat was bitten by dog C. 1) CatA 0 1 0 0 0 Cat B 0 Cat C Cat D 0 Cat E 0 1 Dog A 2) 0 0 0 1 0 0 0 1 0 Dog B 3) 0 0 Dog C 4) 0 1 Dog D 0 0 0 Dog E 5) (A,x) = (x,E) = 1 (y,D) = (C,y) = 1 6) x = C or E y = E Answer: Yes! Dog D bit cat B. 21 3/2/2025
Matching Problem 3-Matching Sets A, B and C, each contains n elements. Set F contains vectors (a,b,c), a A, b B, c C. F is a 3-matching of A,B and C if: It contains exactly n vectors; Each element in A,B and C appears exactly once in F. Many logic puzzles are 3-matching problem. We may need more than one table to solve them. 3/2/2025 22
Matching Problem Who are my family? There are three families, each has three members. The husbands names are Adam, Brian and Chris; The wives names are Dana, Ella and Fanny; The kids names are Matt, Nancy and Oliver. 3/2/2025 23
Matching Problem Who are my family? Chris is not Fanny s husband, nor Nacy s dad. Ella is not Brian s wife, nor Oliver s mom. Fanny is Matt s mom if Oliver s dad is Brian or Chris. If Fanny is Brian s wife, Dana is not Oliver s mom. Can you figure out the members of each family? 3/2/2025 24
Matching Problem Who are my family? Dana Ella Fanny Husband = {Adam, Brian, Chris} Wife = {Dana, Elle, Fanny} Kid = {Matt, Nancy, Oliver} Adam Brian Chris Matt Nancy Oliver Adam Brian Chris Dana Ella Fanny Matt Nancy Oliver 3/2/2025 25
Matching Problem Who are my family? Dana Ella Fanny Chris is not Fanny s husband, nor Nacy s dad. Ella is not Brian s wife, nor Oliver s mom. Fanny is Matt s mom if Oliver s dad is Brian or Chris. If Fanny is Brian s wife, Dana is not Oliver s mom. Adam 0 Brian 0 Chris Matt Nancy Oliver Adam Brian 0 Chris Dana Ella Fanny Matt Nancy 0 Oliver 3/2/2025 26
Matching Problem Who are my family? Dana 0 Ella 0 Fanny 1 Chris is not Fanny s husband, nor Nacy s dad. Ella is not Brian s wife, nor Oliver s mom. Fanny is Matt s mom if Oliver s dad is Brian or Chris. If Fanny is Brian s wife, Dana is not Oliver s mom. Adam 1 0 0 1 0 Brian 0 Chris Matt 1 Nancy Oliver Adam 1 Brian 0 1 Chris Dana 0 0 1 Ella 0 1 Fanny 1 0 0 Assume Fanny is Matt s mom. Matt Nancy 0 Oliver 3/2/2025 27
Matching Problem Who are my family? Dana Ella 0 Fanny Chris is not Fanny s husband, nor Nacy s dad. Ella is not Brian s wife, nor Oliver s mom. Fanny is Matt s mom if Oliver s dad is Brian or Chris. If Fanny is Brian s wife, Dana is not Oliver s mom. Adam 0 1 Brian 0 0 Chris Matt 0 0 Nancy 0 1 Oliver 1 0 0 Adam Brian 1 0 Chris Dana 0 Ella 1 Fanny 0 Matt Oliver s dad is Adam. 0 Nancy 0 Oliver 3/2/2025 28
Matching Problem Who are my family? Dana 1 0 Ella 0 Fanny 0 1 Chris is not Fanny s husband, nor Nacy s dad. Ella is not Brian s wife, nor Oliver s mom. Fanny is Matt s mom if Oliver s dad is Brian or Chris. If Fanny is Brian s wife, Dana is not Oliver s mom. Adam 0 1 Brian 0 0 Chris Matt 0 0 Nancy 0 1 Oliver 1 0 0 Adam Brian 1 0 Chris Oliver s dad is Adam. Dana 0 0 Ella 1 Fanny 0 1 0 Assume Dana is Adam s wife. Matt 0 Nancy 1 0 Oliver 3/2/2025 29
Matching Problem Who are my family? Dana Ella 0 Fanny 1 Chris is not Fanny s husband, nor Nacy s dad. Ella is not Brian s wife, nor Oliver s mom. Fanny is Matt s mom if Oliver s dad is Brian or Chris. If Fanny is Brian s wife, Dana is not Oliver s mom. Adam 1 0 1 Brian 0 0 Chris Matt 0 0 Nancy 0 1 Oliver 1 0 0 Adam Brian 1 0 Chris Oliver s dad is Adam. Dana 0 1 Ella 1 Fanny 0 Fanny is Adam s wife. Matt 0 Nancy Answer: Yes! See the table. 1 0 Oliver 3/2/2025 30
3/2/2025 31
Boolean Logic Boolean Logic A form of algebra in which all values are reduced to either TRUE or FALSE. Especially important forcomputer science because it fits nicely with the binary numbering system (0 or 1). Powerful tool for reasoning. 3/2/2025 32
Boolean Logic What is Boolean Logic? Operand: TRUE (1), FALSE (0). Operator: AND( ), OR(+), NOT( ). 0+0 = 0; 0+1 = 1; 1+0 = 1; 1+1 = 1; 0 0 = 0; 0 1 = 0; 1 0 = 0; 1 1 = 1; 0 = 1; 1 = 0. 3/2/2025 33
Boolean Logic Properties Commutative: x + y = y + x; xy = yx; Associative: x + (y + z) = (x + y) + z; x(yz) = (xy)z; Distributive. x(y + z) = xy + xz; (x + y)z = xz + yz; De Morgan's laws: x y x = + + = x y x y y 3/2/2025 34
Boolean Logic Who is the youngest of them all? Three kids are talking about their ages. Adam: If Chris is not the youngest, then I am. Brian: If I am not the youngest, then Adam is the oldest. Who is the youngest of them all? 3/2/2025 35
Boolean Logic Who is the youngest of them all? A, B, C stand for Adam, Brian and Chris respectively. Xo means X is the oldest; Xy means X is the youngest. If Chris is not the youngest, then Adam is. Cy + Ay = 1 If Brian is not the youngest, then Adam is the oldest. By + Ao= 1 3/2/2025 36
Boolean Logic Who is the youngest of them all? (Cy + Ay)(By + Ao) = 1 Cy By + Cy Ao + Ay By + Ay Ao = 1 Since Cy By = Ay By = Ay Ao = 0, Cy Ao = 1. Answer: Chris is the youngest; Adam is the oldest. 3/2/2025 37
Boolean Logic Who will be hired? After interviewing 3 candidates, the manager told HR: We need more than one person this time. If we hire Adam or Brian and don t hire Chris, then we want Adam, and we will hire Chris if we hire Brian. Otherwise, we will do the opposite. Can you help HR to figure out whom the manager wants to hire? 3/2/2025 38
Boolean Logic Who will be hired? We need more than one person this time. If we hire Adam or Brian and don t hire Chris, then we want Adam, and we will hire Chris if we hire Brian. Otherwise, we will do the opposite. A = hire Adam, B = hire Brian, C = hire Chris. + A B C + = + A B C + A B C + ( ) ( ) ( ) 1 ( ) A B C 3/2/2025 39
Boolean Logic Who will be hired? + + A B + A B C + = A B C + ( ) ( ) ( ) 1 ( ) C A B C + + ) ( + AB C A BC + + ) 1 = ( )( )( AC BC AB AC + + = 1 ABC AB AC We need more than one person this time. ABC AB = = AC = 0 1 Answer: The manager wants to hire Brian and Chris. 3/2/2025 40
Boolean Logic McDonald s Addicts Adam, Brian and Chris go to McDonald s for lunch every day. They eat only beef burgers or chicken sandwiches. 3/2/2025 41
Boolean Logic McDonald s Addicts If Adam buys beef burgers, Brian will definitely buy chicken sandwiches. 2) Either Adam or Chris will have beef burgers. 3) Neither Brian nor Chris eats chicken sandwiches. 1) Who had a beef burger yesterday and a chicken sandwich today? 3/2/2025 42
Boolean Logic McDonald s Addicts A, B, C stand for Adam, Brian and Chris respectively. Xb means X had beef; Xc means X had chicken. If Adam buys beef burgers, Brian will definitely buy chicken sandwiches. 1 b c A B + = 1) Either Adam or Chris will have beef burgers. A C A C + 2) = 1 b b b b Neither Brian nor Chris eats chicken sandwiches. 1 c c B C + = 3) They eat only beef burgers or chicken sandwiches. X X = 4) b c 3/2/2025 43
Boolean Logic McDonald s Addicts + + + + + A B C A C + + + + ) 1 = ) 1 = ) 1 = = ( )( )( )( )( )( + A ( B B A B C A B C A C A C A C A C B B B A B C A C = C C C b b b c b b c c A c c b c c b b b + ( A C c b b c c c c b b b 1 1 c b b c b c c b c b Adam only eats chicken sandwich, and Chris only eats beef burger. Answer: Brian had beef burger yesterday and chicken sandwiches today. 3/2/2025 44
What have we learned? Discrete Math is a powerful tool to solve logic puzzles. Matching Perfect Matching 3-Matching Boolean Logic Discrete Math is fundamental to computer science. Discrete Math can also be fun! 3/2/2025 45
What have we learned? Discrete Math is a powerful tool to solve logic puzzles. Matching Polynomial-time solvable! Perfect Matching Polynomial-time solvable! 3-Matching NP-complete! Satisfiability (Boolean Logic) NP-complete! Computational Complexity is in the foundation of computer science. Computational Complexity is can also be fun! 3/2/2025 46
