Vollständige Induktion Gewichte

Question

Aufgabe:

Mit einem einzigen Gewichtssatz der Form {2^0kg, 2^1kg,..., 2^^(n-1)kg} kann man alle Gewichte 1kg, 2kg, 3kg,...,2^ⁿ -1kg zusammenstellen.

Beweise die Behauptung für alle n Element von N durch vollständige Induktion.

Problem/Ansatz

Zuerst habe ich

A(n): Alle Gewichte g ELement von {1,...,2^ⁿ -1} sind mit einem Gewichtssatz der Form g= ∑xi 2i (unter dem Summenzeichen i=0 und darüber n-1)mit x_i =0 oder 1 darstellbar.

Induktionsanfang

A(1): 2^¹-1=1 und x_i*2¹=2 für x_i =1

Induktionsvoraussetzung

Es sei n eine Zahl für die A(n) stimmt.

Zu zeigen:

g ELement von {1,...,2^ⁿ⁺¹ -1} => g=∑xi 2i (unter dem Summenzeichen i=0 und darüber n)

Nun würde ja der Induktionsschritt kommen, aber mit dem komm ich einfach nicht zurecht, ich dachte an Fallunterscheidung deswegen habe ich xi mit 0 und 1 gewählt.

Answer 1

Fallunterscheidung ist doch OK.

1. Fall g < 2^n . Dann ist das nach Ind.annahme darstellbar, sogar ohne das 2^n kg. Stück zu benutzen.

2. Fall g ≥ 2^n . Dann nehme ich das 2^n kg Stück und muss dann mit den übrigen

das restliche Gewicht von   g -2^n darstellen. Das geht lt. Ind.annahme, da der

Rest weniger als 2^n ist.

Comments

Aber mein Problem ist ich verstehe die Fallunterscheidung einfach nicht. Also ich verstehe noch die Fälle:

1 Fall. g<2^n und auch 2. Fall g>=2^n aber die Begründung, wie ich das beweisen kann versteh ich nicht.

Ich kann auch deiner Antwort oben nicht wirklich folgen, warum das so ist. Kann man das auc vielleicht noch anders erklären?

---

Aber ich seh grad mein Induktionsanfang is scho falsch

---

A(n)=Mit einem einzigen Gewichtssatz der Form {2^0kg, 2^1kg,..., 2^(n-1)kg} kann man alle Gewichte 1kg, 2kg, 3kg,...,2^n -1kg zusammenstellen.

A(1) wäre dann :Mit einem einzigen Gewichtssatz der Form {1kg} kann man alle Gewichte 1kg zusammenstellen.  Das sit wohl wahr.

Angenommen für ein n gilt A(n) .

Dann ist zu zeigen:  Mit einem einzigen Gewichtssatz der Form {2^0kg, 2^1kg,..., 2^(n-1)kg, 2^nkg} kann man alle Gewichte

1kg, 2kg, 3kg,...,2^(n -1)kg , 2^n kg zusammenstellen.

Dann wird auch vielleicht der Rest des Beweises klarer.

---

Ok danke mir is ds ganze jz schon klarer.

Ds bedeutet wenn ich g<2^n habe, dann bedeuted das so viel wie, ich will ein Gewicht mit dem Satz darstellen, was aber kleiner ist als 2^n und deswegen benötige ich das 2^n Gewicht gar nicht.

Bei Fall 2 da blick ich mich noch immer nd ganz durch, weil mein Gewichtssatz is ja gegeben bis 2^(n-1) und das Gewicht mit 2^n -1. Ich versteh hier einfach nicht wieso der Rest dann weniger ist als 2^n

Oder ich weiß jetzt nicht mehr bezieht sich das g jetzt auf den Gewichtssatz oder das Gewicht selbst :-/

---

Das g ist das Gewicht, was du darstellen sollst.

Wenn das größer oder gleich 2^n ist, dann brauchst du ja jedenfalls das 2^n - Gewichtsstück.

Und mit den anderen Gewichtsstücken musst du nur noch

den Rest, also  g - 2^n darstellen. Und weil das g kleiner ist als 2^n

klappt das laut Induktionsannahme.

---

So ist es schon klar, ich glaube ich häng einfach an dem +1.

Weil wenn man ja jetzt bei beiden n -> n+1 macht, dann habe ich bei den Gewichtssätzen {2^0,...,2^^n-1+1=2ⁿ) und bei den Gewichten {1,...,2⁽ⁿ⁺¹⁾-1} und so sind die Gewichte ja mehr, deshalb versteh ich nd wie ma ds darstellen kann. So wie du es oben hast versteh ichs schon aber nicht wieso da 2^n hinter beiden steht.

---

Bei den Gewichten, die du darstellen willst,

geht es ja - wie du richtig sagst - von 1 bis 2^(n+1)-1.

Und 2^n liegt dabei so ungefähr in der Mitte.

Die erste Hälfte ( bis 2^n - 1) kannst du ohne das

2^n -Gewichtsstück darstellen.

Deshalb ist der 1. Fall g < 2^n .

---

Ja genau, das versteh ich nun schon, aber wenn g>= 2^n ist, dann gibt es ja nur Gewichtssätze bis 2^n, aber wie kann man dann einen Gewichtssatz darstellen, der 2^(n+1)-1 ist? Oder funktioniert das, weil ich von dem 2^n abziehe und dann erhalte ich weniger als 2^n und das ist mit dem Rest der Gewichtssätze noch möglich darzustellen?

---

In deiner Formulierung

"dann gibt es ja nur Gewichtssätze bis 2n, aber wie kann man dann einen Gewichtssatz darstellen,..."

liegt schon ein gewisses Misverständnis.

Es müsste heißen

dann gibt es ja nur Gewichte bis 2^n, aber wie kann man dann ein Gewicht darstellen, ...

Wenn du z.B Beispiel 6 kg Kartoffeln abwiegen willst

(Das hier mit dem darstellen gemeint.) , dann genügt dazu der Gewichtssatz

1 , 2, 4 ; denn du nimmst die beiden Gewichte 2 und 4 und legst die auf eine

Seite der Waage und die Kartoffeln auf die andere.

---

Achsoo also wenn ich jz ein Gewicht darstellen will, dass größer als 2^n ist, dann brauch ich einmal das 2^n Gewicht und den Rest kann ich dann noch darstellen, da der Recht kleiner als 2^n ist. Ich glaub jetzt hab ich kapiert, wie das gemeint ist. Mir war glaub ich die ganze Aufgabe nicht verständlich.

Danke für deine Hilfe

Answer 2

"Mit einem einzigen Gewichtssatz der Form {2^0kg, 2^1kg,..., 2^(n-1)kg} kann man alle Gewichte 1kg, 2kg, 3kg,...,2^n -1kg zusammenstellen.

Beweise die Behauptung für alle n Element von N durch vollständige Induktion."

Wenn wir die Null noch als Gewicht hinzuziehen , können wir mit n wie oben beschriebenen sortierten Gewichten 2^n verschiedene Gewichte zusammen stellen.

Das gilt es zu beweisen.

Induktionsanfang

Ein Gewichte 2^{1-1}kg damit kann ich zwei verschieden Gewichte zusammen stellen,

0 kg und 1 kg bis 2^1-1 = 2-1 = 1 kg kann ich also die Gewichte zusammen stellen.

Induktionsannahme

Mit n Gewichten kann ich 2^n verschiedene Gewichte darstellen. Das entspricht den Zahlen von 0 bis 2^n - 1.

Nun fügen wir ein Gewicht 2^{(n+1)-1}kg hinzu.

Die oben erwähnten 2^n Gewichte können wir immer noch darstellen, doch nun können wir jeweils das neue Gewicht dazu legen oder weglassen, dadurch haben wir als doppelt soviel

$$2 *2^n =2^{(n+1)}$$

Möglichkeiten. D.h.wir können wie zu zeigen war, die Gewichte von

$$0 bis 2^{(n+1)}-1 kg$$ legen.

Induktionsschluss