Usb verlängerungskabel(0.5m) und usb stick

es ist ein rätsel, auch wenn es der titel nicht vermuten lässt:wink:

es gibt eine produktion von hundert usb-verlängerungskabel, 5 davon funktionieren nicht. man hatt nun eine menge von
a.) 10 kabeln,
b.) 20 kabeln,
c.) 50 kabeln,
die zufällig aus der produktion ausgewählt wurden.
man hat ein notebook, mit einem funktionierendem usb-hub und ein funktinoierender usb-stick. wie viele versuche braucht man mindestens, um die nicht funktinierenden kabel auszusondern?

a b und c sind verschiedene voraussetzungen, unter denen das rätsel gelöst werden soll. pro versuch heisst: man kann beliebig viele kabel zusammenstecken, am einen ende das notebook und am anderen der stick, danach wird am notebook geprüft, ob eine verbindung zum stick besteht(=alle beteiligten kabel funktionieren) oder nicht(=mindestens eines funktioniert nicht)
besonders ist zu beachten, dass es sein kann, dass sich in den zufällig gewählten mengen alle 5 oder keines der 5 defekten kabel befinden können.

viel spass

erster Versuch:wenn man extrem viel Glück hat…
10 Kabel:mindestversuche 1
man nimmt 5 Kabel,es steht ne Verbindung und die anderen 5 sind kaputt^^

bei 20 und 50 dasselbe^^ also 3 und 9

ernsthafte Taktik
ich änder deine Fragestellung in höchstversuche um 100% sicher zu sein

10 Kabel:
man macht 2 Kabel zusammen

1-2 gibt es Kontakt ok 2 gute

ist eines kaputt geht es weiter
2-3 zusammen…ist es diesmal ok ist 1 kaputt und 2+3 in Ordnung
geht es diesmal nicht können 2 oder 3 kaputt sein
nun nimmt man 3+4
geht es diesmal durch ist 2 kaputt,weil sonst 2+3 funktioniert hätte
geht es nicht durch nimmt man 4+5 usw.
ist nie eines ok sind entweder ALLE Ungeraden oder Geraden kaputt,denn sonst gäbe es immer irgendwannmal ein Paar das funktioniert

= 9 höchstversucche

bei 20 würde ich wohl 2 nehmen
und jeweils 2 neue…bleiben höchstens 10 über,dann die 10er-taktik

=10+9=19 Höchstversuche

bei 50 5 und immer mit 5 neuen,denn es gibt mindestens 5 5er die funktionieren
dann bleiben noch höchstens 25 über
dann die 20ertaktik bleiben wieder höchstens 10 über

= 10+10+9 = 29 Höchstversuche

es geht natürlich auch anders
man nimmt 1 und steckt zusammen
wenns funktioniert 2 an 1 dran ,wenn nicht nur 2 dran
bei 50 wäre es natürlich interessant und es wäre weniger Arbeit vom hin und herstecken her…selbst wenn es auf 5 begrenzt wäre

Frage
Hallo,

geht es darum, eine optimale Strategie zu finden, oder geht es lediglich um die Lösung des Rätsels?

es gibt eine produktion von hundert usb-verlängerungskabel, 5
davon funktionieren nicht. man hatt nun eine menge von
a.) 10 kabeln,
b.) 20 kabeln,
c.) 50 kabeln,

Man braucht mindestens 5 Versuche, egal wieviele Kabel es insgesamt sind.

Gruss,
TR

dat hatte ich dochschon :frowning:

es tut mir leid, wenn ich es nicht richtig formuliert habe.
man sollte eine taktik finden, mit derm man sicher alle defekten kabel aussondern kann, eigentlich ist die kleinste maximale zahl gesucht
(ich dachte an eine ähnliche vorgehensweise wie bei den wiege rätsel)

dann hab ich ja schon richtig interpretiert
nur hab ichs jetzt nicht genau ausgerechnet

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

Versuch
Hallo,

Gesucht ist diejenige Strategie, die die minimale Höchstanzahl Messungen ergibt, und nicht die minimale durchschnittliche Anzahl Messungen (was betriebswirtschaftlich besser wäre).

Eine „fertige“ Lösung hab ich nicht, aber ein paar Ansätze.
Ich beschränke mich mal auf den Fall n=50

  1. Schritt.
    Messe 25 mal jeweils 2 Kabel.
    Danach verbleiben maximal 10 Kabel, die als Defekte in Frage kommen.

  2. Schritt.
    Fall a) 10 kabel übrig -> 5 weitere Messungen notwendig
    Fall b) 8 Kabel übrig -> 7 Messungen notwendig, das ist auch der Worst case.
    –> 25 +7 = 32

Analog komme ich bei n=20 auf 17, und bei 10 auf 9.

Gruss,
TR

hi,
ich denke, man muss für die optimale(n) strategie(n) auch die wahrscheinlichkeiten der einzelnen fälle berücksichtigen. diese wahrscheinlichkeiten berechnen sich aus

wsk(k defekte unter n gezogenen) =
= (g-d über n-k) . (d über k) / (g über n)

wobei g die gesamtzahl der kabel ist (hier also 100), d die gesamtzahl der defekten (hier also 5), n die gesamtzahl der verwendeten (hier also 10, 20 bzw. 50) und k die zahl der defekten unter den gezogenen (hier also 0, 1, 2, 3, 4 oder 5)

diese wahrscheinlichkeiten betragen (auf 4 kommastellen gerundet):

n / k 0 1 2 3 4 5
10 0,5838 0,3394 0,0702 0,0064 0,0003 0,0000
20 0,3193 0,4201 0,2073 0,0478 0,0051 0,0002
50 0,0281 0,1529 0,3189 0,3189 0,1529 0,0281

d.h. z.b.: die wahrscheinlichkeit, bei 20 kabeln genau 2 defekte dabei zu haben, ist 0,2073 oder ca. 20,73%

die optimalen strategien schauen in den verschiedenen fällen vermutlich verschieden aus. bei 10 kabeln ist in über 58% der fälle kein defektes dabei; in gut einem drittel der fälle exakt eines; in ca. 7% der fälle sind es 2. 3 oder mehr sind sehr selten.

bei 50 kabeln muss man damit rechnen, dass 2 oder 3 defekte dabei sind (insgesamt fast 64% der fälle), auch 1 oder 4 können gut vorkommen (insgesamt mehr als 30%), 0 oder 5 sind relativ selten (knappe 6% aber immerhin).

bei 10 kabeln besteht eine erfolgreiche strategie vermutlich darin, zunächst alle 10 kabel auszuprobieren. funktionieren sie, sind mit einem versuch alle 10 als korrekt nachgewiesen, was in über 58% der fälle passieren wird.

in gut einem drittel der fälle ist bei n=10 exakt 1 defektes kabel dabei. das lässt sich durch aufteilung 5:5, und dann 2:3 und dann 1:1 bzw. 1:2 in maximal 4 schritten herausfinden.

in relativ seltenen 7% der fälle haben wir 2 defekte kabel.

usw.
ich bin noch weit davon entfernt, generelle lösungen zu haben.
m.

es ist ein rätsel, auch wenn es der titel nicht vermuten
lässt:wink:

es gibt eine produktion von hundert usb-verlängerungskabel, 5
davon funktionieren nicht. man hatt nun eine menge von
a.) 10 kabeln,
b.) 20 kabeln,
c.) 50 kabeln,
die zufällig aus der produktion ausgewählt wurden.
man hat ein notebook, mit einem funktionierendem usb-hub und
ein funktinoierender usb-stick. wie viele versuche braucht man
mindestens, um die nicht funktinierenden kabel auszusondern?

a b und c sind verschiedene voraussetzungen, unter denen das
rätsel gelöst werden soll. pro versuch heisst: man kann
beliebig viele kabel zusammenstecken, am einen ende das
notebook und am anderen der stick, danach wird am notebook
geprüft, ob eine verbindung zum stick besteht(=alle
beteiligten kabel funktionieren) oder nicht(=mindestens eines
funktioniert nicht)
besonders ist zu beachten, dass es sein kann, dass sich in den
zufällig gewählten mengen alle 5 oder keines der 5 defekten
kabel befinden können.

sechs setzen
hast du die Aufgabe falschverstanden???

„…5 davon funktionieren nicht…“

die 5 sind Fakt und keine zu berechnende Variante

bei 10 heisst des:

bei Kabel 1 bedeutet dies eine wahrscheinlichkeit von 5:10 = 1:2

bei Kabel zwei(9 sind über) 1:1,8+1:2,25 = 1:2,025 weil Variante 1 (Kabel 1 ist defekt)+V2(Kabel 2 ist ok)

usw.

da das Optimum immer 1 ist und der schlechteste Fall von mir auch berechnet wurde…

egal…du hast eine komplett andere Aufgaber gelöst

hast du die Aufgabe falschverstanden???

„…5 davon funktionieren nicht…“

die 5 sind Fakt und keine zu berechnende Variante

die 5 sind laut aufgabentext 5 der zur auswahl stehenden 100. ob sie in den ausgewählten 10, 20 oder 50 drin sind, hängt von der auswahl ab.

ich glaube, du irrst, du depp. setz dich selbst, ganz egal ob mit sechs oder nicht.
m.

Hallo,

Gesucht ist diejenige Strategie, die die minimale Höchstanzahl
Messungen ergibt, und nicht die minimale durchschnittliche
Anzahl Messungen (was betriebswirtschaftlich besser wäre).

Eine „fertige“ Lösung hab ich nicht, aber ein paar Ansätze.
Ich beschränke mich mal auf den Fall n=50

  1. Schritt.
    Messe 25 mal jeweils 2 Kabel.
    Danach verbleiben maximal 10 Kabel, die als Defekte in Frage
    kommen.

  2. Schritt.

Fall b) 8 Kabel übrig -> 7 Messungen notwendig, das ist
auch der Worst case.
–> 25 +7 = 32

Analog komme ich bei n=20 auf 17,

da issn Denkfehler oder??

einmal kommste bei

Fall a) 10 kabel übrig -> 5 weitere Messungen notwendig

und dann

und bei 10 auf 9 (Versuche)

d.h.25+9=34
bei meinen Berechnungen war ich aber schon sehr viel niedriger
ausserdem gibt es nur einen worst case
nämlich den das immer nur 1 defektes Kabel vorkommt

es gilt 5 zu finden
man kann z.b. auch 50 Kabel hintereinander stecken…dummerweise sind dann immer alle Versuche defekt
das ganze gilt bis zu 50/x

sorry
ach sorry du hast recht
ich bin von 5 in der jeweiligen Menge ausgegangen

aber…
man muss doch vom worst case ausgehn d.h. die 5 sind in der jeweiligen Menge …

man muss doch vom worst case ausgehn d.h. die 5 sind in der
jeweiligen Menge …

ich versteh das rätsel so, dass man eine möglichst erfolgreiche strategie entwerfen soll - unabhängig davon / nichts wissend darüber, wie viele der defekten kabel in der auswahl sind.
das macht die sache erst interessant. der „worst case“ für sich ist ja relativ simpel.

und gereizt hat mich natürlich dein arrogantes „setzen sechs“ … und auf einen groben klotz gehört ein grober keil.

m.

Was irgendwie alle nicht beachten…: den usb-hub!
Ich glaube der Fragesteller bezieht sich darauf, dass durch den Hub, bei einer Prüfung im Wechsel, die Leitung zum Hum und vom Hub gleichzeitig, mit nur einem Umstecken geprüft werden kann… wah?

Dies beachtet auch keiner:

besonders ist zu beachten, dass es sein kann, dass sich in den
zufällig gewählten mengen alle 5 oder keines der 5 defekten
kabel befinden können.

…wobei ich mich frage, ob bzw warum nicht 1, 2, 3 und 4 möglich sind.

mfg

hab ich ja verstanden(„sorry“)

meine Strategie wäre halt wie ich es beschrieben habe
denn so würde es beim nicht worst case nicht allzulange dauern

ich hab mir nur überlegt ob es sich lohnen würde vorher mit 5x10er schonmal zu sieben…dann könnte man aber trotzdem nicht ausschliessen das es 5 sind(nur enger verteilt)
aber des wäre mit 5ern wohl effektiver
dann wäre 50% auf jedenfall raus vll auch 30 von 50

Anmerkung
Hallo,

ich verstehe die Aufgabe anders, und der Ursprungsposter hat das ja im nachhinein nochmal klargestellt.
Gesucht ist eine Strategie, die die maximal zu benötigende Testanzahl minimiert.
Du hingegen suchst eine Strategie, die die durchschnittliche Anzahl benötigter Tests minimiert. Das ist auch meines Erachtens sinnvoller, aber leider nicht gefragt.

Gruss,
TR

Lösung:lange Version
also gehts es mit 8 weiter,eigentlich mit 9 aber es wären 5 ausgeschlossene…
man muss die höchste Ausschlusszahl finden

sind 6 Versuche =5x8=40 über =6 Versuche 6x8 =48 2 über
im worst case bleibt die höchste Zahl über also 5x8 d.h.10:6 aussortiert

bei 7 sind es 5x7 über bei 7 Versuchen 15:7 raus
bei 6 sind es 5x6 über bei 8 Versuchen 20:8 = 2,5
bei 5 sind es 5x5 über bei 10 Versuchen 25:10 =2,5
bei 4 sind es 5x4 über bei 12 Versuchen 30:12 = 2,5
bei 3 sind es 5x3 über bei 16 Versuchen 35:16 = 2,1875
bei 2 sind es 5x2 über bei 25 Versuchen =1,6…
bei 1 sind es 5x0 über bei 50 Versuchen die defekten würden gefunden

nehmen wir die 9
45 über um weiterzumachen muss man zumindest mit 1 Versuch 5 weitere ausschliessen
wir teilen durch 8
5 weg aber 5 Versuche
= 10
mit der 5 sind es aber 25…

7:6 Versuche 10 weg -15 bei 11 Versuche
6:7 Versuche 15 weg -20
5:9 Versuche 20 weg -25
4:11 Versuche 25 weg -30

alles schlechter als die anderen Werte

die 8
10 weg bei 6 Versuchen

40 über

7:5 Versuche 5 weg…
6:6 Versuche 10 weg…
5:8 Versuche 15 weg…25:14 1,78
4:10 Versuche 20 weg…30:16 =1,875
3:13 Versuche 25 weg… 35:19 =1,842

die 7
bei 7 sind es 5x7 über bei 7 Versuchen 15:7 raus

35 über
6:5 Versuche 5 weg…
5:7 Versuche 10 weg…
4:8 Versuche 15 weg…-30 schlechter als direkt 3
3:11 Versuche 20 weg…

bei 6 sind es 5x6 über bei 8 Versuchen 20:8 = 2,5
30 über

5:6 Versuche 5 weg
4:7 Versuche 10 weg
3:10 Versuche 15 weg bringt genausoviel wie direkt 3

bei 5 sind es 5x5 über bei 10 Versuchen 25:10 =2,5
25 über
4:6V 5weg 30:16
3:8V 10weg 35:18 = beste
2:12V 15 weg 40:22

bei 4 sind es 5x4 über bei 12 Versuchen 30:12 = 2,5

20 rest

3:6V 5weg 35:18
2:10V 10 weg 40:22

bei 3 35:16
15 über
2:7 Versuche = 40:23 also schlechter

also ist der bisherige Weg:

erst mit 5erVerbindungen 10 Versuche 25 über
dann mit 2ern + 12 Versuche 40 insgesamt weg
40:22

oder

4er mit 12 Versuchen 30 weg
dann 2er mit 10 Versuchen 40 insgesamt weg
40:22

bei 10 Rest muss man mit 9 1ern agieren…

22+9 = 31 Versuche

Lösung:shortcut
erst mit 5erVerbindungen 10 Versuche 25 über
dann mit 2ern + 12 Versuche 40 insgesamt weg
40:22

oder

4er mit 12 Versuchen 30 weg
dann 2er mit 10 Versuchen 40 insgesamt weg
40:22

bei 10 Rest muss man mit 9 1ern agieren…

22+9 = 31 Versuche