door drc. » ma 26 mei 2014, 12:43
Mijn implementatie is werkend. Hier is de methode met de oorspronkelijke opgave als voorbeeld.
Als een getal productless is, is het product van de cijfers kleiner of gelijk aan de som. Dus zijn alle getallen die we vinden door de cijfers te herschikken ook productless. Bijvoorbeeld 321 is productless dus 123, 132, 213, 231 en 312 ook productless.
Zoals Arie al vaststelde, voldoen alle getallen waar minstens een cijfer een 0 zit. De beschrijving is voor productless getallen zonder 0 erin.
Eerst onderzoeken we de set A. Alle cijfers van A zijn van 2 t/m 9, met cijfers in aflopende volgorde.
Stel a_i is het element in A zodat n-1 elementen in A kleiner zijn dan a_n
Dan a_1 = 2, a_{10} = 32, a_{100} = 777.
Stel nu d_jd_{j-1}\cdots d_{1} de cijfers van a_n, de cijfers aan elkaar gekoppeld. Voor a_{10} hebben we dan d_2 = 3,\, d_1 = 2
Het blijkt dat {m + 8 \choose m} - 1 = {m + 8 \choose 8} - 1 elementen hoogstens m cijfers hebben. Daar maken we gebruik van.
Om a_i te vinden schrijven we i eerst in de vorm
{m + 8 \choose 8} + \sum_{j=1}^{m+1} {c_j \choose j}
Hier een voorbeeld voor het bepalen van a_{83}
m wordt zo gekozen dat {m + 8 \choose 8} \le i maar {m + 8 + 1 \choose 8} > i. We kiezen m "maximaal".
Voor a_{83} vinden we dan m = 2.
Dan verminderen we i met {m + 8 \choose 8} = 45 geeft n = 83 - 45 = 38.
Dus schrijven we 38 in de vorm. Omdat m = 2 heeft a_{83} drie cijfers
\sum_{j=1}^{m+1} {c_j \choose j}
We bepalen c_3, door die maximaal te kiezen en dan n verminderen met {c_3 \choose 3}, dan evenzo c_2 en c_1.
We vinden dat 38 = {7 \choose 3} + {3 \choose 2} + {0 \choose 1} En dus
c_3 = 7, c_2 = 3, c_1 = 0.
Dan gebruiken we de relatie tussen c_i en d_i, d_i = c_i + 3 - i.
We vinden dan d_3 = 7 + 3 - 3 = 7,\, d_2 = 3 + 3 - 2 = 4,\, d_1 = 0 + 3 - 1 = 2
Dus a_{83} = 742. Je zou kunnen stoppen met het bepalen van c_i als n = 0, de cijfers zijn 2 vanaf dan.
Als achter een getal een 1 wordt gezet, neemt de som van de cijfers toe met 1, maar het product blijft gelijk. Dus als een getal productless is, kunnen we zoveel enen erachter plakken als we willen en dan is het resultaat nog steeds productless. Hier maken we gebruik van door de score te bepalen van een element in A.
De score van een element in A is het aantal cijfers dat minstens nodig is om die cijfers te bevatten.
a_10 = 32 is niet productless want 3 * 2 > 3 + 2. Als we een 1 achter 32 plakken, krijgen we 321. Dit is productless want 3 * 2 * 1 <= 3 + 2 + 1. De score van 32 is dus 3, want 321 heeft 3 cijfers.
Op vergelijkbare manier vinden we dat 742 een score heeft van 46.
7 * 4 * 2 = 56. 7 + 4 + 2 = 13. Er moeten nog minstens 56 - 13 = 43 enen achter worden geplakt voor een productless getal.
De score van een element in A met m cijfers is dus \prod_{i=1}^{m}d_i - \sum_{i=1}^{m}d_i + m
Hoeveel productless getallen kleiner dan 10^9 bevatten nu alleen 32 en voor de rest enen?
De cijfers van 32 kunnen op 2 manieren worden gerangschikt.
321 voldoet, net als 3211, 32111, 321111, 3211111,...,321111111 net als alle herschikkingen van de cijfers.
Als we de cijfers 32 in die volgorde laten staan, dan zijn er {3 \choose 2} mogelijke herschikkingen van de cijfers van 321; 132, 312 en 321. We vermenigvuldigen met 2 want 32 kan op 2 manieren worden gerangschikt.
Vergelijkbaar vinden we dat voor 3211 2 \cdot {4 \choose 2} = 12 herschikkingen zijn, zodat we voor 32 een totaal van
\sum_{i=3}^{9} \left( 2 \cdot {i \choose 2}\right) vinden.
Om die som te vinden kunnen we gebruik maken van de volgende identiteit:
\sum_{i=m}^{n} {k \choose m} = {n + 1 \choose m + 1}
Zodat
\sum_{i=3}^{9} 2 \cdot {i \choose 2} = 2 \cdot \left(\left(\sum_{i=0}^{9} {i \choose 2}\right) - \left(\sum_{i=0}^{2} 2 \cdot {i \choose 2} \right) \right) = 2 \cdot \left( {10 \choose 3} - {3 \choose 3} \right) = 2(120 - 1) = 238
Om het aantal permutaties van 32 of ook van grotere elementen van A te bepalen, bijv. 99888777755555 kan op minstens twee manieren.
- Bepaal het aantal cijfers m van a in A. Er zijn hoogstens m! herschikkingen. Voor elk uniek cijfer, deel door de frequentie van dat cijfer in a.
9 komt 2 keer voor, dus voor 9, deel door 2!. Het resultaat is {14 \choose 2,3,4,5} = 2522520.
- Stel (lokaal) n = 0, k = 0, r = 1. r is het resultaat. Voor elk uniek cijfer, tel bij n de frequentie op. stel k is de frequentie.
Dit geeft voor 99888777755555 (bijvoorbeeld, hangt van de volgorde van zoeken naar unieke cijfers af)
{2 \choose 2} \cdot {5 \choose 3}\cdot {9 \choose 4}\cdot {14 \choose 5} = 2522520.
We kunnen proberen om alle elementen in A af te lopen, maar A heeft oneindig veel elementen, en we hoeven niet eens alle elementen af te lopen,
want we kijken naar een totaal van hoogstens 9 cijfers, ofwel de score van een element uit A mag hoogstens 9 zijn.
Hoeveel cijfers kan a in A dan maximaal hebben?
Als a hoogstens 1 cijfer heeft, dan werkt a = 2 nog, maar a = 22 niet. Als a hoogstens 2 cijfers heeft, dan werkt a = 22 nog maar a = 222 niet.
2 heeft een score van 1.
22 heeft een score van 2
222 heeft een score van 2*2*2 - (2+2+2) + 3 = 5
2222 heeft een score van 12. 12 > 9 Dus a heeft hoogstens 3 cijfers.
Algemeen, Een getal met n tweeën heeft een score van 2^n - 2*n + n = 2^n - n.
Voor maximaal q cijfers,
Om 2^n - n te verhogen naar 2^n, moeten we bij q nog \lceil \frac{\log(q)}{\log(2)} \rceil optellen.
Dan geeft \lfloor \frac{q + \lceil \frac{\log(q)}{\log(2)} \rceil}{\log(2)} \rfloor
Behalve als q <= 2, dan moet nog 1 worden opgeteld.
We kunnen nu dus alle elementen in A aflopen die hoogstens 3 cijfers hebben. Dat zijn er {11 \choose 8} - 1 = 164,
maar we kunnen er veel overslaan. Dit gedeelte vond ik het lastigst.
Bijvoorbeeld, 63 heeft score 11, dus hoeven we 64, 65 en 66 niet te checken, en kunnen we door naar 72. 72 werkt, maar 73 niet dus kunnen we door
naar 82.
Mijn methode hiervoor is als volgt:
Zoek de plaats van het teken voor de eerste 2. Als er geen twee is, is het de laatste plaats. Voor 99992222 is dat 3. Voor 33 is dat 2. De variabele is y.
Zoek de plaats na de laatste 9. Als er geen 9 is, is het 1. Voor 99992222 is het 5. Voor 33 is het 1.
Bepaal y - t. Is het groter dan 0, dan, kijk naar het cijfer links van y. Verhoog het eerste cijfer van links dat hetzelfde is
als d_y met 1. Alle cijfers rechts daarvan worden 2.
Als het niet groter dan 0 is, verhoog het aantal cijfers met 1 en maak elk cijfer 2. Als we van a_{i} naar a_{i+1} willen gaan
kan dat op vergelijkbare manier.
Mijn implementatie is werkend. Hier is de methode met de oorspronkelijke opgave als voorbeeld.
Als een getal productless is, is het product van de cijfers kleiner of gelijk aan de som. Dus zijn alle getallen die we vinden door de cijfers te herschikken ook productless. Bijvoorbeeld 321 is productless dus 123, 132, 213, 231 en 312 ook productless.
Zoals Arie al vaststelde, voldoen alle getallen waar minstens een cijfer een 0 zit. De beschrijving is voor productless getallen zonder 0 erin.
Eerst onderzoeken we de set A. Alle cijfers van A zijn van 2 t/m 9, met cijfers in aflopende volgorde.
Stel [formule]a_i[/formule] is het element in [formule]A[/formule] zodat [formule]n-1[/formule] elementen in [formule]A[/formule] kleiner zijn dan [formule]a_n[/formule]
Dan [formule]a_1 = 2[/formule], [formule]a_{10} = 32[/formule], [formule]a_{100} = 777[/formule].
Stel nu [formule]d_jd_{j-1}\cdots d_{1}[/formule] de cijfers van [formule]a_n[/formule], de cijfers aan elkaar gekoppeld. Voor [formule]a_{10}[/formule] hebben we dan [formule]d_2 = 3,\, d_1 = 2[/formule]
Het blijkt dat [formule]{m + 8 \choose m} - 1 = {m + 8 \choose 8} - 1[/formule] elementen hoogstens m cijfers hebben. Daar maken we gebruik van.
Om [formule]a_i[/formule] te vinden schrijven we i eerst in de vorm
[formule]{m + 8 \choose 8} + \sum_{j=1}^{m+1} {c_j \choose j}[/formule]
Hier een voorbeeld voor het bepalen van [formule]a_{83}[/formule]
[formule]m[/formule] wordt zo gekozen dat [formule]{m + 8 \choose 8} \le i[/formule] maar [formule]{m + 8 + 1 \choose 8} > i[/formule]. We kiezen m "[i]maximaal[/i]".
Voor [formule]a_{83}[/formule] vinden we dan [formule]m = 2[/formule].
Dan verminderen we i met [formule]{m + 8 \choose 8} = 45[/formule] geeft n = 83 - 45 = 38.
Dus schrijven we 38 in de vorm. Omdat [formule]m = 2[/formule] heeft [formule]a_{83}[/formule] drie cijfers
[formule]\sum_{j=1}^{m+1} {c_j \choose j}[/formule]
We bepalen [formule]c_3[/formule], door die maximaal te kiezen en dan n verminderen met [formule]{c_3 \choose 3}[/formule], dan evenzo [formule]c_2[/formule] en [formule]c_1[/formule].
We vinden dat [formule]38 = {7 \choose 3} + {3 \choose 2} + {0 \choose 1}[/formule] En dus
[formule]c_3 = 7, c_2 = 3, c_1 = 0[/formule].
Dan gebruiken we de relatie tussen [formule]c_i[/formule] en [formule]d_i[/formule], [formule]d_i = c_i + 3 - i[/formule].
We vinden dan [formule]d_3 = 7 + 3 - 3 = 7,\, d_2 = 3 + 3 - 2 = 4,\, d_1 = 0 + 3 - 1 = 2[/formule]
Dus [formule]a_{83} = 742[/formule]. Je zou kunnen stoppen met het bepalen van [formule]c_i[/formule] als n = 0, de cijfers zijn 2 vanaf dan.
Als achter een getal een 1 wordt gezet, neemt de som van de cijfers toe met 1, maar het product blijft gelijk. Dus als een getal productless is, kunnen we zoveel enen erachter plakken als we willen en dan is het resultaat nog steeds productless. Hier maken we gebruik van door de [i]score[/i] te bepalen van een element in A.
De score van een element in A is het aantal cijfers dat minstens nodig is om die cijfers te bevatten.
[formule]a_10 = 32[/formule] is niet productless want 3 * 2 > 3 + 2. Als we een 1 achter 32 plakken, krijgen we 321. Dit is productless want 3 * 2 * 1 <= 3 + 2 + 1. De score van 32 is dus 3, want 321 heeft 3 cijfers.
Op vergelijkbare manier vinden we dat 742 een score heeft van 46.
7 * 4 * 2 = 56. 7 + 4 + 2 = 13. Er moeten nog minstens 56 - 13 = 43 enen achter worden geplakt voor een productless getal.
De score van een element in A met m cijfers is dus [formule]\prod_{i=1}^{m}d_i - \sum_{i=1}^{m}d_i + m[/formule]
Hoeveel productless getallen kleiner dan 10^9 bevatten nu alleen 32 en voor de rest enen?
De cijfers van 32 kunnen op 2 manieren worden gerangschikt.
321 voldoet, net als 3211, 32111, 321111, 3211111,...,321111111 net als alle herschikkingen van de cijfers.
Als we de cijfers 32 in die volgorde laten staan, dan zijn er [formule]{3 \choose 2}[/formule] mogelijke herschikkingen van de cijfers van 321; 132, 312 en 321. We vermenigvuldigen met 2 want 32 kan op 2 manieren worden gerangschikt.
Vergelijkbaar vinden we dat voor 3211 [formule]2 \cdot {4 \choose 2} = 12[/formule] herschikkingen zijn, zodat we voor 32 een totaal van
[formule]\sum_{i=3}^{9} \left( 2 \cdot {i \choose 2}\right)[/formule] vinden.
Om die som te vinden kunnen we gebruik maken van de volgende identiteit:
[formule]\sum_{i=m}^{n} {k \choose m} = {n + 1 \choose m + 1}[/formule]
Zodat
[formule]\sum_{i=3}^{9} 2 \cdot {i \choose 2} = 2 \cdot \left(\left(\sum_{i=0}^{9} {i \choose 2}\right) - \left(\sum_{i=0}^{2} 2 \cdot {i \choose 2} \right) \right) = 2 \cdot \left( {10 \choose 3} - {3 \choose 3} \right) = 2(120 - 1) = 238[/formule]
Om het aantal permutaties van 32 of ook van grotere elementen van A te bepalen, bijv. 99888777755555 kan op minstens twee manieren.
- Bepaal het aantal cijfers m van a in A. Er zijn hoogstens m! herschikkingen. Voor elk uniek cijfer, deel door de frequentie van dat cijfer in a.
9 komt 2 keer voor, dus voor 9, deel door 2!. Het resultaat is [formule]{14 \choose 2,3,4,5} = 2522520[/formule].
- Stel (lokaal) n = 0, k = 0, r = 1. r is het resultaat. Voor elk uniek cijfer, tel bij n de frequentie op. stel k is de frequentie.
Dit geeft voor 99888777755555 (bijvoorbeeld, hangt van de volgorde van zoeken naar unieke cijfers af)
[formule]{2 \choose 2} \cdot {5 \choose 3}\cdot {9 \choose 4}\cdot {14 \choose 5} = 2522520[/formule].
We kunnen proberen om alle elementen in A af te lopen, maar A heeft oneindig veel elementen, en we hoeven niet eens alle elementen af te lopen,
want we kijken naar een totaal van hoogstens 9 cijfers, ofwel de score van een element uit A mag hoogstens 9 zijn.
Hoeveel cijfers kan a in A dan maximaal hebben?
Als a hoogstens 1 cijfer heeft, dan werkt a = 2 nog, maar a = 22 niet. Als a hoogstens 2 cijfers heeft, dan werkt a = 22 nog maar a = 222 niet.
2 heeft een score van 1.
22 heeft een score van 2
222 heeft een score van 2*2*2 - (2+2+2) + 3 = 5
2222 heeft een score van 12. 12 > 9 Dus a heeft hoogstens 3 cijfers.
Algemeen, Een getal met n tweeën heeft een score van 2^n - 2*n + n = 2^n - n.
Voor maximaal q cijfers,
Om 2^n - n te verhogen naar 2^n, moeten we bij q nog [formule]\lceil \frac{\log(q)}{\log(2)} \rceil[/formule] optellen.
Dan geeft [formule]\lfloor \frac{q + \lceil \frac{\log(q)}{\log(2)} \rceil}{\log(2)} \rfloor[/formule]
Behalve als q <= 2, dan moet nog 1 worden opgeteld.
We kunnen nu dus alle elementen in A aflopen die hoogstens 3 cijfers hebben. Dat zijn er [formule]{11 \choose 8} - 1 = 164[/formule],
maar we kunnen er veel overslaan. Dit gedeelte vond ik het lastigst.
Bijvoorbeeld, 63 heeft score 11, dus hoeven we 64, 65 en 66 niet te checken, en kunnen we door naar 72. 72 werkt, maar 73 niet dus kunnen we door
naar 82.
Mijn methode hiervoor is als volgt:
Zoek de plaats van het teken voor de eerste 2. Als er geen twee is, is het de laatste plaats. Voor 99992222 is dat 3. Voor 33 is dat 2. De variabele is y.
Zoek de plaats na de laatste 9. Als er geen 9 is, is het 1. Voor 99992222 is het 5. Voor 33 is het 1.
Bepaal y - t. Is het groter dan 0, dan, kijk naar het cijfer links van y. Verhoog het eerste cijfer van links dat hetzelfde is
als [formule]d_y[/formule] met 1. Alle cijfers rechts daarvan worden 2.
Als het niet groter dan 0 is, verhoog het aantal cijfers met 1 en maak elk cijfer 2. Als we van [formule]a_{i}[/formule] naar [formule]a_{i+1}[/formule] willen gaan
kan dat op vergelijkbare manier.
