16.04.

[west]

habe bis jetzt 435, 438, 442, 450
es fehlt 453

[west]

Inklusions- Exklusionsprinzip

n Personen

D..Menge der Deutschsprachigen,
E..Menge der Englischsprachigen,
F..Menge der Französischsprachigen

u .. Vereinigung
n .. Schnitt

|D| = 10
|E| = 7
|F| = 5

|D n E| = 6
|D n F| = 4
|E n F| = 3

|D n E n F| = 3

Ergebnis kommt ganz einfach:

|D u E u F| = |D| + |E| + |F| - |D n E| - |D n F| - |E n F| + |D n E n F|

n=10+7+5-6-4-3+3=12

sollte stimmen.

[west]

Inklusions- Exklusionsprinzip

da bin ich mir nicht zu 100% sicher...

|A| = 10^8

|A3| = ceil [ 10^(8/3) ] = 464
// Anzahl der Zahlen, die <= 10^8 sind und 3.Potenz einer natürlichen Zahl

|A4| = ceil [ 10^(8/4) ] = 100
|A5| = ceil [ 10^(8/5) ] = 39

die 6. Potenzen fallen aus, da jede Zahl die 6.Potenz von x aus den natürlichen ist auch gleichzeitig 3. Potenz von x^2 ist.
[ 2^6=2^(3+3)=2^3 * 2^3=4^3 ]

|A3 n A4| = ceil [ 10^(8/(3*4) ] = 4
|A3 n A5| = ceil [ 10^(8/(3*5) ] = 3
|A4 n A5| = ceil [ 10^(8/(4*5) ] = 2

|A3 n A4 n A5| = ceil [ 10^(8/(3*4*5) ] = 1

|A3 u A4 u A5| = |A3| + |A4| + |A5| - |A3 n A4| - |A3 n A5| - |A4 n A5| + |A3 n A4 n A5| =
464+100+39-4-3-2+1 = 595

d.h. 595 Zahlen <= 10^8 sind 3., 4., 5. oder 6. Potenz von natürlichen Zahlen.

gesucht sind die, die das nicht sind.
10^8 - |A3 u A4 u A5| = 99.999.405

das wärs.

[west]

Anz. der Perm von a,b,c,d,e,f ohne Blöcke "bcf" und "eb"

das sollte ganz leicht gehen:

Permutationen von
a,b,c,d,e,f = 6!

Fall 1
"bcf",a,d,e = 4!

Fall 2
"eb",a,c,d,f = 5!

Fall 3
"ebcf",a,d = 3!

Fall 3 ist sowohl in Fall 1 als auch in Fall 2 erfüllt.

d.h. Endergebnis =
6! - 4! - 5! + 3! = 720 - 24 - 120 + 6 = 582

fertig.

[west]

abgekupfert von der Montagsgruppe:

es sind n Personen
d.h. jede kann zw. 0 und n-1 Bekannte haben.

Annahme: jede Pers kennt unterschiedl. viele Personen.
d.h. nummeriert nach der Anz der Bekannten:
1. Pers: 0 Bekannte
2. Pers: 1 Bekannter
3. Pers: 2 Bekannte
...
n. Pers: n-1 Bekannte

Person n kennt alle anderen, d.h. Pers 1 kann nicht 0 Bekannte haben --> WIDERSPRUCH

man kann n-1 Elemente nicht auf n Plätze anordnen ohne dass sich ein Element wiederholt.
--> mind. 2 Personen haben gleich viele Bekannte.

[jeuneS2]

Man betrachte Stadt A. A hat mindestens ceil((n-1)/2) direkte Verbindungen, also floor((n-1)/2) indirekte Vernidungen.
Sei B eine Stadt, die nur indirekt mit A verbunden ist. Allgemein gibt es n-2 Möglichkeiten für Verbindungen (nicht zu A, nicht zu sich selbst). Zieht man davon die direkt mit A verbundenen ab, erhält man die Zahl der Möglichkeiten für indirekte Verbindungen zu A über 2 oder mehr Zwischenstationen, also n-2 - ceil((n-1)/2) = ceil((n-1)/2) - 1.
B ist also mit mindestens einer Stadt direkt verbunden, mit der auch A direkt verbunden ist (Argumentation analog zu Bsp. 450).
Da man diese Betrachtung für alle Städte durchführen kann, gilt die Behauptung.

[jeuneS2]

Ich hab das ein bisschen anders, nämlich hab ich alle Potenzen drinnen gelassen, hab aber immer, anstatt zu multiplizieren, das kgV der Potenzen genommen. Heraus kommt das gleiche, also 10^8 - 595. (ist aber auch bei näherer Betrachtung relativ klar). imho ist das Weglassen der 6. Potenzen eine sehr gute Idee... fürs rechnen an der Tafel würd ich die 6. Potenzen weglassen UND mit dem kgV rechnen (weils wasserdicht ist), dann ist es glaub ich so, wie sies haben wolln (wobei - eigentlich isses ja wurscht, wie's ich machen würd ;)).

Alle anderen Beispiele hab ich genauso... und DANKE an west fürs tippen und Mühe machen!

[west]

zuerst mal tnx @ jeuneS2

__________________________

argumentieren und genau aufschreiben würd ichs so:

Stadt A hat ceil((n-1)/2) Verbindungen

B soll nicht A sein und weder direkt, noch über eine andere Stadt mit A verbunden sein.
B kann demnach maximal n-1 -1 -ceil((n-1)/2) Verbindungen haben ohne direkt ( -1 ) oder indirekt über 1 Stadt ( -ceil((n-1)/2) ) mit A verbunden zu sein.

echt min-Anz Verbindungen von B <= Verbindungen, die das Kriterium erfüllen (nicht direkt und nicht über 1 andere Stadt zu A verbunden)
ceil((n-1)/2) <= n-1-ceil((n-1)/2)) - 1
ceil((n-1)/2) <= floor((n-1)/2) - 1
WIDERSPRUCH

fertig.

A und B sind beliebig wählbar, d.h. die Argumentation gilt für alle Städte.

[jeuneS2]

@west:
...die Umformungen mit ceil bzw floor auf der rechten Seite sind glaub ich nicht ganz exakt:
n - 1 - ceil ((n-1)/2) - 1 =
= ceil( n - 1 - (n-1)/2) - 1 = //n + ceil(x) = ceil(n+x), n ganze Zahl
= ceil((n-1)/2) -1

mfg

[tricipitinus]

wtf is ceil ?? ;)

[nexxyz]

hmmm...

ich hab mir folgenden lösungsweg gedacht:

1.. stadt A hat mindestens ceil((n-1)/2) unterschiedliche verbindungen
2. stadt B hat mindestens ceil((n-1)/2) unterschiedliche verbindungen

nun soll man in höchstens 2 schritten von A nach B gelangen können. (ceil((n-1)/2))^2 > n für n>1 und das geht ja aus der angabe hervor, da wir ja mindestens 2 städte haben,

also haben wir mehr mögliche verbindungen (inklusive der verbindung hin und wieder zurück zu sich selbst) mit 2 schritten geschaffen, als wir städte haben -> da alle verbindungen unterschiedlich sind muss A von B aus in höchstens 2 schritten erreichbar sein.

oder irre ich mich da irgendwie?
:confused:

[tricipitinus]

oh..never mind..
[max/min = ceil/floor ? ]

[nexxyz]

ceil = klammerausdruck aufrunden
floor = klammerausdruck abrunden

(nehm ich aus dem vergleich der angabe mit der transskription ins forum halt mal an)

[tricipitinus]

hmm..true...
THX!

[jeuneS2]

... das midm ceil/floor richtig übernommen :thumb: (cf. java et al.)

@nexxyz: deine Argumentation ist ihmo zwar einleuchtend, aber nicht zwingend: was nützt es, die Möglichkeiten zu haben, wenn man sie nicht entsprechend benutzen muss... wie gesagt - in my humble opinion

[nexxyz]

@jeuneS2:

hmmm....da hab ich wohl die angabe etwas anders interpretiert als ihr....ich habe das "nur in 2 schritten" als "in höchstens 2 schritten"-begrenzung interpretiert und nicht als "genau in 2 schritten"

[jeuneS2]

@nexxyz
... nein, nein, unsere Interpretationen sind eh die gleichen... ich denke nur, dass (wenn die Behauptung nicht stimmen würde) es auch sein könnte (so wie ich deine Argumentation verstehe), dass doch mehr als 1 Station dazwischenliegen könnte... vielleicht passt die Argumentation ja eh... ich glaube eben nicht... Beweise zu beweisen oder zu widerlegen überlass ich lieber dem Kaiserle ;)

[nexxyz]

hmmm....naja, wenn wir mit 2 schritt mehr als ALLE städte abdecken können, dann muss stadt B ja auch dabei sein, oder?

[west]

n-1 -ceil((n-1)/2)) == floor((n-1)/2)


setzen wir k = n-1

k - ceil (k/2) == floor (k/2)

stimmt sehr wohl.

man kann das leicht überprüfen, indem man für k eine beliebige gerade und eine beliebige ungerade Zahl nimmt.
laut definition ist n>=2 --> k>=1
d.h. man nimmt z.b.
8 dann stimmts
und 9 dann stimmts auch.

[arthemiss]

HELP!

kann mir jemand das hier erklären bitte?

|D| = 10
|E| = 7

|D n E| = 6 ??????

es ist dringend, ich hab gleich eine übung!

danke im voraus!

[jeuneS2]

@west: Asche auf mein Haupt, deins stimmt natürlich... sollte wahrscheinlich zuerst denken, dann schreiben... tut leid!

[arthemiss]

hmmm...die angaben lesen sollte man....:rolleyes:

:D