| |
| Autor |
 Finden eines Insulaners mit abweichendem Gewicht |
|
Yggdrasil
Senior 
Dabei seit: 01.07.2004
Mitteilungen: 873
Wohnort: Berlin
 |  Beitrag No.80, eingetragen 2023-10-26
|
Hallo, wenn ich nichts überlesen habe fehlt als Variante noch eine Berechnung eines Wägeplans per Induktion :-). (Kann sein, dass der in AnnaKaths C#-Programm versteckt ist. Dort habe ich die Auswahl des Vertreters der Äquivalenzeklasse nicht verstanden.)
Hier wäre meine Lösung zur Berechnung eines Plans für \(n+1\) Wägungen:
Induktionsanfang, \(n=2, m=3\). Es werden drei Leute/Kugeln, \(a,b,c\) gewogen, wobei die Position bezüglich der []-Klammer angibt ob man links, nicht oder rechts auf der Waage steht. Das die Waage in Wägung \(i\) nach links/rechts ausschlägt wird mit 1/2 kodiert und Gleichheit mit 0. Das Resultat aller Wägungen wird als Ternärzahl mit \(n\) Ziffern codiert.
Der Wägeplan \(P_2\)
\(
\begin{align*}
0: && \{a\} && [\;\{b\}\;] && \{c\}\\
1: && \{c\} && [\;\{a\}\;] && \{b\}
\end{align*}
\)
besitzt die Eigenschaft, dass '00', '11' und '22' nicht vorkommen (*). In Tabellenform kann man die Varianten so auflisten.
\(
\begin{align*} && S && L\\
a && 10 && 20 \\
b && 02 && 01 \\
c && 21 && 12
\end{align*}
\)
Induktionsschritt \(n \rightarrow n+1 , m \rightarrow 3\cdot m+3 \)
Die erste Wägung von Plan \(P_n\) gibt eine Partitionierung der Kugeln in drei Teilmengen \(A, B, C\) Elementen vor.
Seien \(f_i\) drei injektive Abbildungen, deren Bilder disjunkt sind und
\(A'_0 := f_0(A), …, C'_2 := f_2(C)\), \(\qquad A' := \bigcup A'_i \), etc.
Drei weitere Kugeln seien mit \(x_i\) bezeichnet.
Wir übernehmen den Wägeplan \(P_n\) für die ersten \(n\) Zeilen und ersetzten alle Kugeln \(x\) durch \(\bigcup \{f_i(x)\}\). Zusätzlich ergänzen wir um die \(x_i\) und eine neue Zeile.
\(
\begin{align*}
0: && A'_0A'_1A'_2 && x_0 && [\;B'_0B'_1B'_2 && x_1\;] && C'_0C'_1C'_2 && x_2\\
1: && … && x_0 && [\;… && x_1\;] && … && x_2\\
…\\
n: && A'_0B'_0C'_0 && x_2 && [\;A'_1B'_1C'_1 && x_0\;] && A'_2B'_2C'_2 && x_1
\end{align*}
\)
Liefern alle Wägungen der ersten \(n\) Zeilen das gleiche Resultat (\(0…0\), \(1…1\),\(2…2\)), so können wir nach Induktionsvoraussetzung (*) ausschließen, dass die abweichende Kugel in \(A'\),\(B'\) oder \(C'\) enthalten ist.
Erste und letzte Zeile ergeben dann, anlog zu \(P_2\), welches \(x_i\) abweicht (und in welche Richtung).
Sind die ersten \(n\) Zeilen nicht gleich, kann andererseits die abweichende Kugel kein \(x_i\) sein. Die ersten \(n\) Wägungen geben vor welches Kugel-Tripel abweicht und in welche Richtung. Die letzte Zeile kann dann den Abweichler identifizieren, weil die drei Kugeln auf links, rechts oder gar nicht auf der Waage liegen.
Es bleibt noch zu zeigen, dass die Eigenschaft (*) erhalten bleibt, da ohne sie den nächste Induktionsschritt nicht möglich wäre:
Ist die gesuchte Kugel \(!= {x_i}\) so können die ersten beiden Wägungen nie das gleiche Resultat liefern, d.h. \(0…0\), \(1…1\) und \(2,…,2\) sind ausgeschlossen.
Andererseits liefern erste und letzte Zeile den Nachweis, dass auch bei Abweichung in \(x_i\) niemals die Wägungen niemals \(0…0\), \(1…1\) und \(2,…,2\) ergeben.
|
 Profil
|
haribo
Senior 
Dabei seit: 25.10.2012
Mitteilungen: 4645
 | Beitrag No.81, eingetragen 2023-10-26
|
von induktion verstehe ich nichts
aber entgegen AK´s vorsichtig geäusserten vermutung das n=3 die einzige supersymmetrie ergibt, hab ich zeit auf n=5 verschwendet, und meine es geht
https://www.matheplanet.de/matheplanet/nuke/html/uploads/c/35059_insulaner120-1.jpg
24 rolierbare fünfersets die sich nie stören also jeweils fünf plätze teilen ergeben 120 personen, die vertauschungen bleiben jeweils gleich --> supersymetrie
die beispielhaft dargestellte 20022 teilt sich ihre plätze reihum mit
20022
00222
02220
22200
22002
wäre selbst also bei R00RR schwer bzw bei L00LL leicht...
für n=5 gibt es dann schon etliche startsets, man kann oft zwei fünfersets S vs L vertauschen (beispielsweise hier 20022 und die vier anderen des sets gegen ihre brüder 10011 und gleichzeitig den blauen 11010 + set gegen brüder 22020, dabei verändern sich die anzahl der 1en und 2en in summe nicht)
und dann geht supersymetrie wohl bei allen prim=n>2 ???
|
Profil
|
AnnaKath
Senior
Dabei seit: 18.12.2006
Mitteilungen: 3859
Wohnort: hier und dort (s. Beruf)
 | Beitrag No.82, eingetragen 2023-10-26
|
\(\begingroup\)\(\newcommand{\C}{\mathbb{C}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\i}{\mathrm{i}}
\newcommand{\d}{\mathrm{d}}
\newcommand{F}{F_{\mu\nu} dx^{\mu} \wedge dx^{\nu} = A_{nu} dx^{\mu} \wedge dx^{\nu} + A_{\nu} A^{\mu} + A_{\mu} A^{\nu} - 2A_{\sigma}A^{\sigma}}\)
Huhu Peter,
nur ganz kurz: Ja, die Supersymmetrie geht in allen diesen Fällen.
Ich habe sogar bereits einen Algorithmus angegeben, diese zu finden - und war nur zu doof zu erkennen, dass er für alle $n$ funktioniert, für die $n | k_n$ gilt. Man muss nur die Codes "geschickt" wählen, um daraus die Zyklen der Permutation zu konstruieren.
Konkret ist bei jedem Code zu entscheiden, ob man diesen oder den geflippten Code für die Konstruktion eines Zyklus verwendet. Dies kann man einfach per Tiefensuche probieren oder auch die Codes so wählen, dass die Ziffern "1" und "2" in der Ternärdarstellung gleich häufig vorkommen.
Dass dies geht liegt einfach daran, dass wir ein "vollständiges Set" von Ternärzahlen haben (also die Ziffern gleich häufig sind) und je Äquivalenzklasse einen Code auswählen können.
Eine Möglichkeit ist es etwa, zu zählen, wie oft man bereits "1" und "2" gewählt hat, und dann bei einem Kandidaten genau dann zum geflippten Code überzugehen, wenn dieser mehr von Ziffer $d$ aufweist und $d$ bisher "unterrepräsentiert" war.
lg, AK\(\endgroup\)
|
Profil
|
haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 4645
| Beitrag No.83, eingetragen 2023-10-27
|
ja gibt bestimmt viele möglichkeiten gleiche verteilung von L/O/R zu finden,
eine tiefensuche mag ja schnell lang werden,
meine auswahlvariante war ungefähr so:
- liste alle sortierten fünfstelligen ternäre sortiert nach grösse auf, und dahinter alle vier rollierten nebst aller dazu gehörigen geschwister
- durchsuche diese liste zeilenweise nach neuen ternären, davon gibt es 48
- davon wähle jeden zweiten
das führte zur schon ziemlich guten L/O/R gesamtsumme von 35/40/45
- wähle händisch zwei nicht gewählte tauschpartner die in summe 5L mehr und 5R weniger haben
letztlich definiert sich die 120er supersymmetrische wipperei also lediglich über die dabei ausgewählten 24 ternäre:
1 4 7 16 19 22
31 34 40 43 195 201
204 210 219 222 225 228
229 231 232 234 237 240
https://www.matheplanet.de/matheplanet/nuke/html/uploads/c/35059_insulaner-6fach.jpg
ich meine es hätte doch was wenn man mit meinetwegen n=6 messungen aus diesem feld bestimmen kann welche zelle ausgefallen ist ?
ok die messverdrahtung muss man irgendwie geschickt in irgendeinen chip pressen... da hilft die supersymmetrie erheblich, keine ahnung
(aus der serie: make millions)
|
Profil
|
AnnaKath
Senior
Dabei seit: 18.12.2006
Mitteilungen: 3859
Wohnort: hier und dort (s. Beruf)
| Beitrag No.84, eingetragen 2023-10-27
|
\(\begingroup\)\(\newcommand{\C}{\mathbb{C}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\i}{\mathrm{i}}
\newcommand{\d}{\mathrm{d}}
\newcommand{F}{F_{\mu\nu} dx^{\mu} \wedge dx^{\nu} = A_{nu} dx^{\mu} \wedge dx^{\nu} + A_{\nu} A^{\mu} + A_{\mu} A^{\nu} - 2A_{\sigma}A^{\sigma}}\)
Huhu Peter,
ja, das wäre tatsächlich eine nette Anwendung :)
Hier als Beispiel zwei supersymmetrische Wiegepläne für $n=5,7$.
Angegeben ist nur die Permutation $\sigma$ in Zyklus-Schreibweise. Nummerierung von Plätzen/Insulanern usf. beginnt bei $0$.
\showon
\sourceon output n=5
Regulärer Wiegeplan für 5 Wägungen und 120 Kugeln:
( 086 110 081 080 063 )
( 045 059 044 061 001 )
( 089 108 119 079 053 )
( 092 111 112 050 028 )
( 054 058 067 013 088 )
( 105 098 115 035 029 )
( 065 078 083 072 114 )
( 055 060 113 070 037 )
( 099 107 066 040 039 )
( 109 101 043 018 068 )
( 100 116 052 036 002 )
( 041 042 016 057 097 )
( 090 117 034 085 030 )
( 077 075 026 103 011 )
( 051 069 033 027 091 )
( 096 084 021 022 023 )
( 049 094 047 087 024 )
( 076 118 046 005 019 )
( 064 102 014 048 007 )
( 073 106 000 095 010 )
( 062 082 020 012 038 )
( 071 031 074 015 017 )
( 093 009 056 008 025 )
( 104 003 032 006 004 )
\sourceoff
\sourceon output n=7
Regulärer Wiegeplan für 7 Wägungen und 1092 Kugeln:
( 1010 885 923 1074 970 1063 670 )
( 403 472 715 391 639 414 253 )
( 906 972 1011 755 878 686 625 )
( 440 506 423 484 385 782 050 )
( 837 743 1018 734 945 242 378 )
( 600 539 604 370 492 298 222 )
( 998 994 902 961 719 799 702 )
( 781 1055 801 922 691 1080 094 )
( 678 375 381 494 935 748 741 )
( 666 483 454 626 858 1040 011 )
( 565 511 681 578 776 037 984 )
( 898 814 1032 819 498 220 333 )
( 592 453 627 712 335 549 931 )
( 872 939 772 889 145 857 182 )
( 726 418 461 387 132 791 865 )
( 514 683 463 470 274 993 203 )
( 752 943 967 996 012 016 725 )
( 583 480 543 714 350 252 004 )
( 875 810 863 449 773 913 478 )
( 1059 946 928 611 1044 955 000 )
( 708 550 512 836 526 822 1057 )
( 724 616 718 754 613 744 121 )
( 486 584 407 1085 700 030 828 )
( 1087 733 1089 596 982 190 172 )
( 694 521 618 899 795 392 900 )
( 368 593 559 1064 746 612 234 )
( 990 952 867 651 609 528 291 )
( 1058 940 779 438 527 250 629 )
( 764 1019 1071 417 421 112 005 )
( 807 778 763 452 345 879 614 )
( 523 605 534 979 071 569 320 )
( 909 916 767 567 276 464 707 )
( 815 974 1086 482 010 634 334 )
( 1033 1076 966 379 354 263 408 )
( 462 553 395 1083 209 283 062 )
( 959 941 964 009 932 808 658 )
( 538 524 662 249 503 566 357 )
( 821 786 768 341 1065 608 610 )
( 766 997 897 191 864 640 020 )
( 522 727 689 104 643 029 1006 )
( 735 833 951 096 1014 101 044 )
( 690 422 531 085 1045 425 985 )
( 457 647 532 256 912 585 041 )
( 817 969 738 218 582 465 268 )
( 803 891 1000 296 579 324 664 )
( 513 401 413 095 831 336 293 )
( 975 838 1029 063 317 918 541 )
( 619 638 502 148 061 447 139 )
( 839 1088 1004 289 022 372 400 )
( 1036 983 914 224 052 548 239 )
( 496 574 477 197 179 130 777 )
( 963 978 1024 053 237 217 262 )
( 516 439 907 479 646 1067 917 )
( 680 499 749 706 489 1039 088 )
( 731 886 654 871 840 347 617 )
( 398 655 965 537 444 158 297 )
( 818 861 406 954 488 992 459 )
( 1047 877 677 796 571 824 175 )
( 544 485 924 374 1050 753 116 )
( 601 649 1052 570 832 275 1003 )
( 597 371 771 558 827 221 236 )
( 1079 948 382 926 045 848 560 )
( 443 390 1072 501 279 562 075 )
( 973 949 529 1020 342 366 497 )
( 1048 800 442 760 359 427 057 )
( 835 911 679 936 331 245 704 )
( 705 455 1030 633 282 099 035 )
( 792 851 530 641 802 798 173 )
( 573 446 894 888 644 306 1046 )
( 475 659 953 950 369 244 024 )
( 816 860 431 428 126 1060 687 )
( 937 905 673 451 146 977 188 )
( 622 657 1082 809 192 758 152 )
( 420 505 830 995 105 269 999 )
( 373 410 845 1012 144 193 079 )
( 555 682 976 141 399 411 323 )
( 790 884 468 199 881 535 073 )
( 473 661 805 266 577 169 811 )
( 1049 756 471 322 783 019 067 )
( 599 696 880 013 921 456 862 )
( 545 383 761 344 920 620 330 )
( 675 448 841 280 915 1073 294 )
( 364 386 890 077 854 288 740 )
( 591 540 849 165 1070 261 014 )
( 557 434 980 084 329 684 853 )
( 469 429 1069 149 031 568 187 )
( 825 896 685 215 102 590 278 )
( 1061 1002 624 214 198 166 466 )
( 988 751 716 235 059 211 039 )
( 586 713 006 645 432 238 770 )
( 785 1008 060 820 1077 164 128 )
( 402 435 343 656 958 458 866 )
( 806 874 002 1084 388 823 143 )
( 561 693 292 508 933 1091 170 )
( 588 594 159 389 929 319 868 )
( 589 710 260 667 789 180 135 )
( 1081 1001 137 895 194 1090 576 )
( 635 367 339 636 118 397 069 )
( 736 747 264 1042 358 698 313 )
( 804 1028 092 947 312 307 672 )
( 487 648 226 556 265 219 089 )
( 1038 1007 167 606 813 493 248 )
( 1043 981 058 404 826 201 674 )
( 377 711 205 942 380 106 309 )
( 1051 774 247 653 437 183 246 )
( 784 903 352 720 349 925 637 )
( 956 1075 023 394 258 788 055 )
( 695 652 361 762 178 1021 310 )
( 542 607 114 1053 326 136 1037 )
( 628 500 257 1068 321 066 048 )
( 564 405 150 119 518 730 210 )
( 859 729 046 032 745 156 412 )
( 602 460 355 003 598 051 086 )
( 991 829 111 251 717 852 517 )
( 775 759 340 290 376 728 200 )
( 430 631 036 027 892 353 847 )
( 419 703 080 233 794 184 300 )
( 846 1026 277 008 337 742 721 )
( 450 723 284 185 056 630 327 )
( 989 844 299 072 154 563 229 )
( 1041 732 157 109 241 043 507 )
( 467 621 223 362 318 040 281 )
( 769 509 944 433 968 436 090 )
( 962 575 797 504 1013 271 113 )
( 930 441 1031 688 155 750 140 )
( 692 904 669 1005 097 986 174 )
( 409 834 697 765 186 127 189 )
( 623 876 365 301 491 887 204 )
( 476 1015 663 161 660 117 195 )
( 850 580 901 273 393 919 351 )
( 957 581 1056 021 519 356 122 )
( 737 603 883 202 230 780 142 )
( 533 793 668 129 091 842 038 )
( 490 893 587 286 216 196 163 )
( 595 787 287 384 873 093 207 )
( 546 870 348 481 162 445 131 )
( 1017 520 338 843 068 415 255 )
( 1034 552 026 1016 015 103 007 )
( 1009 525 225 495 1027 025 110 )
( 938 709 346 671 325 960 302 )
( 426 1022 259 1025 033 856 153 )
( 615 934 034 869 070 285 134 )
( 424 987 138 028 510 360 120 )
( 701 910 083 363 1062 314 171 )
( 642 1035 228 047 332 722 108 )
( 396 1066 049 147 074 927 087 )
( 665 812 017 311 213 076 176 )
( 650 054 676 100 699 303 001 )
( 739 328 971 065 547 098 018 )
( 572 168 554 315 304 757 123 )
( 1023 270 1054 272 177 078 267 )
( 416 064 908 243 551 208 042 )
( 536 232 882 160 081 181 295 )
( 474 151 305 515 206 125 115 )
( 1078 240 082 632 254 107 212 )
( 855 308 124 316 227 231 133 )
\sourceoff
\showoff
Ausprobiert habe ich den Code nur für $n=5,7,11$. Auch für grössere $n$ ist es zwar anschaulich ziemlich "wahrscheinlich", dass es Lösungen gibt, aber man muss ein wenig Glück (oder eine gute Heuristik) haben, die richtigen Repräsentanten auszuwählen (oder eben vollständig suchen).
Händische Auswahl funktioniert bei den bisherigen Beispielen sicher noch, aber für ernste Anwendung (und grössere $n$) wohl schliesslich nicht mehr möglich.
Deine Auswahl ist sicher ziemlich clever, meine Heuristik vermutlich auch nicht völlig absurd.
Aber wir brauchen natürlich trotzdem einen Beweis, dass es für jedes prime $n$ einen solchen Plan gibt!
lg, AK\(\endgroup\)
|
Profil
|
haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 4645
| Beitrag No.85, eingetragen 2023-10-27
|
bei der supersymmetrie sind die bereiche gleichberechtigt, es ist also egal welche zwei gegeneinander ausgewogen werden...
dann scheinen mir als bezeichnung xyz geeigneter als 012?
https://www.matheplanet.de/matheplanet/nuke/html/uploads/c/35059_insulaner120-2.JPG
[Die Antwort wurde nach Beitrag No.83 begonnen.]
|
Profil
|
haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 4645
| Beitrag No.86, eingetragen 2023-10-27
|
für diese prim-einschränkung selber fehlt mir sowiso noch der mir verständliche beweis,
dass die geraden n´s nicht gehen ist evtl. noch einleuchtend,
aber warum ist prim erforderlich?
also als erstes wohl für n=9 sehe ich es in der rechnung das die aufteilung (3^9-3)/2*9 nicht ganzzahlig wird, aber wieso oder wie kann man daraus n = prim´s schlussfolgern?
|
Profil
|
AnnaKath
Senior
Dabei seit: 18.12.2006
Mitteilungen: 3859
Wohnort: hier und dort (s. Beruf)
| Beitrag No.87, eingetragen 2023-10-27
|
\(\begingroup\)\(\newcommand{\C}{\mathbb{C}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\i}{\mathrm{i}}
\newcommand{\d}{\mathrm{d}}
\newcommand{F}{F_{\mu\nu} dx^{\mu} \wedge dx^{\nu} = A_{nu} dx^{\mu} \wedge dx^{\nu} + A_{\nu} A^{\mu} + A_{\mu} A^{\nu} - 2A_{\sigma}A^{\sigma}}\)
Huhu Peter,
\quoteon(2023-10-27 12:14 - haribo in Beitrag No. 86)
dass die geraden n´s nicht gehen ist evtl. noch einleuchtend,
aber warum ist prim erforderlich?
\quoteoff
Ich bin leider nicht gerade eine grosse Zahlentheoretikerin...
Aus der Forderung $n | k_n$ ergibt sich jedenfalls $3^{n-1} \equiv 1 (n)$. Das ist nach dem (kleinen) Fermatschen Satz zumindest für prime $n$ erfüllt.
Ob die Forderung auch notwendig ist, habe ich mir (noch?) nicht abschliessend überlegt.
lg, AK\(\endgroup\)
|
Profil
|
haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 4645
| Beitrag No.88, eingetragen 2023-10-28
|
kleiner fermat steht schwarz und schweiget
das letzte bild ein möbius? rund und schön
die geflippten auf der anderen seite
können wir nicht sehn...
ungefähr nach m. claudius
|
Profil
|
haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 4645
| Beitrag No.89, eingetragen 2023-10-30
|
immerhin n als primzahl führt dazu dass immer alle rollierten zahlen ohne mehrfache auftreten, die es bei n=9 und drei dreiergruppen sofort gibt,
xyz|xyz|xyz
zxyzxyzxy
yzxyzxyzx
xyzxyzxyz entspricht wieder dem ersten
mehrere gleiche gruppen sind bei n=prim nun mal nicht möglich
evtl erklärt das ausreichend die n=prim anforderung?
|
Profil
|
Yggdrasil
Senior
Dabei seit: 01.07.2004
Mitteilungen: 873
Wohnort: Berlin
| Beitrag No.90, eingetragen 2023-11-04
|
\quoteon(2023-10-13 16:28 - Wario in Beitrag No. 69)
\quoteon(2023-10-13 16:21 - haribo in Beitrag No. 68)
dann gib mal n=363 ein…
\quoteoff
Die Verallgemeinerung des Problems auf $n\in\mathbb{N}$ ist interessant.
Von zentraler Bedeutung ist hier m.E. wie man die Lösung verständlich, sinnvoll, nachvollziehbar und übersichtlich angibt.
Damit meine ich nicht nur die Anzahl der Wägungen, sondern auch den Gesamtablauf und dessen Möglichkeiten.
Ein Baumdiagramm ist grundsätzlich naheliegend, ist aber bei größeren $n$ nicht mehr umsetzbar.
Daher hatte ich mich gefragt, ob man evtl. eine oder mehrere (geschlossene) Formeln dazu ermitteln kann, die es erlauben de Pfade zu beschreiben.
Ideen?
\quoteoff
Ich habe die Rekursion in meinen Formeln für den Wägeplan auflösen können und kann damit für jede Kugel (einzeln) bestimmen wo sie auf jeder Wägung zu liegen hat.
Ich kann also nicht den gesamten Wägeplan für n=363 ausgeben, aber für jede Kugel 0,…,(3^363-3)/2 sagen wo sie zu liegen hat ;)
Außerdem sind das dann, hoffe ich, die gewünschten, ausreichend einfache Formeln zur Beschreibung der Mengen.
Das PDF-Dokument, das am Ende herauskam ist allerdings 9 Seiten lang und ich frage mich wie ich es hier am besten poste. Gibt es neben Bildern auf dem MP auch die Option PDFs hochzuladen?
Den reinen Tex-Code in einen Beitrag zu packen erscheint mir bei der Länge etwas ungünstig.
Das zugehörige Python-Programm ist
\showon
\sourceon Python3
#!/usr/bin/python3
#
import sys
import argparse
from itertools import zip_longest
__M = [ (3**n - 3)//2 for n in range(5)]
# M(n) ist maximale Anzahl von unterscheidbaren Kugeln.
# Weiterhin gilt 3**k = M(k+1) - M(k), d.h.
# man braucht die Potenzen von 3 nicht auch noch cachen.
def M(n):
assert(n>=0)
global __M
try:
return __M[n]
except IndexError:
# Rekursiv m(n+1) = 3 * m(n) + 3 berechnen.
n2 = len(__M)-1
while n2 <= n:
__M.append(3 * __M[n2] + 3)
n2 += 1
return __M[n]
# Ternärstring von x und und genau k Zeichen (0 wird "0^k", etc).
def tri_str(x, k):
l = []
while(x):
# l.append(str(x%3)) # Hm, für große Zahlen ist modulo float statt int
l.append(str(int(x%3)))
x = x//3
if len(l) > k:
raise Exception("Input number too big")
# Add zeros for short number strings
l += ["0"] * k
# Restrict on last k positions
l = l[:k]
l.reverse()
return "".join(l)
# Konstruktion von T(x)
def T(n, x):
# d = 3**(n-2)
d = M(n-1) - M(n-2)
if x < d:
return "01" + tri_str(x, n-2)
elif x < 2*d:
return "21" + tri_str(x-d, n-2)
elif x < 3*d:
return "10" + tri_str(x-2*d, n-2)
else:
flip = M(n) - x - 1
l = 2
Ml = M(l) # 3
while Ml <= flip:
l += 1
Ml = M(l)
# M(l) > flip >= M(l-1)
z = Ml-1-flip
return "2"*(n-l) + "0" + tri_str(z,l-1)
def RotJ(j):
# modulo always positive in Python
return (j-1)%3
def eval_all_entries_of_wage(n, i):
return gen_wage_generator(n, i, True)
# Generator functions returning (l,m,r) tuples
def gen_wage_generator(n, i, as_generator=True):
if i == 0:
lw = [ eval_wage0(n, j) for j in range(3) ]
elif i == 1:
lw = [ eval_wage1(n, j) for j in range(3) ]
else:
lw = [ eval_wagei(n, i, j) for j in range(3) ]
if as_generator:
return zip_longest(*lw) # Generator of Tripels
else:
return lw # List with tree separate generator
# Generator functions returning l,m or r value
def eval_wage0(n, j):
m = M(n) # (3^n - 3) / 2
d = 2 * M(n-2) + 3 # 3**(n-2)
#assert( d == 3**(n-2))
# 1.-3. Zeile von T(x)
s1 = d*j
e1 = s1 + d
for x in range(s1,e1): yield x
# Restliche Zeilen (2^d0-Präxfixe/Dreiecksbereich)
for l in range(n-2,0,-1):
# Eval range for z of Form 2^{n-l-1}0z_0…z_{l-1}, z=(z_i)
# with fixed top numeral z_0=j
d4 = M(l) - M(l-1) # 3**(l-1)
zS = d4 * j
zE = zS + d4
# Use x = M(n) - M(l+1) + z
for x in range( M(n) - M(l+1) + zS, M(n) - M(l+1) + zE):
yield x
# Generator functions returning l,m or r value
def eval_wage1(n, j):
m = M(n) # (3^n - 3) / 2
d = M(n-1) - M(n-2) #2 * M(n-2) + 3 # 3**(n-2)
#assert( d == 3**(n-2))
# 1.-3. Zeile von T(x)
# Rotation von Waage 0
s1 = d*RotJ(j)
e1 = s1 + d
for x in range(s1,e1): yield x
# Restliche Zeilen (2^d0-Präxfixe/Dreiecksbereich)
# Gleich zu Waage 0
for l in range(n-2,0,-1):
# Eval range for z of Form 2^{n-l-1}0z_0…z_{l-1}, z=(z_i)
# with fixed top numeral z_0=j
d4 = M(l) - M(l-1) # 3**(l-1)
zS = d4 * j
zE = zS + d4
# Use x = M(n) - M(l+1) + z
for x in range( M(n) - M(l+1) + zS, M(n) - M(l+1) + zE):
yield x
# Generator functions returning l,m or r value
def eval_wagei(n, i, j):
m = M(n) # (3^n - 3) / 2
d = 2 * M(n-2) + 3 # = 3**(n-2) = 3**k
#assert( d == 3**(n-2))
#assert( n>i and i>2 )
k = n-2
e = n-1-i
# 1.-3. Zeile von T(x)
# [Prefix]*^(i-2) j *^{n-(i+1)}
# [Prefix]*^(k-1-e) j *^{e}
# ^vorne
# ^j
# ^hinten
# <- k Stellen --------->
# <-- n Stellen ---------------->
#
# Da alle drei Prefixe durchlaufen werden gibt es 3^(i+1) verschiedene
# Varianten für die höherwertigen Ziffern.
if i == n-1: # d.h. keine Ziffern hinter j.
vorneBegin = j
vorneEnd = 3*d + vorneBegin
for x in range(vorneBegin, vorneEnd, 3): yield x
else:
j_shift = j * (M(e+1) - M(e)) # j * 3**(n-(i+1))
# vorneStep = 3**(n-(i+1)+1) # Entspricht +1 an der Ziffer vor dem fixen 'j'
vorneStep = M(e+2) - M(e+1) # 3**(e+1) # Entspricht +1 an der Ziffer vor dem fixen 'j'
vorneBegin = j_shift + 0
vorneEnd = 3*d + j_shift
zHintenEnd = M(e+1) - M(e) # 3**(e)
for vorne in range(vorneBegin, vorneEnd, vorneStep):
hintenStart = vorne + 0
hintenEnd = hintenStart + zHintenEnd
for x in range(hintenStart, hintenEnd): yield x
# Restliche Zeilen (4. Fall)
# 1 0:
d = M(l+1)-M(l)
else:
d = 1
# assert( d == 3**(l))
zStart = RotJ(j) * d
# zEnd = zStart + d
# Use x = M(n) - M(l+2) + z
xStart = M(n) - M(l+2) + zStart
xEnd = xStart + d
for x in range(xStart, xEnd): yield x
# c)
for l in range(e-1,-1,-1):
if l > 0:
d = M(l+1)-M(l)
else:
d = 1
# assert( d == 3**(l))
# Top numeral in z is fixed
zStart = j * d
# zEnd = zStart + d
# Use x = M(n) - M(l+2) + z
xStart = M(n) - M(l+2) + zStart
xEnd = xStart + d
for x in range(xStart, xEnd): yield x
def print_labels(n):
print(f"Erzeuge Label für n={n}:")
m = M(n)
for x in range(m):
print(f"{x:3}, {T(n,x)}")
def print_wage(n,i):
def transpose(l,j):
for x in l: yield f"{x[j]:3}"
print(f"Waage {i}:")
if True:
# Per Generator, nie komplett im Speicher
# und transponiert mit Spalten 'L M R'.
gen = eval_all_entries_of_wage(n, i)
for (left,mid,right) in gen:
print(f"{left:3} {mid:3} {right:3}")
elif False:
# Zurück-Transponiere Waagen-Output in lange Zeilen
# Transpose output from kx3 to 3xk, k = m(n)/3
full_list = list(gen)
print(" Left: ", end='')
print(",".join(transpose(full_list, 0)))
print(" Middle: ", end='')
print(",".join(transpose(full_list, 1)))
print(" Right: ", end='')
print(",".join(transpose(full_list, 2)))
else: # Einzelnen Spalten separat berechnen
[genL, genM, genR] = gen_wage_generator(n, i, False)
genL = [f"{x:3}" for x in genL]
genM = [f"{x:3}" for x in genM]
genR = [f"{x:3}" for x in genR]
print(" Left: ", end='')
print(",".join(genL))
print(" Middle: ", end='')
print(",".join(genM))
print(" Right: ", end='')
print(",".join(genR))
def print_all_wages(n):
for i in range(n):
print_wage(n,i)
# Plan für einzelne Kugel berechnen
def gen_plan(n, x, printTx=False):
Tx = T(n,x)
p = []
if printTx:
print(f"T({x}) = {Tx}")
Prefixes = ["01", "21", "10"]
try:
j = Prefixes.index(Tx[0:2])
p.append(j)
p.append((j+1)%3)
for i in range(2,n):
p.append(int(Tx[i]))
return p
except ValueError: # 2^{k-l}0 case
pass
j = int(Tx[-1])
p.append(j)
p.append(j)
# Eval l in 2^{k-l}0, k=n-2
# izero = k-l = n-2-l, l = n-2-izero
izero = Tx.index("0")
l = n - 2 - izero
# j2 = int(Tx[n-l]) # Index kann negativ sein...
for i in range(2,n-l-1):
p.append(int(Tx[n-l-1]))
for i in range(n-l-1, n-l):
p.append((int(Tx[n-l-1])+1)%3)
# 2^{k-l}0*^{l-e}j...
#
# k+2-e = n-(n-1-i) = i+1
for i in range(n-l, n):
p.append(int(Tx[i]))
return p
# Compare eval_all_entries_of_wage
# with plan(n,x) output
def collect_and_compare_plans(n):
waagen = []
for i in range(n):
gen = eval_all_entries_of_wage(n, i)
waagen.append(list(gen))
kugeln = []
for x in range(0, M(n)):
kugeln.append(gen_plan(n,x))
# Waagen ist Liste mit n Einträgen.
# Jeder Eintrag hat M(n)/3 Einträge von 3-Tupeln
# wobei Index (0) für die linke Seite steht, usw.
#print(waagen)
# Kugeln ist M(n)-lange Liste mit n-Tupeln, welche 0-2 enthalten.
#print(kugeln)
error = False
for iwaegung in range(n):
waegung = waagen[i]
for (l,m,r) in waegung:
if kugeln[l][i] != 0:
error = True
if kugeln[m][i] != 1:
error = True
if kugeln[r][i] != 2:
error = True
if error:
print(f"Fehler bei Waegung {iwaegung} und Tripel {l},{m},{r}.")
print(f" Kugel {l} wird auf {kugeln[l][i]} gelegt.")
print(f" Kugel {m} wird auf {kugeln[m][i]} gelegt.")
print(f" Kugel {r} wird auf {kugeln[r][i]} gelegt.")
break
if error:
break
if not error:
print("Individuell berechnete Kugelpläne passen zu Gesamtwägeplan.")
return error
def parse_args():
parser = argparse.ArgumentParser()
parser.add_argument('-n', dest="n", default=4, type=int,
help='Kompletten Wägeplan für n Wägungen ausgeben.')
parser.add_argument('-x', '--kugel', dest="x", default=None, type=int,
help='''\
Wägeplan für Kugel x ausgeben\
Wägungen werden nicht komplett berechnet.\n\
Negative x um M(n) (rechter Intervalrand) verschoben.\
''')
parser.add_argument('-i', default=None, type=int,
help='Nur i-te Wägung eines Plans ausgeben')
parser.add_argument('-T', dest="listT", action='store_true',
help='T(x)[0,M(n))-Werte auflisten')
parser.add_argument('-c', '--check', dest="check", action='store_true',
help='''\
Prüfe ob alle Einzel-Kugelpläne das gleiche\
Resultat wie die Komplettberechnung liefern.\
''')
return parser.parse_args()
if __name__ == "__main__":
#n = 4
#if len(sys.argv) > 1:
# n = int(sys.argv[1])
args = parse_args()
n = args.n
if args.listT:
print("T(x):")
print_labels(n)
if args.i is None and args.x is None:
print(f"Alle Wägungen für n={n}:")
print_all_wages(n)
if not args.i is None:
if args.i >= n or args.i < 0:
print(f"IndexError: i-argument needs to be in [0,…,{n-1}]")
else:
print_wage(n,args.i)
if not args.x is None:
x = args.x
if x < 0:
x = M(n) + x
if x >= M(n) or x<0:
print(f"IndexError: x-argument needs to be in [0,…,{M(n)-1}]")
else:
print(f"Kugelplan für {x}:")
p = gen_plan(n,x)
print(p)
print(" (0: Kugel links, 1: Kugel mittig, 2: Kugel rechts)")
if args.check:
collect_and_compare_plans(n)
\sourceoff
\showoff
Mit -n N kann man alle Wägungen auflisten. Mit -n N -x ID
kann man es auf eine Kugel einschränken.
Beispiele:
\sourceon Bash
\numberson
python3 Insulaner.py -n 4
Alle Wägungen für n=4:
Waage 0:
Left: 0, 1, 2, 3, 4, 5, 6, 7, 8, 27, 28, 29, 36
Middle: 9, 10, 11, 12, 13, 14, 15, 16, 17, 30, 31, 32, 37
Right: 18, 19, 20, 21, 22, 23, 24, 25, 26, 33, 34, 35, 38
Waage 1:
Left: 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 36
Middle: 0, 1, 2, 3, 4, 5, 6, 7, 8, 30, 31, 32, 37
Right: 9, 10, 11, 12, 13, 14, 15, 16, 17, 33, 34, 35, 38
Waage 2:
Left: 0, 1, 2, 9, 10, 11, 18, 19, 20, 33, 34, 35, 36
Middle: 3, 4, 5, 12, 13, 14, 21, 22, 23, 27, 28, 29, 37
Right: 6, 7, 8, 15, 16, 17, 24, 25, 26, 30, 31, 32, 38
Waage 3:
Left: 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 38
Middle: 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 36
Right: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 37
\sourceoff
\sourceon Bash
\numberson
python3 Insulaner.py -n 363 -x 123456789012345678901234567890123456789012345678901234567890
Kugelplan für 123456789012345678901234567890123456789012345678901234567890:
T(123456789012345678901234567890123456789012345678901234567890) = 010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002112200221011222211011210021001120212001202021200222211221110110111020200111100101002022201001121102100021221122100010221000
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 1, 2, 2, 0, 0, 2, 2, 1, 0, 1, 1, 2, 2, 2, 2, 1, 1, 0, 1, 1, 2, 1, 0, 0, 2, 1, 0, 0, 1, 1, 2, 0, 2, 1, 2, 0, 0, 1, 2, 0, 2, 0, 2, 1, 2, 0, 0, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 2, 0, 2, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 2, 0, 2, 2, 2, 0, 1, 0, 0, 1, 1, 2, 1, 1, 0, 2, 1, 0, 0, 0, 2, 1, 2, 2, 1, 1, 2, 2, 1, 0, 0, 0, 1, 0, 2, 2, 1, 0, 0, 0]
(0: Kugel links, 1: Kugel mittig, 2: Kugel rechts
\sourceoff
|
Profil
|
Diophant
Senior
Dabei seit: 18.01.2019
Mitteilungen: 11123
Wohnort: Rosenfeld, BW
 | Beitrag No.91, eingetragen 2023-11-04
|
Hallo Yggdrasil,
\quoteon(2023-11-04 14:48 - Yggdrasil in Beitrag No. 90)
Gibt es neben Bildern auf dem MP auch die Option PDFs hochzuladen?
\quoteoff
Nicht so, dass sie direkt im Beitrag angezeigt werden. Aber über einen kleinen Umweg geht es:
- Im eigenen Notizbuch eine öffentliche Notiz anlegen
- Zu dieser Notiz die Pdf-Datei hochladen
- Durch Rechtsklick auf das Dateisymbol im Notizbuch, das jetzt vorhanden ist, die URL zu dem Anhang holen und in den Beitrag im Thread kopieren.
Danach kann jeder Interessierte durch Klick auf deinen Link die Pdf-Datei für sich herunterladen. Wichtig ist dabei wie gesagt, dass die Notiz auf 'öffentlich' gestellt wird, sonst bist du der einzige, der darauf zugreifen kann.
Gruß, Diophant
|
Profil
|
Yggdrasil
Senior
Dabei seit: 01.07.2004
Mitteilungen: 873
Wohnort: Berlin
| Beitrag No.92, eingetragen 2023-11-04
|
Danke, Diophant.
Pdf-Link: https://matheplanet.com/matheplanet/nuke/html/dl.php?id=2492
Da ich nicht sicher bin ob obiger Download-Link konstant bleibt, wenn ich das PDF später austausche hier noch der Link zum öffentlichen Eintrag des Notizbuchs: https://matheplanet.com/matheplanet/nuke/html/fav.php?op=print&fav_id=93525&select=gelb
Das meiste ist nur die Definition der Schreibweisen, etc.
Auf Seite 3 ist die Definition der Konvertierung einer Insulaner/Kugel-Id
in ein Label. Da die Label mit wachsendem n nur hinten geändert werden ergibt sich dann die Beschreibung der Mengen (links, mittig, rechts) für jede Wägung auf Seite 6-7.
|
Profil
|
Diophant
Senior
Dabei seit: 18.01.2019
Mitteilungen: 11123
Wohnort: Rosenfeld, BW
| Beitrag No.93, eingetragen 2023-11-04
|
\quoteon(2023-11-04 15:15 - Yggdrasil in Beitrag No. 92)
Pdf-Link: https://matheplanet.com/matheplanet/nuke/html/dl.php?id=2492&1699106776
Da ich nicht sicher bin ob obiger Download-Link konstant bleibt, wenn ich das PDF später austausche...
\quoteoff
Nein, das wird er meiner Kenntnis nach nicht tun. Ich kann dir aber bestätigen: der Link funktioniert.
Gruß, Diophant
|
Profil
|
| Caban hat die Antworten auf ihre/seine Frage gesehen. | | Seite 3 | Gehe zur Seite: 1 | 2 | 3 |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
