domingo, 4 de abril de 2010

Tarjetas adecuadas

IV Concurso IES Miguel Hernández, 2009

Tenemos un conjunto de tarjetas marcadas con los números del 1 al 98, usando dos dígitos distintos en todas ellas (01, 02, 03, ..., 98).

Un conjunto de estas tarjetas se llama conjunto adecuado si ninguna de las tarjetas del conjunto tiene el primer dígito igual al segundo dígito de otra tarjeta del conjunto.

Encuentra un conjunto adecuado que tenga una suma lo mayor posible, que no pueda superar otro conjunto adecuado. Explica porqué no se puede obtener un conjunto adecuado con una suma mayor.

Solución

2 comentarios:

Lluís Usó dijo...

Si no he comés cap error, el conjunt que compleix les condicions, i té la suma màxima, és aquell que té 9,8,7,6,5,4,3 en les desenes, i només 2,1,0 en les unitats, la suma val aleshores 3045.

Primer que res, cal trobar una expressió algebraica per a la suma, així podem resoldre'l com un simple problema d'optimització en una variable:

Siga n el nombre de xifres que usarem per a les desenes (és òbvi que començarem pel 9, i utilitzarem les n majors...), ens queden per a les unitats 10-n xifres. Notació: S(a,b)[f(i)] representa el sumatori entre a i b dels valors f(i) amb i natural.

La suma val:

(10-n)*S(10-n, 9)[10i]+n*S(0,9-n)[i]=(5n^3)/2 -(195n^2)/2 + 995n

Derivem respecte a n:

(15n^2)/2 -195n + 995, igualem a 0, i resolem, n=6,97, o 19,023,

derivem un altre cop,

15n-195, evaluem en els possibles valors, i veiem que 19,023 és un mínim (de fet no pot ser ja que n<10), i 6,97 é màxim.

Ara, provem amb 7, i obtenim 3045, per si de cas, amb 6, dona 3000, per tant, el màxim amb n natural l'obtenim per a n=7 Vol dir que utilitzem les 7 xifres més elevades per a les desenes i la resta per a les unitats.

Supose que hi haurà mètodes més ràpids i senzills, però aquest té l'avantatge que no cal "idea feliç" ni cal argumentar per què la nostra solució és efectivament vàlida...

Damià Torres Latorre dijo...

Primer trobem una expressió algebraica per a la suma...
x= nº de xifres diferents en les desenes.
T_n= nombre triangular n
S=(100-10x)(T_9-T_(9-x))+T_9
Desenvolupem i reduïm i ens queda:
S=5x³-145,5x²+958,5x-45
Ara hem de trobar un màxim:
Posem S=f(x),i
f'(x)=15x²-291x+958,5; que s'anula per a x=15,1945...(no pot ser)
i x=4,2055...
Tornem a derivar:
f''(x)=30x-291
i com per a 4,2055 F''(x)<0, 4,2055
és màxim.
Provem amb 4 i la suma dóna 1860.
per si de cas provem amb 5; però dóna 1800.
Sol·lució: gastarem 4 xifres diferents en les desenes.
El conjunt és:
95 94 93 92 91 90
85 84 83 82 81 80
75 74 73 72 71 70
65 64 63 62 61 60

Aquest mètode és complicat i de nivell avançat però no cal explicar per què la solució és vàlida; i si els càlculs no fallen, no falla mai.