Transcript Come determinare - MATEMATICA-INFORMATICA

6 novembre 2008
Università delle LiberEtà
udine
giuseppina trifiletti
giuseppina trifiletti
giuseppina trifiletti
In mathematics, a prime number (or a prime) is a natural
number which has exactly two distinct natural number
divisors: 1 and itself. An infinitude of prime numbers
exists, as demonstrated by Euclid around 300 BC. The
first twenty-five prime numbers are:
2, 3, 5, 7, 11, 13, 17, 19, 23,
29, 31, 37, 41, 43, 47, 53,
59, 61, 67, 71, 73, 79, 83,
89, 97 …
giuseppina trifiletti
Go out Barbara!
giuseppina trifiletti
N objects are set in a circle
one object every M objects is
removed and the circle is closed
Which object will be the last?
Which is the elimination order?
giuseppina trifiletti
There isn't an all-cases formule
The problem can be solved using a
precise algorythm
the right one for each counts,
which,
when
translated
to
a
programming language, allows the
computer to give us an answer in a
short time.
giuseppina trifiletti
The Lager Counts
In a work camp for war prisoners there were 10
people.
The prisoners had to be killed.
The guards' chief, sadistic but a math-lover, decided
to save one prisoner's life.
The prisoners must be in a circle,
To pick the lucky one he decided to make a counts
with 17 beats.
He said he begins from the first at his left. He, of
course, would not have counted himself.
Then, before starting the counts, he asked: “Does
someone want to change their place?”
Only one of them lifted his hand and moved to the
chief's right.
Why ?
Some other prisoners understood why, but didn't
want to challenge for the safety-place, they chose
instead to die with their friends.
giuseppina trifiletti
The Lager Counts
This is for you an hard black counts
Now in a ring all you by hand
Will not die out in this bad band
The one who now will not go out
giuseppina trifiletti
17 beats for your end
\
This
is
\
for
1
Now
in
not
9
The
a
ring
die
out
all
hard black counts
you
4
by
7
in
10
14
\
3
6
one who now
13
an
2
5
Will
you
\
this
8
bad
11
will
hand
band
12
not
go
out
15
16
17
Scan go-out
separating
We must now make
a practical demonstration
Some volunteers come here
please
giuseppina trifiletti
What if the prisoners
example, 24?
Could
they
steadyness?
react
were,
with
for
such
No.
They had to calculate differently
because 24 > 17
For the previous work strategy it is necessaire
that
• The number of beats
- must be prime
- must be greater than the number of
prisoners
• The first of the counts must be always
the first at the left of the chief
If it is not so, the rest of the counts will no more
be always different from 0 and so, sooner or later,
the one before the first in the counts will be
picked out and so he won't be saved.
If the prisoners were 4, or any other number
smaller than 17 (and of course >1)
chief
chief
A
B
D
B
D
C
4 prisoners
chief
C
removed B
chief
A
B
D
A
C
removed D
A
B
D
C
removed C
“A” would not have been picked out in any case.
They leave in the following order
B, D, C
B first
(17 : 4 = 4 and rest is 1)
D second
(17 : 3 = 5 and rest is 2)
C third
(17 : 2 = 8 and rest is 1)
The last is A
giuseppina trifiletti
Fortunately the guards' chief
loved to make bad jokes to try his
prisoners spirit and sharpness.
In the end he punished the one
who chose to save himself
and gave a free day to those who
resigned to death.
giuseppina trifiletti
A good chance to talk
about the algorythms
and
about the prime numbers
giuseppina trifiletti
giuseppina trifiletti
Hot new – sexy prime numbers
•
Mathematicians sometimes also like to have fun. In
spite of their name though, sexy primes are not
connected to sex but to number 6 which, in latin, is
called “sex”.
•
A couple of prime numbers is called “sexy” if the
difference between the two is equal to 6. So sexy
couples are of the kind: (p, p+6).
•
Do you want a list of the first few sexy couples?
Here it is: ...
–
(5, 11), (7, 13), (11, 17), (13, 19), (17, 23), (23,
29), (31, 37), (37, 43), …
giuseppina trifiletti
The importance of Prime Numbers
•
•
The importance of prime numbers comes
from the fact that they are the bricks that
form all natural numbers. It means that
each natural number (2,3,4,5,6,7,8,...) can
be built using those bricks.
Fundamental Arithmetic Theorem
– Each natural number can be
represented only in one way as a
product of prime numbers.
– Examples: 38 = 19x2
72 = 32 x 23
38 = 19 times 2
72 = 3 at the second power times 2 at the third power
The importance of prime numbers
in cryptography and security
During the last 20 years the Prime numbers
theory attracted also interest of many notmathematicians,
because of its application in computer
science and cryptography,
linked for example to security inside the
internet, digital signatures, transmission of
encrypted data ...
giuseppina trifiletti
Great prime numbers
Factorization and Security
In reality you have to choose great prime numbers (p and
q), so that it becomes impossible to factorize, separate
into factors a number, so as 15 =3 x 5, n = p x q, in a
reasonable amount of time.
The method is based on the assumption that it is
extremely difficult to get to know p and q knowing their
product.
Try to discover which factors form the number 2047, for
example.
You'll need some time.
Just imagine what will happen if the number is made of
millions of digits!
giuseppina trifiletti
28 settembre 2008
46mo Mersenne prime number
• Some Californian
mathematicians discovered
a prime number with 13
million of digits.
• When they will publisch
their results they’ll receive
a 100-thousand dollars
Marin Mersenne
prize
1588-1684
giuseppina trifiletti
Not all prime numbers can be expressed as 2p1 and not all 2p-1 numbers are prime numbers
• \Not all Mersenne's numbers are prime numbers and
not all prime numbers can be written as Mersenne's
numbers.
– Number 5 (which is a prime number), for
example, can't be expressed as 2p-1.
– 211-1=..... is not a prime number and it is the
smallest of this kind of numbers not to be a prime
number.
• Mersenne's formule though can find great prime
numbers (thanks to the exponential formule) which are
very useful for cryptography and not only for that.
giuseppina trifiletti
THE SAME NUMBERS OF FRIENDS
• How much would you bet that in our
group at least 2 people have the same
number of friends?
• How much would you bet that in any
group of people at least 2 people have
the same number of friends?
giuseppina trifiletti
Any group with 5 people
and the drawers principle
• A group made of 5 people A,B,C,D,E
• Nobody in the group is friend with himself
• If one person in the group, for example A, has no
friends then B,C,D,E can't have 4 friends, and if one
person in the group has 4 friends there can't be
anyone with no friends.
• So each person can have
– 0,1,2, 3 friends
or
1,2,3, 4 friends
• Only 4 drawers for 5 people
• One drawer has to be used for at least 2 people
The number for friends can be
0
1
2
3
3
4
or
1
2
Only 4 drawers for 5 people
only m-1 drawers
if the people are m
Aldo, Bruno, Carla, Dario, Elisa, meet
by chance.
I can bet 1 million euros, or even much
more, because I am perfectly certain,
that at least 2 of them have the same
number of friends in the group itself,
even if the group is made of random
people.
giuseppina trifiletti
We investigate and discover (with a
fast heartbeat, because of the high
bet)
that Aldo has no friends in the group, B
has one friend, C has 2 friends and D has
3 friends.
So unlucky!
Until now everyone has a different
number of friends!
giuseppina trifiletti
In this way we filled all the drawers.
0 friends
1 friend
2 friends
3 friends
Aldo
Bruno
Carla
Dario
But what about Elisa?
How many friends does she have?
giuseppina trifiletti
I can conclude, with some considerable relief, that I
can only put her in one of the 4 drawers.
As a matter of fact Elisa states that she has two
friends, so she'll be put in Carla's drawer.
0 friends
Aldo
1 friend
2 friends
3 friends
Bruno
Carla
Elisa
Dario
4 drawers
I bet and
I won a million of dollars.
Who, among you, would like
to give them to me?
SOLUTION: for every individual I in the group, made
of m people, let n(I) be the number of I's friends
inside the group. So, not allowing I to be friends with
himself, n(I) can only be 1,2,...m-1. We can observe
that, for a fixed group with a determined number of
elements/ndividuals, n(I) can't be 0 and also m-1. If
there was a person with m-1 friends, every other
person would have at least 1 friend. In the same way
if one person had no friends (0 friends), there
couldn't be people with m-1 friends. If we use the
drawers principle (where the m number of people is
the number of objects to put in the drawers and the
drawers are the possible m-1 values assigned to
n(I)), you can see that at least 2 people have to stay
in the same drawer, which means that they have the
same number of friends.
THE BIRTHDAY
• THE SAME MONTH
How much would you bet that in our group
– At least two people’s birthdays happen in the same month?
How many people should be there to have the certainty of
this?
– At least three people’s birthdays happened in the same
month? How many people should be there to have the
certainty of this?
• THE SAME DAY
How much would you bet that in our group
– At least two people’s birthdays happened on the same day?
How many people should be there to have the certainty of
this?
Il paradosso del compleanno
• It is a paradox of probability theory defined in the
1939 by Richard von Mises.
• The paradox states
– the probability at least 2 people in a group have
the birthday in the same day is much higher than
the intuition suggests: in fact already in a group of
23 people the probability is approximately 51%;
with 30 people excedes the 70%, with 50 people it
touches the 97%
– Even if to arrive to the certainty it needs a group
of 366 people (thanks to the Principle of the
drawers)
giuseppina trifiletti
A good chance to talk
about combinatory calculation
and
about probability
giuseppina trifiletti