Komplexitätstheorie Hausaufgaben 1

(181.040 VO SS 2,0)

Hausaufgabe 1.1

You overhear the following dialogue about x and y, both in [2, 3, ..., 100], between two mathematicians, let's call them Prof. P. and Prof. S. w.l.o.g.:

P.:
Well, I know xy, but I don't know x and y.
S.:
I know x+y, and I knew that you don't know x and y.
P.:
Hoho, but then I know x and y.
S.:
In that case I also know x and y.

Your task: Find x and y. If you know the answer, you can contact me to check whether we found the same solution.


Hausaufgabe 1.2

Beweise, dass Ramsey(3,4)=9.


Wolfgang Slany
Last modified: Tue Mar 7 18:40:37 CET 2000