Ich suche Hilfe zur Chicken-Nugget-Zahl

8 views
Skip to first unread message

neu...@tuhh.de

unread,
Nov 24, 2021, 10:43:57 AM (5 days ago) Nov 24
to
43 ist die Chicken-Nugget-Zahl, McDonalds, Chicken-Nuggets!!!

Nun gut, das muß man ggf. erläutern:
Chicken-Nuggets gibt es im 6er, 9er und 20ger Pack.
Will man z.B. 12, erhält man 6+6, möchte man 15, bekommt man 6+9, oder 21= 6+6+9, oder 41= 6+6+9+20, oder 42= 6+6+6+6+6+6+6 u.s.w.

Es gibt ein paar Anzahlen, die man nicht bestellen kann, z.B. 11, oder eben 43 oder oder oder. Aber 43 ist die größte Zahl die nicht abgeliefert werden kann!

Damit ist 43 die Chicken-Nugget-Zahl. qed. ;-)

Wie das mit Mathematiker so ist, der Spieltrieb ist geweckt!


Als ich das in der Google-Rätsel-Gruppe vorstellte, bekam ich nicht eine Antwort. Ich habe aber ggf. selber Schuld, da ich selbst keinen vollständigen theoretischen Zugang finde!

Ich stelle mal dar, wie weit ich komme und bitte hier explizit um Mithilfe. Ich finde es ist interessante, gar nicht so schwere Mathematik und der Ingenieur in mir ist auch zufrieden, nur der Mathematiker hatt's eben vollständig!


Mathematisch formulierte, 6x +20y +9z= n= 43
läßt sich in positiven ganzen Zahlen x, y, z nicht lösen und
43 ist die größte positive ganze Zahl n für die diese Aussage gilt!


Also, 6x +20y +9z= n= N= 43 ist eine lineare Diophantische Gleichung.
Sie ist lösbar (in Ganzen Zahlen), wenn ggT(x,y,z)|n.
Es gilt hier, ggT(6,20,9)=1 und 1 teilt natürlich jedes n.

Also gibt es hier Lösungen in den ganzen Zahlen IZ.

(Für den Fall, für bel. x,y,z mit ggT(x,y,z)= C>1,
gibt es überhaupt nur Lösungen wenn C|n,
wenn nicht gibt es sicher gar keine größte solche Zahl n=N)

Wenn N=43 eine Zahl ist, für die sich diese Gleichung in positiven ganzen Zahlen x, y, z nicht lösen läßt, aber sich die 6 Zahlen 44, 45, 46, 47, 48 und 49 darstellen lassen und damit auch alle weiteren - indem man immer wieder 6 hinzuzählt, folgt, daß n=N=43 die größte solche Zahl ist! QED.).


Nehmen wir an das Problem sei Lösbar (d.h. ggT(x,y,z)= 1),
wie finde ich nun die Kandidaten n aus IN als Anwärter für die größte Zahl N?

Da das Problem lösbar ist, liefert die Theorie für die Menge der Lösungen zu irgendeinem n folgendes:

Für alle (a,b) aus IZxIZ und n aus IN gilt:
Es gibt x(a,b), y(a,b) u. z(a,b) so daß: 6x(a,b) +20y(a,b) +9z(a,b)= n

Aber, für x<0 od. y<0 od. z<0 ist es keine Lösung in natürlichen Zahlen.

Wie findet man die n aus IN für die es keine Lösung x,y,z aus IN gibt?

Man findet, da ggT(x,y,z)=1 mindestens ein Paar (u,v) aus {x,y,z} mit ggT(u,v)=1 und damit - hier ohne Beweis -,
daß N'= u*v -u -v eine obere Grenze für N ist!


a) Analog dem Sieb des Eratosthenes füllt man ein Array f(n) mit 0<n<N',
und schaut nach für welche n f(n) leer bleibt

Hat man ein N'=m als obere Schranke für's Suchen. Mit Python:

n=[20,6,9]
m=151
f=list(range(0,m+1))
for i in range(0,int((m+1)/n[1])):
_for j in range(0,int((m+1)/n[2])):
__for k in range(0,int((m+1)/n[0])):
___a=i*n[1]+j*n[2]+k*n[0]
___if a<m+1:
____f[a]=0
print(f)


b) Theoretischer: Man findet explizit die 3 Ungleichungen

x= f(a,b,y,z) >= 0,
y= g(a,b,x,z) >= 0,
z= h(a,b,x,y) >= 0,

die aber leider nichtlinear sind!

Eventuell gelingt es zu zeigen, daß für bel. (a,b) kein (x(a,b,z,y),y(a,b,z),z(a,b)) im positiven Oktanten liegt!

Ein bißchen unübersichtliche Übersicht erhält man mit Python durch:

r=6
s=20
t=9
N= 50
for u in range(30,N):
_for a in range(-2,3):
__for b in range(-2,3):
___if u%r-r*a < 0:
____z= -((u%r-r*a)%(s%r))-(s%r)*b
____y=((u%r-r*a)+1)//(s%r)-z*((t%r)//(s%r))+b
___else:
____z= (u%r-r*a)%(s%r)-(s%r)*b
____y= (u%r-r*a)//(s%r)-z*((t%r)//(s%r))+b
___x= -(s//r)*y -(t//r)*z +u//r +a
____if x<0 or y<0 or z<0:
_____pass
____else:
_____print(u,a,b)

Ausgegeben wird ein Lösbares n und die Parameter (a,b) dafür!

(Anmerkung: Der Lösungsgang bedingt die Reihenfolge (x,y,z)= (6,20,9).
Andere Werte für x,y und z mögen andere Reihenfolgen bedingen!)

Die "Rahmenparameter" u,a,b habe ich schon "optimiert",
man erkennt auch ein bißchen Struktur
und, daß a,b <0 _kein_ hinreichendes Kriterium ist!


Weiß jemand weiter?
Bitte sagt doch mal was dazu!

VG Siggi N.

neu...@tuhh.de

unread,
Nov 24, 2021, 10:58:36 AM (5 days ago) Nov 24
to
Bevor ich erschlagen werde: Z.B. https://de.wikipedia.org/wiki/M%C3%BCnzproblem

Hast Du schon gegoogelt!? :-( Pardon!

Siggi N.
Reply all
Reply to author
Forward
0 new messages