Taximetrikken

[Gustav]

Taximetrikken $d(x,y)$ er en avstandsfunksjon mellom to punkter $x=(a,b)$ og $y=(c,d)$ i planet, gitt ved $d(x,y)=|a-c|+|b-d|$.

La $S$ være en mengde bestående av punkter i planet slik at nøyaktig to ulike verdier forekommer for d(x,y) for alle distinkte punkter x og y i S.

Hva er maksimalt antall punkter i $S$?

Edit: omformulering

[Åberg]

Hvis dette skal være sant, kan må [tex]d(x,y) = 0 + |b-d|[/tex] eller [tex]d(x,y) = |a-c| + 0[/tex] som er kun sant hvis en kun kan bevege seg i X retning eller i Y retning omgangen, og hver gang en beveger seg i X retning og Y retning så beveger seg en i en fast distanse?

Da må:

[tex]S = (a + m|a-c|, b + n|b-d|)[/tex] hvor [tex]m,n\in \mathbb{Z}[/tex]

[Åberg]

Beklager, tror ikke jeg har forstått spørsmålet riktig. Det er derfor forrige svar sikkert virket veldig dumt

Men kan det være 4 punkt, som tar form som et kvadrat (hvor alle sider er like lange)?

[stensrud]

Taximetrikken $d(x,y)$ er en avstandsfunksjon mellom to punkter $x=(a,b)$ og $y=(c,d)$ i planet, gitt ved $d(x,y)=|a-c|+|b-d|$.

La $S$ være en mengde bestående av punkter i planet slik at nøyaktig to ulike verdier forekommer for d(x,y) for alle distinkte punkter x og y i S.

Hva er maksimalt antall punkter i $S$?

Edit: omformulering

Har løst denne før, så skal ikke ødelegge moroa for noen andre. Men, løste du den uten spoiler alert? For meg virker det som oppgaven var veldig enkel hvis du kjente til det, men tilsvarende vanskelig hvis du ikke gjorde det.

[Gustav]

Taximetrikken $d(x,y)$ er en avstandsfunksjon mellom to punkter $x=(a,b)$ og $y=(c,d)$ i planet, gitt ved $d(x,y)=|a-c|+|b-d|$.

La $S$ være en mengde bestående av punkter i planet slik at nøyaktig to ulike verdier forekommer for d(x,y) for alle distinkte punkter x og y i S.

Hva er maksimalt antall punkter i $S$?

Edit: omformulering

Har løst denne før, så skal ikke ødelegge moroa for noen andre. Men, løste du den uten spoiler alert? For meg virker det som oppgaven var veldig enkel hvis du kjente til det, men tilsvarende vanskelig hvis du ikke gjorde det.

Løste den uten Erdös-Szekeres ja. Brukte et slags geometrisk argument der jeg konstruerte mengden utfra snittet mellom "sirkler" om to punkter i S. Med "sirkel" mener jeg da mengder på formen $\{x\in\mathbb{R}^2| d(x,y)=r\}$, som jo er kvadrater rotert 45 grader.

Observerte først at maksimalt antall elementer i S må være større enn 9. Deretter at de to manhattenavstandene må være r og 2r (hvis ikke vil S bestå av færre enn 9 elementer).



Hvis A og B er med i mengden må f.eks. alle andre punkter ligge som illustrert her. Det er lett å se at hvis et punkt ligger utenfor de blå, på de svarte linjene, så vil mengden maksimalt ha færre enn 9 punkter. Så vi står da igjen med de 16 blå punktene. Utfra det er det lett å argumentere for at maks 9 av de igjen kan være med i S.