19. Türchen

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    • 19. Türchen

      Keine schöne Lösung, aber etwas Probieren hilft. Freund Java bestätigt:

      Java-Quellcode: Tag19.java

      1. package kalender;
      2. import java.util.*;
      3. import static java.lang.Math.abs;
      4. public class Tag19 {
      5. public static void main(String[] args){
      6. int a,b,c,d,e,f,g,h,i,j;
      7. int counter = 0;
      8. final int MAX=15;
      9. List<Integer> differences;
      10. for(a=1;a<=MAX;a++){
      11. for(b=1;b<=MAX;b++){
      12. System.out.println(a+ " "+b);
      13. if(b==a) continue;
      14. for(c=1;c<=MAX;c++){
      15. if(c==a) continue;
      16. if(c==b) continue;
      17. for(d=1;d<=MAX;d++){
      18. if(d==a) continue;
      19. if(d==b) continue;
      20. if(d==c) continue;
      21. for(e=1;e<=MAX;e++){
      22. if(e==a) continue;
      23. if(e==b) continue;
      24. if(e==c) continue;
      25. if(e==d) continue;
      26. for(f=1;f<=MAX;f++){
      27. if(f==a) continue;
      28. if(f==b) continue;
      29. if(f==c) continue;
      30. if(f==d) continue;
      31. if(f==e) continue;
      32. for(g=1;g<=MAX;g++){
      33. if(g==a) continue;
      34. if(g==b) continue;
      35. if(g==c) continue;
      36. if(g==d) continue;
      37. if(g==e) continue;
      38. if(g==f) continue;
      39. for(h=1;h<=MAX;h++){
      40. if(h==a) continue;
      41. if(h==b) continue;
      42. if(h==c) continue;
      43. if(h==d) continue;
      44. if(h==e) continue;
      45. if(h==f) continue;
      46. if(h==g) continue;
      47. for(i=1;i<=MAX;i++){
      48. if(i==a) continue;
      49. if(i==b) continue;
      50. if(i==c) continue;
      51. if(i==d) continue;
      52. if(i==e) continue;
      53. if(i==f) continue;
      54. if(i==g) continue;
      55. if(i==h) continue;
      56. for(j=1;j<=MAX;j++){
      57. if(j==a) continue;
      58. if(j==b) continue;
      59. if(j==c) continue;
      60. if(j==d) continue;
      61. if(j==e) continue;
      62. if(j==f) continue;
      63. if(j==g) continue;
      64. if(j==h) continue;
      65. if(j==i) continue;
      66. differences = new ArrayList<>();
      67. differences.add(abs(a-c));
      68. differences.add(abs(a-d));
      69. differences.add(abs(a-e));
      70. differences.add(abs(i-c));
      71. differences.add(abs(i-d));
      72. differences.add(abs(i-e));
      73. differences.add(abs(b-f));
      74. differences.add(abs(b-g));
      75. differences.add(abs(b-h));
      76. differences.add(abs(j-f));
      77. differences.add(abs(j-g));
      78. differences.add(abs(j-h));
      79. differences.add(abs(a-b));
      80. differences.add(abs(i-j));
      81. if(findDuplicates(differences)){
      82. System.out.println("Möglichkeit" + ++counter);
      83. System.out.println(" a= " + a + " b= " + b + " c= " + c + " d= " + d + " e= " + e + " f= " + f + " g= " + g + " h= " + h + " i= " + i + " j= " + j);
      84. }
      85. }
      86. }
      87. }
      88. }
      89. }
      90. }
      91. }
      92. }
      93. }
      94. }
      95. }
      96. public static boolean findDuplicates(List<Integer> listContainingDuplicates)
      97. {
      98. final Set<Integer> set1 = new HashSet<>();
      99. for (Integer yourInt : listContainingDuplicates)
      100. {
      101. if (!set1.add(yourInt))
      102. {
      103. return false;
      104. }
      105. }
      106. return true;
      107. }
      108. }
      Alles anzeigen
      Mit MAX=15 läuft das Programm ewig und findet keine Lösung, mit MAX=16 findet es nach wenigen Sekunden schon etwas:


      1---2
      34
      16131415
      9---5

      In dieser Tabelle ist das Netz vereinfacht dargestellt - sich (auch über Eck) berührende Zahlen sind benachbarte Blautöne, und die 1-2 sowie 9-5 berühren sich ebenfalls. Zahlen in Zeile 2 sind paarweise NICHT benachbart.
      \binom{2^{\binom{2^2}{2}}}{2} = 2016
    • Ich habe mit Excel experimentiert nachdem ich die Nachbarschaften in einen Graphen übertragen habe.

      Es gibt 10 zu färbende Bereiche und 14 Differenzen.

      Damit ist bereits klar, dass eine optimale Lösung - wenn es sie denn gäbe - die Differenzen 1 bis 14 und die Werte 1 bis 15 aufwiese wobei die Farbbereiche mit der Farbe 1 und der Farbe 15 nebeneinander lägen.

      Das klappt jedoch nicht - warum, kann ich allerdings nicht beweisen.

      Hier eine mögliche Lösung für die max Farbe 16:

      2016-19 ok.PNG

      Gelb sind die Farbwerte der zu färbenden Bereiche, grau die Differenzen zwischen den Farben.

      8 der Excel-Felder sind Eingabefelder (die etwas dunkleren), die restlichen 16 Felder werden berechnet. Mit der Zählenwenn() Funktion habe ich dann geprüft und angezeigt ob Zahlen verbotenerweise doppelt in den grauen bzw. gelben Feldern vorkommen.
      So konnte ich recht schnell experimentieren.

      Man sieht, dass es rechts und links Bereiche und Pfade gibt, die bestimmte Muster bilden - insbesondere bietet es sich an, dass auf einer Seite die Summen (Im Beispiel rechts 8+3=7+4=6+5) bzw. auf der anderen Seite die Differenzen (Im Beispiel links 13-10=13-11=15-12) auf den Pfaden jeweils zueinander passen. Damit sind gar nicht so viele Möglichkeiten durchzuprobieren bis man eine Lösung findet.


      Damit kommen wir zu der Zusatzfrage: Wieviele verschiedene gültige Färbungen gibt es?
    • Es ist relativ einfach zu zeigen, dass I=15 nicht funktioniert:

      In dem symmetrischen Graphen sind die wichtigsten Knoten die, die in deinem Beispiel durch 4, 13, 1 und 2 besetzt werden.
      Die Idee ist zu zeigen, dass egal welche Parität die Zahlen dieser Knoten haben, die Gesamtsumme aller Differenzen immer gerade sein muss.
      Das kommt aber nicht mit 1+2+3+...+14 = 105 auf.
    • frank.buchholz schrieb:

      Damit kommen wir zu der Zusatzfrage: Wieviele verschiedene gültige Färbungen gibt es?
      Nun ja, ich hab ein Programm geschrieben, dass mir 1472 Färbungen ausgibt.

      Das Programm färbt den folgenden Graphen ein:


      a---------f
      /|\/|\
      bcegij
      \|/\|/
      d---------h


      Das Programm setzt aber a = 1 und b = 16, und sorgt dafür dass c < e und g < i < j ist.

      Um alle gültigen Färbungen zu bekommen, muss man noch mit folgendem multiplizieren.

      2 - da es zu jeder Färbung eine inverse Färbung gibt, bei der jede Farbe x durch 17-x ersetzt wird.
      4 - da die 1 (bzw. 16) an a, f, d oder h sein kann.
      3! * 3! - da die Felder b, c, e und g, i, j jeweils auf 3! verschiedene Arten eingefärbt werden können.

      Wenn ich mich nicht vertan hab, sollte es also

      1472 * 2 * 4 * 3! * 3! = 423936

      verschiedene Färbungen geben.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von Muetze ()

    • Ich habe 237 weitere Färbungen gefunden, wenn man mit Muetzes Bezeichnungen a = 1 und f = 16 (b < c < e und g < i < j) setzt.
      Etwa
      b, c, e = 12, 13,14
      g, i, j = 2, 7, 9
      d = 8 und h = 10

      Da sich weiterhin 4 mögliche Positionen für die "1" finden lassen und 3!*3! Permutationen für b, c, e, g, i, j sollte es weitere
      237 * 4 * 3! * 3! = 34128
      verschiedene Färbungen geben (inverse Färbungen sind hier schon dabei).


      Falls es jemanden interessiert: Programmiert in python3, etwa 25 Zeilen Code, Laufzeit weniger als eine halbe Sekunde.
    • T A H hat natürlich recht, ich hab die Färbungen mit a = 1 und f = 16 vergessen.

      Hab darum mein Programm dafür angepasst.

      Mit b < c < e und g < i < j kommt mein Programm auf 756 weiteren Färbungen,
      und damit auf

      756 * 4 * 3! * 3! = 108864

      verschiedene zusätzliche Färbungen.

      Übrigens sind meine Programme in C++, die Laufzeit ist jeweils deutlich unter 50ms.
      Sind aber jeweils ca. 260 Zeilen, hab das ziemlich aufwändig hingeschrieben.

      Nur hat offenbar einer von uns einen Fehler im Programm, kann jemand eine der Zahlen
      bestätigen?

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von Muetze ()

    • T A H schrieb:

      Ich denke, das sollten jetzt alle sein. (Das hatte ich zwar vorher auch schon gedacht, aber noch nicht geschrieben.)
      Ja, das sollten alle sein, da die maximale Differenz 15 irgendwo vorkommen muss.

      Insgesamt sind es damit:

      423936 + 108864 = 532800

      verschiedene Färbungen unter denen Mondrian auswählen kann.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von Muetze ()