ECS 20 – Fall 2021 –
Today: Introduction
1. Opening comments 2. Examples
Introduction
o 2.1. Counting paths
o 2.2. Ramsey number R(3,3)
o 2.3. At least 6 shuffles needed to shuffle a deck
Announcements
1. Find the course homepage & read the syllabus
2. Get setup on Gradescope
3. Get setup on Piazza
4. PS1 due next Tuesday – typeset with LaTeX
5. TAs: AJ3: Arefeh, John, Jon, Justin
6. Phones & laptops off and in your bagRule 1
7. Requested: Proper mask, properly worn.
Requested: well-fit N95 or KN94Rule 2
Introduction
1. Opening Comments
• Welcome! Strange to be back in the classroom? It is for me.
• Discrete (not discreet) math: deals with finite and countably infinite sets
• A term rarely used by mathematicians, who say what they do more
specifically.
• Some branches mathematics that we talk about in discrete math:
• Set theory (but not crazy-big sets)
• Logic (basic logic, nothing too foundational)
• Combinatorics (how to count things, how to enumerate thing)
• Probability (but on finite or countably infinite probability spaces) • Graph theory (points and two-elements subset of them)
• All of this stuff could be taught in high school or middle school. If you went to a really good school, maybe it was
• I tend to ask more of my students than other professors do
• I never talk-down to the students
1
• I don’t follow or require any text.
• I don’t enforce prerequisites.
• I ask challenging HW questions.
• Yet I am trying to become a more effective teacher for “average” students. Retiring soon. I would like to think of myself as having embodied a broad interest in students’ well being, not just the intellectual growth of the top of the class.
• I am interested in you. If I don’t seem to know you as well as I should, it might be because I am totally face blind. Be kind and tell me who you are if the context doesn’t make that obvious.
Goals:
1. learn some standard material
2. gain some mathematical maturity
3. improve your ability to think creatively in a rigorous domain
4. improve your technical writing
5. invite introspection
Much of what one learns in this class from struggling working out problems. You are going to get stuck; to have feelings that you don’t know where to start; might feel stupid or frustrated. Pairs allowed this term for homeworks.
Problem-Solving Hints:
1. Reformulate to something equivalent
2. Generalize
3. Work out special cases. Small cases. Look for patterns.
4. Name things (e.g., introduce variables)
5. Create tailor-made definitions
6. Draw pictures
7. Think recursively
8. Adopt a playful attitude
9. Forget pattern-matching
10. But look for echoes!
11. Know what you know (don’t fool yourself, don’t try to fool others) 12. Treat the exposition as part of the problem solving
2
For further advice of this character, read ́lya, How to Solve It. He describes a 4-step strategy: (1) Understand the problem; (2) Make a plan; (3) Carry out the plan; (4) Look-back.
2. Examples
2.1 Counting paths
How many paths are there by which you can walk from one corner of downtown Davis, say the NE corner, to the opposite corner?
First we need to refine the question. Only allowed to walk on streets or walkways that show up on Google maps. Travel from one intersection to another. Path has to be “reasonable”: traversing each street or walkway has to move you in the right direction, lowering your distance to your destination. NE corner = 5th and F; SW corner = 1st and A
3
4
Key insight: The number of paths to a vertex (a point of intersection of two line segments) is the number of paths to the north plus the number of paths to the east. The number of paths from the starting point to itself is 1. From this, can iteratively figure everything out quite quickly, as marked above. Answer: 226 paths.
2.2. Ramsey number R(3,3)
Suppose we have 6 people gathered. I claim that either three mutually know one another, or three mutually don’t know one another. Assume, however unrealistically, that knowing is symmetric: if A knows B then B knows A.
Represent people as points (vertices) and relationships between them as lines (edges), the line either black (if they know one another) or red (if they don’t). Recast in this way, we are looking at the complete graph (all pairs of vertices connected) on 6 vertices, with edges colored either red or black, and we are claiming that the graph necessarily has a monochromatic triangle (three mutually connected vertices, all edges of the same color).
A computer scientists would pass rather quickly/effortlessly to people being vertices, relationships being edges. This is both the strength of computer
5
science, but also it’s weakness. Strength people we can solve real-world problems, often rather easily, by introduction such abstractions. Weakness because we forget that people and their relationships are order of magnitude more complex than vertices and edges, and we have passed from the one to the other only as a sort of temporary fiction. If that fiction is believed too firmly, we actually begin to treat people as vertices in a graph.
01 52
43
So why does a 6-vertex graph with edges colored black or red have a monochromatic triangle. (A 5-vertext graph might not.) (Find some monochromatic triangles in the graph above.)
Choose one vertex, say vertex 0, and inspect all of its 5 neighbors:
01 52
43
Vertex 1 is connected to these five neighbors with red or with black edges. Either 3 or more of these edges are red OR 3 or more of these edges are black – otherwise, vertex 0 wouldn’t be connected to five neighbors, but 4 or
6
fewer. Lets suppose, as in the picture, that 3 or more of 0’s neighbors are joined to it on red edges. If any of these neighbors are joined by a red edge, then we are done: we have found a monochromatic triangle. Otherwise, all three of these neighbors are connected to one another by black edges, in which case we are done: we have a black triangle. The case with three neighbors connected by black edges is analogous.
Not true for 5:
GENERALIZING:
Let R(n,n) = the minimum number of vertices such that the complete graph on n vertices with edges colored two colors must have a monochromatic n- clique. Note: not obvious that such a number exists—that too must be proven. That such a number does exist is Ramsey’s Theorem. Perhaps we will prove it later in the term.
R(3,3) = 6
R(4,4) = 18
R(5,5) is unknown! We do know that 43 ≤ R(5,5) ≤ 48
“[Paul] Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.” [ ]
7
2.3: At least 6 shuffles needed to shuffle a decks
In 1992, and showed that after seven random riffle shuffles of a deck of 52 cards, every configuration is nearly equally likely.
8
In general, the authors show that ~ 1.5 lg n riffle shuffes are necessary and sufficient to well-shuffle a deck of n cards (in the sense of getting the total- variation distance to drop under 1/2).
We claim that 5 shuffles of a deck of 52 cards is not enough to randomize the cards.
Here by shuffles I mean the usual “riffle shuffle.” Prof. Rogaway demonstrates one with an imaginary deck.
Assume a starting sequence of 1, 2, 3, …, 51, 52
Even though we won’t define what it means to randomize the cards, clearly a deck cannot be well randomized unless you can get any resulting sequence of cards starting from any given initial sequence. For example, you should be able to shuffle the sequence above and end up with:
52, 51, …, 3, 2, 1
We are going to show that 5 shuffles of this deck will never transform the specified starting sequence to the specified final sequence. So it can’t do a good job of mixing the deck.
9
From http://www.math.hmc.edu/funfacts/ffiles/20001.4-6.shtml (now defunct):
An amazing fact is that five random riffle shuffles are not enough to randomize a deck of cards, because not only is every configuration not nearly equally likely, there are in fact some configurations which are not reachable in 5 shuffles!
To see this, suppose (before shuffling) the cards in a deck are arranged in order from 1 to 52, top to bottom. After doing one shuffle, what kind of sequences are possible? A moment’s reflection reveals that only configurations with 2 or fewer rising sequences are possible. A rising sequence is a maximal increasing sequential ordering of cards that appear in the deck (with other cards possibly interspersed) as you run through the cards from top to bottom. For instance, in an 8 card deck, 12345678 is the ordered deck and it has 1 rising sequence. After one shuffle,
16237845
is a possible configuration; note that it has 2 rising sequences (the black
numerals form one, the red numerals form the other). Clearly the rising
sequences are formed when the deck is cut before they are interleaved in the
shuffle.
So, after doing 2 shuffles, how many rising sequences can we expect? At most 4, since each of the 2 rising sequences from the first shuffle have a chance of being cut in the second shuffle. So the number of rising sequences can at most double during each shuffle. After doing 5 shuffles, there at most 32 rising sequences.
But the reversed deck, numbered 52 down to 1, has 52 rising sequences! Therefore the reversed deck cannot be obtained in 5 random riffle shuffles!
Max number of rising sequences after
0 shuffles: 1 1 shuffles: 2 2 shuffles: 4 3 shuffles: 8 4 shuffles: 16
5 shuffles: 32 We still can’t have reached anything with more than 32 rising sequences
6 shuffles: 64
10