Linealproblem in zwei Dimensionen

03/08/2009 - 21:42 von Rainer Rosenthal | Report spam
Vor Jahren gab es hier in dsm heftige Diskussionen
zum Linealproblem: Man kann mit einem Lineal L, das
die Marken 0, 1, 2, ... n besitzt, alle Strecken mit
Làngen in diesem Bereich messen, aber man kann das
auch tun, wenn einige dieser Marken fehlen.

Beispiel: Lineal L = 0-1-2-3-4

Alles was man damit messen kann, kann
man auch mit diesem Lineal messen, bei
dem einige Marken fehlen:

Lineal L' = 0-13-4

Mir ist nun eine zweidimensionale Variante eingefallen,
für die ich bereits eine einfache erste Aufgabe pràsen-
tieren kann.

Wir betrachten ein Gitter wie z.B. dieses:

03 - 13 - 23 - 33
| | | |
| | | | Hier steht xy kurz für (x,y)
02 - 12 - 22 - 32
| | | |
| | | |
01 - 11 - 21 - 31
| | | |
| | | |
00 - 10 - 20 - 30

Zwischen den Punkten (1,1) und (3,2) haben wir den
x-Abstand |1-3| = 2 und den y-Abstand |1-2| = 1.
Das Abstandspaar (2,1) kann natürlich auch zwischen
anderen Punkten des Gitters gefunden werden, z.B.
bei (1,0) und (3,1) oder auch bei (0,2) und (2,3).

Frage: Wieviele Punkte benötigt man im Gitter, um
alle Abstandspaare darstellen zu können?

Antwort: 6 (in Worten sechs).

Problem: wie hat man diese 6 Punkte zu wàhlen?

Gruss,
Rainer Rosenthal
r.rosenthal@web.de
 

Lesen sie die antworten

#1 Robert Figura
03/08/2009 - 22:29 | Warnen spam
Rainer Rosenthal schrieb:
Frage: Wieviele Punkte benötigt man im Gitter, um
alle Abstandspaare darstellen zu können?

Problem: wie hat man diese 6 Punkte zu wàhlen?





s
p
o
i
l






s
p
o
i
l







s
p
o
i
l









x-x-
-
x--x

Auf dem 5x5 Lineal habe ich 11 Verbaut. Wer bietet weniger?

Grüße
- Robert

/* mandlsig.c 0.42 (c) by Robert Figura */
I02;float O,o,i;main(l){for(;I--;putchar("oO .,t>neo.ckgel-t\
agidif@<ra urig FrtbeRo"[I%74?I>837&874>I?I^833:l%5:5]))for(O=o=l0;O*O+o*o<(16^l++);o=2*O*o+I/74/11.-1,O=i)i=O*O-o*o+I%74*.04-2.2;}

Ähnliche fragen