essay
jenny2000000
I399_Lecture_4.pptxI399 – Problem solving Techniques
Lecture 4
Today
Scholarly Research
Math
Scholarly Research
P a r t 1:
B i g g e r Q u e s t I o n s
OneSearch@IU
synthesis
How to search a scholarly database
again, have a developed question
learn the language of the database
keywords and subject terms
isolate key terms
find related terms
background search (Google, Wikipedia, etc.)
potentially good for terms
do an initial search
look at subject terms
combine subject terms with AND
Activity
find subject terms for:
The effects of differing cultural backgrounds on interpretation of on screen computer images
Activity
Activity
Activity
Activity
Activity
Activity
Activity
Activity
cultural differences
cross-cultural studies
cross cultural differences
cultural influences
Activity
Activity
image analysis
visual perception
Activity
computer:
computer software
computers
Activity
computer image:
image processing
image analysis
computer vision
Activity
find resources
The effects of differing cultural backgrounds on interpretation of on screen computer images
Activity
Activity
Activity
Activity
once you have a good source
find similar
look at subject combination
what did it site?
who sited it?
Activity
find resources similar to:
New Thinking in Comparative Education
Marianne A Larson (Ed.)
why bother with scholarly publications?
depth
breadth
evidence
insight
reproducibility
not infallible
more sources
Activity
Comparing Popular and Scholarly Publications
Math
P a r t 1:
M a t h ? ! ?
math is a way of assigning representations to certain concepts
laying out some basic frameworks (axiom)
and seeing what happens from there
math is language
Goals
consistency in reproduction
predictive power
Goals
exploration of what's possible
P a r t 2:
P r o o f s
Proofs
show what you know
lingo not the most important bit
basics
A proof consists of a series of valid statements that demonstrate the truth of a theorem, such as:
Axioms
Things we (or someone else) have previously proven
Algebraic transformations or Logical manipulations
Constructions
Basic Methods of Proof:
If we want to prove Thing A implies Thing B
Direct Proof:
Assume Thing A is True, show Thing B must be True logically.
Proof by Contradiction
Assume Thing A implies Thing b is False, show this causes a contradiction, such as something is both true and false at the same time or 1 = 2.
Basic Method of Dis-Proof:
Counterexample (show one example where the ‘Theorem’ is False)
Direct Proofs
Start with what you want to prove
Spell out steps to get to desired conclusion
Justifying as you go
Try to focus on how an argument is constructed.
Some Definitions
Even – an integer is even if it can be written as 2 times another integer.
x is even if there is another integer (i) such that x = 2 * i
Some Definitions
Even – an integer is even if it can be written as 2 times another integer.
6 is even because it can be written as
2 * another integer (in this case 3)
Some Definitions
Even – an integer is even if it can be written as 2 times another integer.
5 is not even because there is in integer that can be multiplied by 2 to get 5
Direct Proof
Thm: If x and y are even integers, so is (x + y).
Pf:
GIVEN: Assume x and y are even integers.
So there is an integer a s.t. x = 2 * a (def. even)
And there is an integer b s.t. y = 2 * b (def. even)
So (x + y) = (2a + 2b) (algebra)
(x + y) = 2(a + b) (algebra)
Let's call whatever a+b is c (construction)
c is an integer because int + int is an int (prior)
So (x + y) = 2c, where c is an integer
TARGET: So (x + y) is even. (def. even)
Proof by Contradiction
Thm: There is no largest integer.
Pf:
Assume, for the purposes of contradiction, that there IS a largest integer. Call it a
Consider b = a + 1
b > a
This contradicts a being the largest integer!
So there cannot be a largest integer. ■
Dis-proof by Counterexample
Thm??: Every positive integer is the sum of the squares of 2 integers
Dis-Pf:
Let x = 3.
If 3 = a2 + b2, then a2 , b2 ≤ 3.
Since a,b are intigers and a2 , b2 ≤ 3; a,b must be in this list: -1, 0, 1
(±1) 2 = 1 and (0) 2 = 0
But 3 ≠0 + 0, 3 ≠ 0 + 1, 3 ≠ 1 + 1
So the “theorem” is false.
where are you looking to go
where are you starting from
what steps in between
Begin with
You can do the following things as many times as you like:
Double the contents of the string after the : for
example, becomes , or
becomes
Replace with : becomes
or
Append to the string if it ends in : becomes
Remove any : becomes
exercise
Begin with
Double the contents of the string after the
Replace with
Append to the string if it ends in
Remove a
Goal: Transform into
exercise
Who found an answer?
exercise
Is there an answer?
simplify
translate
relate
identify keys
test
work from both ends
look for contradictions
What do we need?
1
2
4
4
8
5
5
5
10
7
Initially, we do not have a multiple of three .
To make our goal we must have multiple of three
Can we ever make a multiple of three?
Thought: If n is not a multiple of three, then n – 3 is not a multiple of three.
Proof: By contrapositive; we'll prove that if n – 3 is a multiple of three, then n is also a multiple of three. Because n – 3 is a multiple of three, we can write n – 3 = 3k for some integer k. Then n = 3(k+1), so n is also a multiple of three, as required.
Thought: If n is an integer that is not a multiple of three, then 2n is not a multiple of three.
Proof: Let n be an integer that isn't a multiple of three. If n is congruent to one modulus three, then n = 3k + 1 for some integer k. This means 2n = 2(3k+1) = 6k + 2 = 3(2k) + 2, so 2n is not a multiple of three. Otherwise, n must be congruent to two modulus three, so n = 3k + 2 for some integer k. Then 2n = 2(3k+2) = 6k+4 = 3(2k+1) + 1, and so 2n is not a multiple of three.
Proof: Let n be an integer that isn't a multiple of three.
If n is congruent to one modulus three, then n = 3k + 1 for some integer k.
This means 2n = 2(3k+1) = 6k + 2 = 3(2k) + 2
so 2n is not a multiple of three.
Otherwise, n must be congruent to two modulus three, so n = 3k + 2 for some integer k.
Then 2n = 2(3k+2) = 6k+4 = 3(2k+1) + 1
and so 2n is not a multiple of three.
Proof: Let n be an integer that isn't a multiple of three.
a possibility is that our number is one more than a multiple of three, that means our number is 3 times some integer (multiple of three) plus one more (3k +1)
This means 2n = 2(3k+1) = 6k + 2 = 3(2k) + 2
so 2n is not a multiple of three.
Otherwise, n must be congruent to two modulus three, so n = 3k + 2 for some integer k.
Then 2n = 2(3k+2) = 6k+4 = 3(2k+1) + 1
and so 2n is not a multiple of three.
Proof: Let n be an integer that isn't a multiple of three.
a possibility is that our number is one more than a multiple of three, that means our number is 3 times some integer (multiple of three) plus one more (3k +1)
This means if we double our number we'll have six times some integer plus 2
so 2n is not a multiple of three.
Otherwise, n must be congruent to two modulus three, so n = 3k + 2 for some integer k.
Then 2n = 2(3k+2) = 6k+4 = 3(2k+1) + 1
and so 2n is not a multiple of three.
Proof: Let n be an integer that isn't a multiple of three.
a possibility is that our number is one more than a multiple of three, that means our number is 3 times some integer (multiple of three) plus one more (3k +1)
This means if we double our number we'll have six times some integer plus 2
this means our number can't be divisible by three since it is 3 times an integer with two left over
Otherwise, n must be congruent to two modulus three, so n = 3k + 2 for some integer k.
Then 2n = 2(3k+2) = 6k+4 = 3(2k+1) + 1
and so 2n is not a multiple of three.
Proof: Let n be an integer that isn't a multiple of three.
a possibility is that our number is one more than a multiple of three, that means our number is 3 times some integer (multiple of three) plus one more (3k +1)
This means if we double our number we'll have six times some integer plus 2
this means our number can't be divisible by three since it is 3 times an integer with two left over
if our number isn't one more than a multiple of 3, it has to be 2 more (3 more would make it a multiple of 3)
Then 2n = 2(3k+2) = 6k+4 = 3(2k+1) + 1
and so 2n is not a multiple of three.
Proof: Let n be an integer that isn't a multiple of three.
a possibility is that our number is one more than a multiple of three, that means our number is 3 times some integer (multiple of three) plus one more (3k +1)
This means if we double our number we'll have six times some integer plus 2
this means our number can't be divisible by three since it is 3 times an integer with two left over
if our number isn't one more than a multiple of 3, it has to be 2 more (3 more would make it a multiple of 3)
if we pull out all the 3s then that leaves us with 1 left
and so 2n is not a multiple of three.
Proof: Let n be an integer that isn't a multiple of three.
a possibility is that our number is one more than a multiple of three, that means our number is 3 times some integer (multiple of three) plus one more (3k +1)
This means if we double our number we'll have six times some integer plus 2
this means our number can't be divisible by three since it is 3 times an integer with two left over
if our number isn't one more than a multiple of 3, it has to be 2 more (3 more would make it a multiple of 3)
if we pull out all the 3s then that leaves us with 1 left
and so 2n is not a multiple of three.
Thought: No matter which moves are made, the number of in the string never becomes multiple of three.
Proof: Lets take the statement “After any n moves, the number of . in the string will not be multiple of three.”
We will prove that this statement is true for all number of moves 0 or greater
Lets start by showing that the number of after 0 moves is not a multiple of three. - After no moves, the string is which has one in it. Since one isn't a multiple of three, our statement is true.
Next, suppose that our statement has held to some arbitrary point. We then need to show that the next step is also true
Lets call the number of at our arbitrary point r. By our statement we know that r is not a multiple of three. Now, consider the four possible choices for the next move:
Case 1: Double the string after the After this, we will have 2 times r in the string, and from our lemma 2r isn't a multiple of three.
Case 2: Replace with After this, we will have r – 3 in the string, and by our lemma r – 3 is not a multiple of three.
Cases 3 and 4: Either append or delete . This preserves the number of in the string, so we don't have a multiple of three at this point.
Therefore, no sequence of next moves ends with a multiple of three
P a r t 3:
F a i l u r e
how to deal with failure
don't give up
establish why you are failing
what do you need for success
is success possible?
justify
at what cost success
Activity
Can we turn over successive pairs to leave only heads facing up?
P a r t 4:
I n d u c t i o n
solutions that work at any scale
this lets us do the hard work with simple cases
does a generalization actually hold up
show:
starts true
remains true
so always true
how to prove something is true for an infinite number of possibilities
Think about Dominos
1
etc.
103
“Domino Principle”:
The 1st domino is knocked over
If an arbitrary domino (the k-th one) is knocked over
then the next one (the (k+1)-th domino) also falls
All dominoes are knocked over
k
k+1
…
…
1
104
The Principle of Mathematical Induction (PMI)
Induction is an extension of the Domino Principle
To prove a statement always holds we can prove the following:
The basis: show the statement holds for some first value.
The inductive hypothesis (IH): if the statement holds for some arbitrary point
The inductive step (IS): then the same statement also holds for the next point.
105
Induction problems often take the form of a shortcut:
Induction allows us to prove this shortcut works
Induction problems follow a template.
Setting up the template always has 3 steps.
Once you understand how to apply that template, you’ve already done most of the problem!
Activity revisited
Can we turn over successive pairs to leave only heads facing up?
Activity revisited
Can we turn over successive pairs to leave only heads facing up?
Activity revisited
Can we turn over successive pairs to leave only heads facing up?
Activity revisited
Either increase heads by 2
Decrease heads by 2
Or number remains unchanged
Activity revisited
Can we turn over successive pairs to leave only heads facing up?
So how does Induction work?
We prove the statement is true at the Basis Case (say, n = 1).
2
1 + 2 + 3 + … + (n-1) + n = n(n+1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ….
112
Now, if we let k = 1, we know that if the statement is true at k, it’s also true at k+1. So the Basis Case + the Inductive Step tells us that it’s true at 2.
2
1 + 2 + 3 + … + (n-1) + n = n(n+1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ….
113
If it’s true at 2, by the same reasoning it’s true at 3.
2
1 + 2 + 3 + … + (n-1) + n = n(n+1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ….
114
Since the statement being true at each value implies the truth of the next value, the statement is true for all non-negative values of n.
2
1 + 2 + 3 + … + (n-1) + n = n(n+1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ….
115
So the general format of the template looks like this:
k k+1
Step 1, prove the Basis Case(s)
Step 2, state the Inductive Hypothesis (If it’s true for n = k …)
Step 3, prove the Inductive Step … then it’s true for n = k+1
116
Then by the Principle of Mathematical Induction (PMI), it’s true for all values of n ≥ the basis case(s)!
k k+1
117
Activity
there are 50 coins
you can not see or discern their faces
you know there are 40 heads 10 tails
how do you separate into two piles guaranteeing equal number of tails in both?
P a r t 5:
R e a l W o r l d
defend your ideas
create shortcuts
computer structures
figure out if something is possible
Double your money
divide money in halves called a and b.
So a = b.
a2 = a * b
a2 - b2 = ab - b2
(a – b) (a + b) = b (a – b)
a + b = b
b + b = b (Remember, a = b)
2b = b
all your money = half your money
avoid scams
P a r t 6:
L i m i t s
language barriers
does your problem fit the model
A group of people with assorted eye colors live on an island. They are all perfect logicians. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. On this island there are 100 blue-eyed people. So any given blue-eyed person can see 99 people with blue eyes, but that does not tell them their own eye color.
One day an outsider arrives and says "I can see someone who has blue eyes." Who leaves the island, and on what night? There are no mirrors or reflecting surfaces. It doesn't depend on tricky wording or anyone lying or guessing, and it doesn't involve people doing something like creating a sign language or doing genetics.
reality
P a r t 7:
M i d t e r m
Next Week
Can be taken Monday through Wednesday
3 hour timeframe
show me how you approach problems
can use notes
no internet (aside from accessing the midterm)
no communicating with others about the midterm
break the problems down
detail all your work
Questions?
