Exploring Discrete Mathematics for Computer Science and Geometry
Dive into the world of discrete mathematics for computer science with Prof. Shachar Lovett. Learn about recurrences, domino tiling, and geometrical theorems. Understand the Fibonacci sequence, interior angles of polygons, and more in this immersive study session.
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
CSE 20: Discrete Mathematics for Computer Science Prof. Shachar Lovett
2 Today s Topics: 1. Recurrences examples
3 1. Domino tiling
4 Domino tiling A board with 2 rows and n columns How many ways can you tile it with 2x1 dominos (all identical)
5 Domino tiling Example: n=1 One way
6 Domino tiling Example: n=2 Two ways
7 Domino tiling Example: n=3 3 ways
8 Domino tiling Example: n=4 A. 3 ways B. 4 ways C. 5 ways D. 6 ways E. None of the above
9 Domino tiling Example: n=4 A. 3 ways B. 4 ways C. 5 ways D. 6 ways E. None of the above
10 Domino tiling Number of ways to tile an 2xn board with 1x2 and 2x1 domino pieces 1,2,3,5,8,13, Fibonacci sequence! Can we prove it? Try yourself first
11 Domino tiling P(n) number of ways to tile an 2xn board with 2x1 and 1x2 dominos Lets look on the right most tiles 2 x (n-1) board 2 x (n-2) board
12 Domino tiling 2 x (n-1) board 2 x (n-2) board 1st option: can tile remaining board in P(n-1) ways 2nd option: can tile remaining board in P(n-2) ways So P(n)=P(n-1)+P(n-2)
13 2. Geometry
14 Polygons Theorem: in a polygon with n sides, the sum of the interior angles is (n-2)180 Example: sum of angles is 3*180
15 Polygons Theorem: in a polygon with n sides, the sum of the interior angles is (n-2)180 Proof by induction on n Base case: A. n=1 B. n=2 C. n=3 D. n=4 E. Other
16 Polygons Theorem: in a polygon with n sides, the sum of the interior angles is (n-2)180 Proof by induction on n Base case: A. n=1 B. n=2 C. n=3 D. n=4 E. Other
17 Polygons Theorem: in a polygon with n sides, the sum of the interior angles is (n-2)180 Proof by induction on n Base case: n=3, sum of angles in a triangle is 180 (without proof here)
18 Polygons Theorem: in a polygon with n sides, the sum of the interior angles is (n-2)180 Inductive step: assume for n, prove for n+1 That is Assume: every n-polygon has degree sum (n-2)180 WTS: every (n+1)-polygon has degree sum (n-1)180
19 Polygons Theorem: in a polygon with n sides, the sum of the interior angles is (n-2)180 Inductive step: assume for n, prove for n+1 Main idea: split (n+1)-polygon to a triangle and an n-polygon Triangle, sum of angles is180 n-polygon, sum of angles is(n-2)180 by inductive hypothesis
20 Polygons Theorem: in a polygon with n sides, the sum of the interior angles is (n-2)180 Inductive step: assume for n, prove for n+1 Split the polygon by a diagonal to an n-polygon and a triangle. The sum of the angles in the (n+1)- polygon is equal to the sum of angles in the triangle plus the sum of the angles in the n-polygon. The sum of angles in the triangle is 180 . The sum of angles in the n-polygon is (n-2)180 by the inductive hypothesis. So, total sum of angles is (n-1) 180 . QED
21 A different proof Theorem: in a polygon with n sides, the sum of the interior angles is (n-2)180 Choose a point in the middle, create triangles n triangles; in each the sum is 180 Subtract center, contributes 360 (full circle) Total: n*180 - 360 = (n-2)180
22 3. Plane tiling
23 Plane tiling Partitioning the plane in a regular manner Which shapes can be used for that?
24 Boring example: squares
25 Boring example: triangles
26 Less boring: two squares What should be the ratio between the two squares to get this to work?
27 Pentagons: 14 possibilites
28 Escher
29 More Escher
30 Even more Escher
31 Regular tiling Regular polygon: all angles are the same
32 Regular tiling Which regular polygons can tile the plane? We have seen two examples What else?
33 Regular tiling regular n-polygon: regular polygon with n sides n=3,4 give a tiling A. That s it B. There is a finite number of additional solutions C. There is an infinite number of additional solutions
34 Regular tiling Theorem: a regular n-polygon tile the plane only for n=3,4,6 How can we prove it? Take a couple of minutes to brainstorm with your neighbours
35 Regular tiling: proof We proved: in any polygon with n sides, sum of internal angles is (n-2)*180 In a regular n-polygon, all angles = ? 2 ? 180 If they tile the plane, then at a vertex, they must complete 360 If k regular n-polygons touch at a vertex, we have the equation ?? 2 ? 180 = 360
36 Regular tiling: proof What are the integer solutions of ?? 2 ? 180 = 360? ? ? 2 180 = ? 360 ? ? 2 = 2? ? 2 ? = 2? 2? ? 2 n = All (n,k) integer solutions -> proof of theorem Also: ? 3,? 3
37 Regular tiling: proof 2? ? 2 n = ? = 3:? = 6 ? = 4:? = 4 ? = 5:? = 10/3 invalid ? = 6:? = 3 ? > 6:? < 3 hexagon tiling square tiling triangular tiling invalid
38 Regular tiling: proof 2? ? 2 n = ? = 3:? = 6 ? = 4:? = 4 ? = 5:? = 10/3 invalid ? = 6:? = 3 ? > 6:? < 3 hexagon tiling square tiling triangular tiling invalid
39 All regular tilings
