Usb verlängerungskabel(0.5m) und usb stick

Freizeit & Hobby Rätsel
#41

was aber bei 50 Kabeln weniger dramatisch ist…
siehe „22 Versuche“

Bitte gehe Deine Strategie nochmal Durch, die hat einen gravierenden Fehler.
Wenn Du nach dem ersten Testdurchgang nur 4 oder 3 defekte Stränge findest anstatt 5, dann ist das ein viel ungünstigerer Fall.

Dann weißt Du nämlich nicht, daß genau 1 defektes Kabel pro Strang ist, es könnten auch mehr sein. Da reicht es nicht bei einer weiteren Teilung nur einen der Teile zu prüfen.

Ich vermute, daß dieser Irrtum auch in Deinen anderen Überlegungen auftaucht.

1 Like
#42

Richtig Tom:
Die Fragestellung war so, daß, bei einer bestimmten Anzahl von Kabeln, maximal 5 defekte Kabel sind.
Das mit den genau 5 von Hundert einer Produktion hat der Fragesteller „niemand“ nur reingeschrieben, damit klar ist, daß es bei zB 50 Stück nicht genau, sondern 0, 1, 2, 3, 4 oder 5 defekte Kabel sein können.

Bei genau 5 ist die Sache zu trivial, da reichen wenige Testungen. Durch geschicktes Teilen kommt man schnell an den Punkt, wo man 5 defekte Stränge erhält. Dann ist aber bekannt, daß genau 1 defektes Kabel drin ist. Und dann reicht pro Teilung ein Test um weiter gesunde auszuschließen.

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#43

bei 64 isses ja relativ einfach

8x8erkabel

Bis dahin kapiert,
aber dann glaube ich machst Du es Dir einfach.

Wie gehst Du weiter, wenn Du 4 oder 3 defekte 8er-Stränge gefunden hast?

In einem, der von 3 gefundenen Strängen, sind zwar mindestens 1 aber bis zu maximal 3 defekte Kabel drin.
Bei einer weiteren Teilung in zB 4er-Stränge bleibt immer ungewiß wo defekte Kabel sein könnten.

#44

Leider sind diese angeblichen Lösungen keine echten.

Ich habe mir die Mühe gemacht sie durchzuprüfen.

[War etwas anstrengend, weil es schwer ist diesem Telegrammstil zu folgen.
Es schult bisweilen die eigene Konzentration. (aber bitte demnächst etwas klarer und eindeutiger, sonst wird es bald einfach überlesen und nicht ernst genommen)]

Folgendem Fehler unterliegen die Lösungen von „derdepp“:
(bitte nicht persönlich nehmen, sondern als Bereicherung auffassen)

Er ging bei seinen Überlegungen (das zeigen die anderen Postings zu dem Rätsel) davon aus, daß der ungünstige Fall (seine Worte waren ‚worst case‘) der sei, daß nach dem Testen von einer bestimmten Anzahl Strängen maximal 5 defekte gefunden wurden.

Es ist aber so, daß dies eher ein Glücksfall ist, denn dann weiß man ganz sicher, daß in jedem Strang genau nur ein defektes Kabel sein kann.
Das ist eher hilfreich, da durch weiteres Teilen und Ausschlußverfahren die Sache schnell eingeengt werden kann.

Die wirklich ungünstgen Fälle sind die, daß man nur 4 oder 3 Stränge findet. Bei Teilung dieser entstehen 8 bzw 6 neue Stränge, bei denen man eben nicht ohne Weites mit einer Messung Erkenntnis über einen anderen Strang bekommen kann.

#45

dann reduziert sich aber auch die Restmenge

also bei 3x8 bleiben 24
8Versuche

weiter mit 6x4
also es werden alle getestet vom Prinzip her
5x4 bleiben über

dann 5x2
sind 24 Versuche auf den ersten Blick

bei
4x4 die über bleiben
sind es 8x2 die
getestet werden

=22 Versuche

8 sind über
man muss einzeln testen
und maximal 7 Versuche dazu
denn wenn bei 1+2,3+4,5+6 nicht beide kaputt sind
sind 7+8 kaputt

wenn 5+6 kaputt muss man 7 testen um zu sehn ob 7 oder 8 kaputt sind

#46

ja sorry dass ich bloss allen anderen gefolgt bin und des als worst case angesehn habe…

#47

Ausführlicher Lösungsweg 1. Teil
Wichtige Vorüberlegungen und Erkenntnisse für die nachfolgende Abhandlung:

-Habe ich einen Strang (mehrere verbundene Kabel), von dem nichts bekannt ist, muß er mindestens einmal getestet werden.
Ich nenne einen sochen Strang mal StUn (Strang unbekannt).

-Liefert mir der Test eines StUn (Strang unbekannt) ein positives Ergebnis, so sind alle Kabel darin in Ordnung und ich kann diesen bei Seite legen. Ich nenne diesen pSt (positiver Strang).

-Liefert mir der Test eines StUn (Strang unbekannt) ein negatives Ergebnis, dann muß mindestens ein Kabel darin defekt sein.

-Er wird dann zu einem Strang, bei dem bekannt ist, daß er mindestens ein defektes Kabel enthält (aber durchaus auch mehr enthalten kann).
Einen solchen Strang nenne ich StM1 (Strang mindestens 1).

-Ein StM1 (Strang mindestens 1) kann ich teilen, muß aber beide Teile prüfen für weitere Aussagen.
Nach der Prüfung eines der beiden Teilstücke eines solchen StM1 (Strang mindestens 1) erhalte zunächst mal 2 StUn (Strang unbekannt) wobei mindestens einer ein StM1 (Strang mindestens 1) und höchstens einer ein pSt(positiver Strang) ist.

-Einen Strang, von dem bekannt ist, daß genau ein defektes Kabel enthalten ist nenne ich StG1 (Strang genau 1).
Es reicht wenn ich einen StG1 (Strang genau 1) teile und nur einen Teil prüfe.
Nach dieser einen Prüfung erhalte ich wiederum einen StG1 (Strang genau 1) und einen pSt(positiver Strang).

Um es kurz zusammen zu fassen und die neue Terminologie zu lernen:

1 StUn wird 1 mal getestet, ergibt im besten Fall 1 pSt im anderen Fall ein StM1.
oder so:
1 StUn 1 Test > entweder
a) 1 pSt oder
b) 1 StM1

1 StM1 wird geteilt, man erhält 2 StUn; nach 2 Tests > entweder
a)2 StM1 oder
b)1 StM1 + 1 pSt

1 StG1 wird geteilt 1 Test nötig, man erhält >
1 StG1 + 1 pSt

Nach dieser Erkenntnis merkt man schon, daß es sinnlos ist vorher in irgendeiner Weise Stränge zu testen, wenn die Zahl der defekten Kabel insgesammt nicht begrenzt sonder vollkommen unbekannt wäre.
Denn jeder StM1 hinterläßt mindestens 2 weitere Testungen. Also hätte man sich den Test des gesamten Strangs gleich sparen können.

Erst die Beschränkung von maximal 5 defekten Kabeln ermöglicht es StG1 zu produzieren, welche bessere Aussagen liefern.

Bei einem StG1 hat man mit Hilfe von ständigen Halbierungen und jeweils einer Prüfung schnell das defekte Kabel.
Ein 25er StG1 ist spätestens nach 5 Teilungen und jeweiligen Prüfungen durch.
Wobei die kleinste maximale Prüfung der nächstgrößten 2er-Potenz entspricht.
Also von 25 wäre das 32 (=25)
Bei einem 50er StG1, der kleiner als 64 ist (=26) 6 Teilungen und Tests.

Es gilt also möglichst StG1er zu produzieren.

Eine kleine Tabelle, für maximale Tests vo StG1ern. Brauchen wir später noch öfter.
2er-StG1=1Test
3er- und 4er-StG1 = 2 Tests
5er- bis 8er-StG1 = 3 Tests
9er- bis 16er-StG1 = 4 Tests
17er- bis 32er-StG1 = 5 Tests
33er- bis 64er-StG1 = 6 Tests
65er- bis 128er-StG1 = 7 Tests

Ende des 1. Teils

#48

Ausführlicher Lösungsweg 2. Teil
Jetzt wende ich die Erkenntnisse aus Teil 1 mal an.

Es bringt wenig, wenn man genau oder weniger als 4 Stränge bildet und testet.
So bekommt man auf jeden Fall höchstens 4 StM1. Diese hinterlassen (sieh Teil 1) nach ihrer Teilung doppelt soviele Stränge, die alle zu testen sind und man hätte sich die vorergehenden Testungen gleich sparen können.

Bei 10 Kabeln heißt das, man fängt mit fünf 2er-StUn (2er-Stränge Unbekannt) an.
Das sind 5 Tests.

Diese hinterlassen bestenfalls fünf 2er-StG1 (2er-Stränge mit genau 1), die mit 5 weiteren Tests zu beenden wären.
Gesamt also 10 Versuche.

Oder sie hinterlassen 4 (oder im günstigeren Fall weniger) 2er-StM1 (2er-Stränge mit mindestens 1).
Diese müssen aber alle geteilt und alle geprüft werden. Wären 8 weiter, also gesamt 13 Tests

Hier haben wir den Beweis, daß 10 Kabel besser einzeln zu testen sind.

Hier stellte sich mir die Frage: Ab wann lohnt sich eine Strategie überhaupt.

Die nahliegende Überlegung war, erhöhen wir die Anfangsmenge auf 12 und machen wir das Spiel von vorne.
Also zunächst 6 2er-StUn mit 6 Tests gibt, wie oben, bestenfalls 5 2er-StG1 mit 5 weiteren oder im ungünstigen Fall 4 2er-StM1 die 8 weitere Tests nötig machen. Das macht bei 12 Kabeln 14 nötige Tests
Und so weiter, bei 14 Kabeln sind es 15 Tests und endlich bei 16 Kabeln braucht man mit dieser Strategie, die zwei Kabel zusammenfasst auch 16 Tests.

Die ersten 5 3er-StUn sind ja mit 15 Kabeln machbar. Wer will kann das gerne selber durchrechnen. Selbst mit einem speziellen Trick (zu dem komme ich etwas später) kommt man auch auf 16 Tests.

Und auch mit 17 Kabeln sind mit Strategie noch 17 Testungen notwendig. Ich spar mir das Ausführen.

Ab 18 Kabeln ist eine Strategie erst versuchsärmer.

Das ist ganz wichtig bei der weiteren Betrachtung. Sollte bei allen Teilungen 17 oder weniger Kabel übrigbleiben, über die absolut keine Aussage möglich ist, lohnt es sich diese einzelnd zu prüfen.

Ende des 2. Teils

genug für heute.
Wer Fehler entdeckt, bitte melden.

#49

Ausführlicher Lösungsweg 3. Teil
Vorgehensweise bei 50 Kabeln:

  1. Schritt
    Möglichst lange und gleichzeitig viele Stränge bilden.
    Also 6 Stränge mit je 7 Kabel und einer mit 8.

Kurz:
6 x 7er-StUn und 1 x 8er-StUn
7 Tests.
Fall a):
5 x 7(8)-erStG1(Strang mit genau einem)
laut Tabelle in Teil 1 wären das weitere 15 Testungen (5x3)
zusammen also 22 Tests.

Fall b):
3 x 7er-StM1(Strang mit mindestens einem) und 1 x 8er-StM1
diese werden möglichst halbiert (also in 4er- und 3er-Stränge)
man erhält dann 3 x 3erStUn und 5 x 4erStUn
[Würde man nun genauso weiterverfahren, müßte man alle 8 Stränge testen und käme im (günstigen Fall auf 5 StG1) ungünstigsten Fall wieder auf 4 Stränge mit je mindestens einem Defekten. Diese wären maximal dann 16 Kabel und die lassen sich laut Teil 2 am besten einzeln testen.
Macht zusammen (7+7+16) 30 Tests.]
Jetzt kommt der spezielle Trick, den ich schon mal erwähnte:
Von den 8 Strängen werden nur 4 getestet , und zwar immer nur einen von dem jeweiligen Ursprungsstrang.
Folgendes ist nämlich bekannt:
Entweder hat ein Ursprungsstrang höchstens 2 defekte Kabel, wobei dann alle anderen genau 1 haben.
Oder aber alle enthalten genau 1.
Erhalte ich beim Testen ein positiven Strang muß das Gegenstück dazu mindestens 1 defektes Kabel haben.
Erhalte ich ein negatives Ergebnis, dann hat das Gegenstück höchstens in einem Fall genau ein defektes Kabel. In allen anderen Fällen aber keines.

Also sortiere ich die 8 Stränge in einen Haufen mit mindestens 1 defektem Kabel pro Strang und einen Haufen, indem entweder alle positiv sind, oder nur 1 Strang 1 defektes Kabel hat.
Den letztgenannten Haufen verbinde ich zu einem langen Strang und prüfe diesen ( 1 Test )aus maximal 8 Kabeln bestehenden Strang.

-Ist ist dieser negativ, dann enthält er genau ein defektes Kabel und kann mit 3 weiteren Tests ermittelt werden und die anderen 4 Stränge mit je maximal 4 Kabeln entalten auch genau 1 Defektes, welche auch durch 8 Tests (4 x 2) ermittelt werden können. Also zusammen dann
20 Testungen (7+1+3+8)

  • ist er positiv, heißt das, daß die 4 verbleibenden Stränge je mindestens 1 oder aber einer gar 2 Fehler aufweist.
    Da es maximal 16 Kabel sind, sind diese auch mit 16 Versuchen einzeln günstiger zu ermitteln. In dem Fall wären es dann 29 Testungen (7+1+3+16)

Fall c))
wir erhalten im ungünstgen Fall 2 x 7er-StM1 und 1 x 8er. StM1.
Also 3 Stränge mit mit mindestens einem Defekten.
Die teilen wir in 6 Stränge prüfen 6 ( 6 Testungen ) und erhalten dann wiederum im ungünstgen Fall 4 x 4er-StM1, die 16 Testungen notwendig machen.
Also 29 Tests insgesamt (7+6+16)

Fall d)
wir erhalten 2 StM1 aus insgesamt maximal 15 kabeln, die einzeln zu testen sind. Sind 15 Testungen plus die 7 von vorher, macht gesamt
22 Tests

Der schlechteste Fall war also b und c mit 29 notwendigen Tests