Zadanie Steinhausa

05.04.07, 15:35
Dane są dwa trójkąty o bokach odpowiednio a, b, c i a1, b1, c1. Jakie są
warunki konieczne i wystarczające, żeby w pierwszym trójkącie można było
umieścić drugi ?

To zadanie zamieścił prof. Hugo Steinhaus w swojej książeczce "sto zadań", w
rozdziale ostatnim zatytułowanym "zadania bez rozwiązań". Autor uprzedził, że
niektóre z podanych tam zadań nie posiadają znanych rozwiązań.
Czy ktoś zna rozwiązanie TEGO zadania ?
    • mikronezja Pewnie okrąg opisany na a1,b1,c1 musi mieć 05.04.07, 16:00
      promień mniejszy lub równy okręgowi wpisanemu w trójkąt a,b,c. Wtedy się zawsze
      da umieścić ... tak mi się wydaje.
      • Gość: gość Re: Pewnie okrąg opisany na a1,b1,c1 musi mieć IP: *.mimuw.edu.pl 05.04.07, 16:47
        Wtedy - oczywiście. Ale nie "wtedy i tylko wtedy" (wystarczy pomyśleć o dwóch
        trójkątach równobocznych o prawie tej samej wielkości), a chodzi o warunek
        równoważny (wystarczający I dostateczny).
    • Gość: gość Re: Zadanie Steinhausa IP: *.mimuw.edu.pl 05.04.07, 16:44
      Podejrzewam, że dla trójkątów odpowiedź jest znana (ale może być całkiem
      skomplikowana). Oczywiście mając konkretny zestaw danych a,b,c,a1,b1,c1,
      łatwo kwestię rozstrzygnąć - kłopot może być z podaniem precyzyjnej formuły w
      języku używającym tylko tych wielkości (nawet głupi wzór Herona na pole
      trójkąta o znanych bokach nie jest bynajmniej prosty), a także ze wskazaniem
      algorytmu, który rzecz rozstrzygałby w KAŻDYM przypadku. Ale odpowiedzi nie
      znam, a problem jest ciekawy choćby ze względu na zastosowania. Analogiczne
      pytania można zadać dla czworościanów i bardziej złożonych brył czy figur,
      wtedy robi się już chyba beznadziejnie.

      Z prostych obserwacji - muszą zachodzić oczywiste nierówności między polami
      powierzchni, obwodami i średnicami (średnicą trójkąta jest jego najdłuższy bok).
      Także koło wpisane w "mniejszy" trójkąt musi mieć nie większy promień niż to
      wpisane w "większy" (analogiczny fakt dla okręgów opisanych nie musi
      zachodzić!). Podejrzewam jednak, że sprawdzenie tych czterech parametrów nie
      wystarcza. Byłbym trochę zdziwiony, gdyby istniała jakaś prosta reguła.
    • Gość: gość Re: Zadanie Steinhausa - odpowiedź IP: *.mimuw.edu.pl 12.04.07, 10:12
      Przez święta trochę nad tym pomyślałem i znam już mniej więcej odpowiedź -
      "mniejszy" trójkąt można umieścić w "większym" wtedy i tylko wtedy, gdy można
      go w nim umieścić w taki sposób, by jeden z boków "mniejszego" trójkąta był
      zawarty w jakimś boku "większego" trójkąta. (Dowód tego faktu jest prostym
      zadaniem z programowania liniowego, spiszę to i wklepię za jakiś czas). To już
      redukuje zagadnienie do rozważenia skończonej liczby przypadków (ok. osiemnastu
      - 3 boki x 3 boki x dwie orientacje - to ostatnie, jeśli dopuszczamy
      odbijanie "mniejszego" trójkąta, a nie tylko jego obracanie i przesuwanie),
      choć wypisanie explicite kryterium jako funkcji parametrów a, b, c, a1, b1, c1
      jest wciąż katorżniczą robotą (ale jedynie żmudną i raczej bezsensowną, nie
      zaś - niewykonalną).

      Co ciekawe, dowód silnie korzysta z tego, że rzecz dzieje się na płaszczyźnie.
      Podejrzewam, że analogiczne kryterium dla dwóch czworościanów w przestrzeni nie
      jest prawdziwe (np. jeśli czworościan foremny wsadzimy między dwie równoległe
      płaszczyzny zawierające dwie przeciwległe krawędzie tego czworościanu, to
      czworościanu foremnego tej samej wielkości nie da się między nie wsunąć tak, by
      któraś z jego ścian była równoległa do tych płaszczyzn) - teraz można te dwie
      płaszczyzny potraktować jako dwie ściany dużego spłaszczonego czworościanu...
      - ale tu trzeba trochę uściślić.
      • Gość: gość Re: Zadanie Steinhausa - dowód IP: *.mimuw.edu.pl 16.04.07, 17:10
        Przepraszam za brak polskich liter, nie powinno to chyba utrudnic
        powaznie lektury. Najpierw wyjasnie, co rozumiem przez orientacje:
        na plaszczyznie sa dwa typy trojkatow o bokach 3, 4, 5 - takie, po ktorych
        obwodzie idac od boku najkrotszego, poprzez bok o dlugosci 4, az do boku
        najdluzszego poruszamy sie zgodnie z ruchem wskazowek zegara (wokol wnetrza
        trojkata) i takie, po ktorych ruch ten odbywa sie w kierunku przeciwnym do
        ruchu wskazowek zegara. Te dwie klasy mozna nazwac orientacjami i ma to
        sens takze dla kazdego innego zestawu parami roznych dlugosci bokow.
        Dla trojkata rownoramiennego nie ma potrzeby rozwazania tego pojecia.
        Operacje takie jak przesuniecie, obrot czy jednokladnosc nie zmieniaja
        orientacji, natomiast symetria (odbicie) wzgledem prostej - zmienia.
        Zadanie Steinhausa mozna rozwazac w dwoch wariantach - przy zadaniu
        konkretnej orientacji lub przy dopuszczeniu swobody w tym wzgledzie.
        W pierwszym przypadku trojkata o bokach 3, 4, 5 nie mozna wlozyc w trojkat
        o bokach 5, 4, 3 (boki w kolejosci zgodnej z ruchem wskazowek zegara)
        - w drugim natomiast oczywiscie mozna. Zadanie w drugim wariancie jest
        oczywiscie rownowazne dwom zadaniom w pierwszym wariancie (chyba ze
        "mniejszy" lub "wiekszy" trojkat jest rownoramienny i wtedy miedzy oboma
        wariantami nie ma roznicy). Pokaze wiec, jak rozwiazac zadanie Steinhausa
        w pierwszym wariancie. Ponadto rozwiazemy problem ogolniejszy: majac dane
        dwa zestawy dlugosci bokow a, b, c i a1, b1, c1, znajdziemy najwiekszy
        trojkat o bokach ta, tb, tc (z ta konkretna orientacja, a wiec bedacy
        obrazem trojkata o bokach a, b, c w jednokladnosci o skali t, potem jeszcze
        ewentualnie obroconym i przesunietym) mieszczacy sie w trojkacie o bokach
        a1, b1, c1 (i znow tej wlasnie orientacji). Jesli da sie to zrobic
        dla pewnego t wiekszego od (lub rownego) 1, to jest to oczywiscie zarazem
        rozwiazanie problemu Steinhausa (w "powiekszonym trojkacie" o bokach ta,
        tb, tc miesci sie tym bardziej trojkat o bokach a, b, c), a jesli
        najwieksza skala t, dla ktorej mozna tego dokonac, jest mniejsza od 1,
        to wynika stad, ze odpowiedniego "wlozenia Steinhausa" oczywiscie w tym
        przypadku nie bedzie. Ze w ogole takie maksymalne t istnieje, wynika
        ze standardowych argumentow zwartosciowych, ktore powinny byc kazdego, kto
        przeszedl podstawowy kurs analizy, dosc jasne. Udowodnimy, ze owo optymalne
        (a wiec z maksymalna wartoscia parametru t) upakowanie przeskalowanej kopii
        trojkata o bokach a, b, c w "wiekszym" trojkacie o bokach a1, b1, c1 jest
        osiagane wtedy, gdy ktorys bok owej kopii lezy na tej samej prostej,
        co ktorys bok "wiekszego" trojkata (a wiec jest w tym boku "wiekszego"
        trojkata zawarty). W szczegolnosci latwo stad wywnioskowac podobna
        konkluzje w oryginalnym problemie Steinhausa (tyle, ze tam "mniejszy"
        trojkat mozna czesto przesuwac, bo jest wiecej luzu, a wiec prawdziwa jest
        tylko implikacja, ze jesli w ogole da sie wlozyc, to TAKZE i w taki sposob,
        by ktorys bok "mniejszego" trojkata wyladowal na ktoryms z bokow
        "wiekszego" - ale niekoniecznie TYLKO w ten sposob).

        Teraz szczegoly techniczne dowodu. Wybieramy na plaszczyznie zespolonej C
        jakies trzy liczby zespolone z1, z2 i z3 takie, by trojkat o wierzcholkach
        z1, z2 i z3 mial boki dlugosci a, b, c (w zadanej orientacji). Wybieramy
        tez na plaszczyznie zespolonej C trzy polplaszczyzny P1, P2 i P3 tak,
        by ich czescia wspolna byl trojkat o bokach a1, b1 i c1 (znow o wlasciwej
        orientacji) - proste bedace brzegami tych polplaszczyzn zawieraja
        boki tego "wiekszego" trojkata. Teraz rozwazamy liczby zespolone x i y.
        Funkcja liniowa f(z)=xz+y odwzorowujaca C w C jest zlozeniem jednkladnosci
        o skali |x| (wartosc bezwzgledna czyli modul x) z obrotem o kat rowny
        argumentowi liczby zespolonej x i pewnym przesunieciem. W szczegolnosci
        f(z1), f(z2) i f(z3) beda wierzcholkami pewnego trojkata o bokach |x|*a,
        |x|*b, |x|*c (w odpowiedniej orientacji). Oczywiscie, aby ten trojkat byl
        zawarty w "wiekszym" trojkacie, potrzeba i wystarcza, by punkty f(z1),
        f(z2) i f(z3) nalezaly do polplaszczyzn P1, P2 i P3:

        x*z1+y nalezy do P1,
        x*z1+y nalezy do P2,
        x*z1+y nalezy do P3,
        x*z2+y nalezy do P1,
        x*z2+y nalezy do P2,
        x*z2+y nalezy do P3,
        x*z3+y nalezy do P1,
        x*z3+y nalezy do P2,
        x*z3+y nalezy do P3.

        Jesli przez A oznaczymy zbior wszystkich par liczb zespolonych (x,y)
        (a wiec bedzie to pewien podzbior C^2), to latwo zobaczyc, ze jest on
        czescia wspolna dziewieciu polprzestrzeni (czterowymiarowych; tak jak
        prosta dzieli plaszczyzne na dwie polplaszczyzny, a plaszczyzna przestrzen
        trojwymiarowa na dwie polprzestrzenie, rowniez trojwymiarowa podprzestrzen
        afiniczna dzieli przestrzen czterowymiarowa C^2 = R^4 na dwie
        czterowymiarowe polprzestrzenie) odpowiadajacych powyzszym dziewieciu
        warunkom. Wynika stad natychmiast, ze zbior A jest wypukly. Jest on takze
        oczywiscie ograniczony (|x| nie moze byc zbyt duze, co wynika np.
        z porownania pol trojkatow, a stad wynika juz takze, ze i |y| musi byc
        ograniczone) i domkniety, a wiec jako przeciecie skonczonej liczby
        polprzestrzeni jest on po prostu pewnym czterowymiarowym wieloscianem
        wypuklym. Funkcja g(x,y)=|x| jest, jak latwo sprawdzic, wypukla, wiec
        na wieloscianie wypuklym A przyjmuje maksimum w ktoryms z jego
        wierzcholkow (punktow ekstremalnych). Przypominam, ze chcemy te funkcje
        zmaksymalizowac, bo to ona mierzy skale t powiekszenia naszego "mniejszego"
        trojkata. Wierzcholek czterowymiarowego wieloscianu wypuklego musi nalezec
        do co najmniej czterech (trojwymiarowych) scian - podobnie, jak np.
        w wierzcholku trojwymiarowego wieloscianu wypuklego musza zbiegac sie
        co najmniej trzy dwuwymiarowe sciany. Zatem co najmniej czetry sposrod
        wypisanych powyzej dziewieciu nierownosci liniowych musza byc dla tej pary
        (x,y) rownosciami. Teraz wystarczy zauwazyc, ze nie moga jednoczesnie
        zachodzic rownosci we wszystkich trzech warunkach dotyczacych z1, bo
        punkt f(z1) nie moze lezec jednoczesnie na brzegu polplaszczyn P1, P2 i P3
        (te trzy proste brzegowe nie przecinaja sie przeciez w jednym punkcie).
        Podobnie nie moga zachodzic jednoczesnie rownosci we wszystkich trzech
        warunkach dotyczacych z2, ani jednoczesnie we wszystkich trzech warunkach
        dotyczacych z3. Zatem spelnione sa jednoczesnie dwie rownosci dotyczace P1
        lub dwie dotyczace P2, lub dwie dotyczace P3. To zas odpowiada temu, ze
        ktores dwa sposrod punktow f(z1), f(z2), f(z3) znajduja sie na brzegu tej
        samej z polplaszczyzn P1, P2 lub P3, a wiec laduja na ktoryms z bokow
        "wiekszego" trojkata. To konczy dowod.

        To naprawde jest bardzo proste, jesli ma sie odrobine doswiadczenia
        z geometria liniowa; mam nadzieje, ze ten dowod bylby czytelny dla
        wiekszosci studentow drugiego roku studiow matematycznych (choc wymaga
        przemyslenia). To zreszta fajny przyklad, jak geometria wysokowymiarowa
        przydaje sie do problemu dwuwymiarowego, niemalze go trywializujac.

        Co do analogu trojwymiarowego, nie jest prawda, ze optymalne wkladanie
        kopii jednokladnej jednego czworoscianu w drugi jest realizowane w podobny
        sposob, czyli tak, by ktores dwie dwuwymiarowe sciany tych czworoscianow
        znajdowaly sie na tej samej plaszczyznie. Podobnie, nie jest w trzech
        wymiarach prawda, ze jesli mozliwe jest "Steinhausowskie" wlozenie,
        to jest ono takze mozliwe w taki sposob, by ktores dwie sciany lezaly
        na tej samej plaszczyznie. Zeby to zobaczyc, wystarczy zerknac na przyklad
        wymieniony w poprzednim moim poscie. Zamiast dwoch rownoleglych plaszczyzn
        mozna wziac uczciwy, ale bardzo rozplaszczony czworoscian. Detale
        obliczeniowe pozostawiam chetnym, idea jest jasna.

        Oczywiscie mozna pokazac, ze wlozenie "Steinhausowskie" symleksu w sympleks
        (sympleks dwuwymiarowy to trojkat, a trojwymiarowy to czworoscian) w n
        wymiarach istnieje wtedy i tylko wtedy, gdy istnieje wlozenie
        "Steinhausowskie" takie, ze wszytkie poza co najwyzej jednym wierzcholkiem
        "mniejszego" sympleksu laduja na brzegu "wiekszego" (idea jest taka
        • Gość: gość Re: Zadanie Steinhausa - korekta IP: *.mimuw.edu.pl 16.04.07, 17:12
          Dopiero teraz zauważyłem, że w wersji Indrisowskiej to a1, b1, c1 wkłada się w
          a, b, c, odwrotnie niż u mnie (co oczywiście jest wyłącznie kwestią notacyjną),
          bez wpływu na rozumowanie.
        • Gość: gość koniec dowodu (zżarło) IP: *.mimuw.edu.pl 16.04.07, 18:20
          Oczywiscie mozna pokazac, ze wlozenie "Steinhausowskie" symleksu w sympleks
          (sympleks dwuwymiarowy to trojkat, a trojwymiarowy to czworoscian) w n
          wymiarach istnieje wtedy i tylko wtedy, gdy istnieje wlozenie
          "Steinhausowskie" takie, ze wszytkie poza co najwyzej jednym wierzcholkiem
          "mniejszego" sympleksu laduja na brzegu "wiekszego" (idea jest taka - jesli
          w ogole da sie wlozyc, to przesuwajac da sie wlozyc tak, by ktorys
          wierzcholek wyladowal na brzegu, wtedy juz go trzymamy i poruszamy dalej
          "mniejszym" sympleksem, az znow jakis wierzcholek dotknie brzegu
          "wiekszego" sympleksu, wtedy jego tez juz trzymamy w miejscu itd. - dopoki
          nie chwycimy za wszystkie poza jednym wierzcholki, wciaz mamy swobode ruchu
          - to oczywiscie tylko szkic rozumowania, ale latwy do uscislenia). Taka
          redukcja wciaz jednak pozostawia do rozwazenia mnostwo przypadkow
          (jest duzo stopni swobody) i niewiele w zwiazku z tym pomaga...

          Zainteresowanych zachecam do przemyslenia nastepujacej kwestii:
          co konkretnie sypie sie w dowodzie dwuwymiarowym, gdy probujemy go
          przeniesc do wymiaru trzy (oczywiscie nie ma na to szans, bo teza nie jest
          prawdziwa)? Strukture algebraiczna zespolona mozna oczywiscie zastapic
          jezykiem operatorow liniowych i przesuniec, wiec nie calkiem tu jest
          problem. Podpowiedz: jaka wlasnosc ma rodzina afinicznych przeksztalcen
          konforemnych plaszczyzny, ktora nie przysluguje rodzinie afinicznych
          przeksztalcen konforemnych przestrzeni trojwymiarowej?

    • llukiz Re: Zadanie Steinhausa 12.04.07, 11:04
      przy oznaczeniu A>B>C i A1>B1>C1

      A1<A B1<B C1<C
      • Gość: gość Re: Zadanie Steinhausa IP: *.mimuw.edu.pl 12.04.07, 12:04
        Tak prosto to nie jest: np. w trójkąt o bokach 2, 2, 3 wsadzisz trójkąt
        równoramienny o ramieniu prawie 3 i małej podstawie (czyli np. 3-1/10, 3-1/10,
        1/100)...
Pełna wersja