24/10/2015 Olimpiadi di Problem Solving filerighe di una scrittura che l'ufficiale non aveva mai...

24/10/2015 Olimpiadi di Problem Solving

http://www.olimpiadiproblemsolving.com/preview2_allenamento.php?4a7or2cp05jqp7eq7asaq1da94&idp=59 1/6

Codice test: 2012-g1-sec-sec - Titolo: 2012-allenamento-gara1-sec-sec

Domanda numero 1 - Codice 2012-SS-G1-001 - Livello di difficoltà: 1.00

PREMESSA: Con il termine

regola(<sigla>,<lista antecedenti>,<conseguente>,<peso>)

si può descrivere una regola (di deduzione) che consente di dedurre il conseguente conoscendo tutti gli elementi contenuti nella lista degliantecedenti; ogni regola è poi identificata in modo univoco da una sigla e ha un peso, che dà l'idea di quanto sia oneroso applicarla. Peresempio, dato il seguente insieme di regole:

regola(1,[c1,c2],i,12) regola(2,[i,h],a,3) regola(3,[h,p1],c1,2) regola(4,[h,p2],c2,7) regola(5,[c1,c2],a,4) regola(6,[p1,p2],h,3)

regola(7,[p1,p2],i,2) regola(8,[c1,i],c2,8) regola(9,[i,a],h,6),

si osserva che, conoscendo gli elementi contenuti nella lista [p1,p2], è possibile dedurre (direttamente) h con la regola 6 e i con laregola 7; ma conoscendo [p1,p2] è anche possibile dedurre c1 applicando prima la regola 6 (per dedurre h) e poi la regola 3(conoscendo ora [h,p1]). Si può quindi dire che la lista [6,3] rappresenta un procedimento per dedurre c1 da [p1,p2]; la lista contieneinfatti l'indicazione delle regole che devono essere applicate. Per esempio, la lista [6,3,4,5] rappresenta un procedimento per calcolare ada [p1,p2]. Sommando i pesi delle regole applicate è possibile ottenere una valutazione del procedimento; pertanto, si può affermareche il procedimento [6,3,4,5] per dedurre a da [p1,p2] ha valutazione di 16.

PROBLEMA: È dato il seguente insieme di regole (in cui il nome del termine è "rs" invece di "regola"):

rs(1,[c1,c2],i,12) rs(2,[c1,i],c2,7) rs(3,[c2,i],c1,7) rs(4,[i,h],a,7). rs(5,[a,h],i,7) rs(6,[i,a],h,7) rs(7,[c1,c2],a,12) rs(8,[c1,a],c2,12). rs(9,[c2,a],c1,12) rs(10,[c1,p1],h,7) rs(11,[c1,h],p1,7) rs(12,[p1,h],c1,7).rs(13,[p1,p2],h,8) rs(14,[h,p1],p2,7) rs(15,[p2,h],p1,7) rs(16,[c2,p2],h,7). rs(17,[c2,h],p2,7) rs(18,[p2,h],c2,7) rs(19,[c1,p1],i,7) rs(20,[c1,i],p1,7).rs(21,[p1,i],c1,7) rs(22,[c2,p2],i,7) rs(23,[c2,i],p2,7) rs(24,[p2,i],c2,7).rs(25,[p1,p2],i,2) rs(26,[i,p1],p2,2) rs(27,[p2,h],p1,2).

Dati gli elementi [c1,a], trovare la lista L che descrive il procedimento per derivare p1 che abbia valutazione K minima e calcolare ilvalore di K.

L [

]

K


PROBLEMA: Nel seguente testo in inglese, sostituire a X1, X2, ... X9 i vocaboli indicati con A, B, ... O elencati di seguito, in modo daricostruire frasi con senso compiuto.

X1 don't like sweeping generalizations, particularly when our X2 make them. But X3 are generally more X4 of this offence as the speakergets more grey hairs. So I'm going to start off with a big X5 that probably will not hurt anyone's feelings. A little gimmick that I use in myhistory course is this: after a few weeks when students read a little bit about the general history of mathematics, I ask them to make a

X6 of the twenty most important events in the history of X7. Their lists and mine lead to a lively discussion. On my list appears themodern X8 as one of the very most important mathematical events of all time.

I think that it would remain on even the X9 list that one could imagine.

Lista dei vocaboli tra cui scegliere quelli da usare per la sostituzione:

A) mathematics B) shortest C) physics D) camera E) historians F) tolerant G) longest H) integration I) music J) HistoriansK) generalization L) list M) computer N) strangest O) students

Compilare la tabella seguente, associando ad ogni X1, X2, ... la lettera A, B, ... che individua il vocabolo da inserire nel testo.

X1

X2

X3

X4

X5

X6

X7

X8

X9


PROBLEMA: Nel seguente testo alcuni vocaboli sono stati sostituiti dalle sigle X1, X2, X3, ...



L'ufficiale scorse una grossa X1: era larga X2 centimetri e alta circa X3 centimetri. Nella parte X4 vi erano 14 righe di figurine X5 chel'ufficiale riconobbe come X6, la misteriosa scrittura usata migliaia di anni prima dagli antichi X7. Nella parte centrale erano incise 32righe di una scrittura che l'ufficiale non aveva mai visto prima. Nella parte inferiore vi erano 54 righe in lingua X8. Qualche giorno dopo ilnero basalto inciso fu mandato ad Alessandria: l'ufficiale non immaginava affatto che proprio lui e i suoi soldati avevano compiuto unodei più importanti ritrovamenti X9 di tutti i tempi. La stele di X10, come fu chiamato il blocco ritrovato, fornì agli X11 la chiave perdecifrare l'antica scrittura egizia, rendendo sempre più sicura la conoscenza e la interpretazione di quella perduta X12.

Per dare senso compiuto al testo, sostituire le sigle X1, X2, X3, ... con vocaboli appropriati scelti dalla lista seguente; per specificarequeste sostituzioni, accoppiare a ciascuna X la sigla A che individua il vocabolo prescelto. L'ultimo accoppiamento è riportato a mo' diesempio.

A1 superiore A2 Sumeri A3 greca A4 archeologici A5 75 A6 posteriore A7 centinaia A8 latina A9 librari A10 120 A11 stilizzate A12 pietra A13 studiosi A14 Rosetta A15 100 A16 dipinte A17 civiltà A18 Egizi A19 geroglifici A20 150

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

X12


PREMESSA: Il seguente grafo stradale

può essere descritto dal seguente insieme di termini (ciascuno dei quali definisce un arco tra due nodi del grafo con la indicazione dellarelativa distanza)

a(n1,n2,2) a(n2,n3,5) a(n3,n4,3) a(n4,n5,4) a(n5,n6,2) a(n6,n1,3)a(n1,n7,8) a(n2,n7,6) a(n3,n7,1) a(n4,n7,9) a(n5,n7,7) a(n6,n7,4)

Un percorso tra due nodi del grafo può essere descritto con la lista dei nodi che lo compongono ordinati dal nodo di partenza al nodo diarrivo. Per esempio, la lista [n5,n7,n2,n1] descrive un percorso dal nodo n5 al nodo n1 di lunghezza K = 15.

PROBLEMA

Disegnare il grafo stradale corrispondente al seguente insieme di termini (che hanno nome "as" invece di "a"):

as(n1,n2,2) as(n2,n3,6) as(n2,n4,3) as(n9,n3,5) as(n7,n8,5).as(n3,n7,7) as(n4,n7,9) as(n1,n5,10) as(n8,n9,4) as(n6,n8,7).

as(n5,n4,6) as(n5,n6,3) as(n6,n7,1) as(n3,n8,15)

Trovare la lista L del percorso più lungo (senza passare più di una volta per uno stesso nodo) fra il nodo n1 e il nodo n9; calcolare larelativa lunghezza K.

L[ ]

K


PROBLEMA: Nelle lezioni di educazione alimentare, i ragazzi hanno classificato alcuni alimenti in relazione al contenuto proteico e al lorocosto. I risultati di questa classificazione sono descritti da una tabella avente la dichiarazione



tabx(<sigla dell'alimento>,<tipo>, <valore proteico>, <costo>).

Il tipo si riferisce all'origine dell'alimento: "a" per vegetali, "b" per latticini, "c" per carni.

Il contenuto della tabella, che riporta i dati relativi a un certo numero di alimenti, è il seguente:

tabx(m1,a,190,148) tabx(m2,a,166,142) tabx(m3,b,180,131)tabx(m4,c,173,120) tabx(m5,a,196,150) tabx(m6,b,199,150)tabx(m7,b,192,138) tabx(m8,c,197,151) tabx(m9,b,198,149)tabx(m10,a,192,140) tabx(m11,c,188,149) tabx(m12,a,179,130)tabx(m13,b,185,141) tabx(m14,c,182,132) tabx(m15,c,199,148)tabx(m16,c,177,135) tabx(m17,c,177,140) tabx(m18,c,182,155)tabx(m19,a,185,140) tabx(m20,b,195,140) tabx(m21,c,184,198)tabx(m22,a,196,142) tabx(m23,b,180,140) tabx(m24,c,198,140)

Trovare le liste La, Lb e Lc delle sigle che corrispondono alle tre diete che si possono costruire con 3 elementi dello stesso tipo(rispettivamente vegetali, latticini e carne) aventi un costo non superiore a 425 e col maggior contenuto proteico Pa, Pb e Pc

N.B. Le sigle nelle liste devono comparire in ordine crescente: m1 prima di m2; m2 prima di m3, ... m14 prima di m15, ecc. A mo' diesempio sono riportati i valori di Lb e Pb.

La[ ]

Lb [m3, m6, m20]

Lc[ ]

Pa

Pb 574

Pc


PREMESSA

Alcuni ragazzi decidono di costruire un ipertesto multimediale sugli avvenimenti storici significativi della loro regione. Per organizzare ilprogetto, dividono il lavoro in singole attività e assegnano ogni attività a un gruppo di loro.

Le attività sono descritte col seguente termine

a(<sigla attività>,<durata in giorni>,<ragazzi impegnati>);

esempio, il termine a(a1,1,6) significa che l'attività a1 dura un giorno e impiega 6 ragazzi.

Le attività non possono svolgersi tutte contemporaneamente, ma devono essere rispettate delle priorità descritte con termini del tipo

p(<precedente>,<successiva>);

come per esempio p(a4,a8) e p(a6,a8); ogni termine esprime il fatto che l'attività associata alla sigla di destra (detta successiva) puòiniziare solo quando l'attività associata alla sigla di sinistra (detta precedente) è terminata. Ovviamente se una attività ha piùprecedenti, può iniziare solo quando tutte le precedenti sono terminate; i due termini appena visti implicano che l'attività a8 può iniziaresolo dopo che sono terminate le due attività a4 e a6.

PROBLEMA.

Le attività di questo progetto sono descritte dai seguenti termini:

a(a1,1,6), a(a2,2,4), a(a3,3,3), a(a4,2,1), a(a5,2,1), a(a6,2,6), a(a7,2,3), a(a8,2,7), a(a9,2,5), a(a10,1,4), a(a11,1,3), a(a12,1,8),a(a13,2,7), a(a14,2,1), a(a15,1,9).

Le priorità sono descritte dai seguenti termini:

p(a1,a2), p(a1,a3), p(a2,a4), p(a2,a5), p(a3,a6), p(a3,a7), p(a4,a8), p(a5,a8), p(a5,a9), p(a6,a8), p(a7,a8), p(a7,a10), p(a8,a12),p(a9,a11), p(a9,a13), p(a10,a11), p(a11,a12), p(a11,a14), p(a12,a15), p(a13,a15), p(a14,a15).

Trovare il numero minimo N di giorni necessari per completare il progetto, tenuto presente che alcune attività possono essere svolte inparallelo e che ogni attività deve iniziare prima possibile (nel rispetto delle priorità). Inoltre:

1. trovare il numero X1 del giorno in cui lavora il maggior numero MM di ragazzi;2. trovare il numero X2 del giorno in cui lavora il minor numero Mm di ragazzi;

N

X1

MM

X2

Mm


PREMESSA: Per descrivere una procedura di calcolo viene spesso usato uno pseudolinguaggio che utilizza parole inglesi e simbolimatematici. Compresa la sequenza dei calcoli descritti nell'esempio che segue, eseguire le operazioni indicate utilizzando i dati di inpute trovare il valore di output per la variabile Z.

PROBLEMA



procedure PROVA;input A, B, C;

S = 0;for I=1 to C do

S=S+I*I;endfor;if A>B

then K = A-B; else K = A+B;

endif;Z = S+K;output Z;

endprocedure;

I valori in input sono:

5 per A,7 per B,4 per C.

Z


PREMESSA: Si chiamano diagrammi di Ferrers (di n caselle o di contenuto n) delle configurazioni di n caselle disposte in una o più righeorizzontali, allineate a sinistra e tali che ogni riga deve contenere un numero di caselle uguale o inferiore a quello della riga superiore.Queste configurazioni si descrivono anche con la lista dei numeri che indicano le lunghezze delle righe: il primo numero indica le caselledella prima riga, il secondo le caselle della seconda riga, e così via. Esempi sono i seguenti: sopra ogni diagramma è riportata la listache lo descrive, che può essere chiamata forma.

Si chiama tabella di Young un diagramma di Ferrers di n caselle riempito con i numeri interi da 1 a n. Esempi sono i seguenti.

Se i numeri, dentro le caselle, sono disposti in modo che il loro valore risulti in ordine crescente, sia per riga sia per colonna, la tabella sidice standard; (vedi prima, terza e quinta tabella precedente).

Nelle tabelle standard, la prima casella della prima riga contiene sempre 1. Il numero n si trova sempre nella casella più a destra di unadelle righe del diagramma.

Infine, si tenga presente che, per esempio, per [4] e [1,1,1,1] esiste una sola tabella standard; per [3,1] e [2,1,1] ne esistono 3; se,però, nel diagramma [2,1,1] si fissa il 4 nella seconda casella della prima riga, allora esiste un solo modo di completare la tabella inmaniera standard.

PROBLEMA

Si consideri il diagramma descritto dalla lista [4,4,2,2] in cui 8 è (fisso) nella seconda casella della seconda riga, 12 è (fisso) nellaquarta casella della seconda riga e 11 è (fisso) nella seconda casella della quarta riga;

Dire in quanti modi S è possibile completare il diagramma in maniera standard.

S


PROBLEMA

In un magazzino sono depositati alcuni scatoloni; la lista che descrive la sigla e il peso di ciascuno di questi è la seguente [(a1,5),(a2,4),(a3,3),(a4,2),(a5,6),(a6,4),(a7,4).

Due trasportatori A e B sono incaricati di spostare questi scatoloni in un altro deposito; in quanti modi N diversi A può portare via 3 diquesti materiali in modo da lasciare a B un trasporto con un carico complessivo uguale a quello da lui trasportato?



N


L'Hotel Fantasy ha delle chiavi per le stanze formate da un quadrato di plastica su cui sono segnati n´n cerchietti che possono essereperforati o no; i lettori, posti all'ingresso di ogni stanza, hanno una fenditura in cui si introduce la chiave e sono capaci di riconoscere sequesta è o no relativa a quella stanza; tutte le chiavi sono simmetriche, così che non ha importanza con quale lato viene introdotta nel

lettore.

Una chiave, formata da 4´4 cerchietti, è la seguente.

Quale è N, il massimo numero di stanze che può avere l'hotel?

N


PROBLEMA

Maps can be easily pictured as graphs. In such a graph every node is a country and the lines between the nodes mean that they bordereach other. The picture shows a graph of a map with seven countries.

Beaver Jim has to find a map that fits the given graph. He has four options. Can you help him find a map that matches the graph?

The graph:

Your answer: Map


PROBLEMA

Beaver paddles in his canoe on a river. The river has a number of little lakes. Beaver likes all lakes of the river and has thought of an algorithm to make sure that he reaches every lake.He knows that at each lake there is a maximum of two rivers that he has not yet seen.



If beaver arrives at a lake he decides which river to take with the following rules:If there are two rivers he has not yet seen, he takes the river on his left hand side;If there is one river which beaver has not yet seen, beaver takes this river;If beaver has seen all the rivers from a little lake, he paddles his canoe one lake back towards the previous lake.Beaver stops his day of canoeing if he has seen everything and has come back to the start point.Below you can see the river and the little lakes where beaver paddles his canoe:

In each little lake beaver sees a different animal. Beaver writes down the animal name when he sees an animal for the first time.

In which order will beaver write down the animals?

Multiple Choice:

A : fish, frog, crocodile, turtle, stork, snake, otter, duck B : fish, crocodile, snake, stork, duck, otter, frog, turtleC : fish, frog, turtle, crocodile, stork, otter, duck, snakeD : fish, crocodile, snake, stork, duck, otter, frog, turtle

Your answer

Stampa questa pagina

Torna alla gestione allenamenti

http://www.olimpiadiproblemsolving.com/gestione_allenamenti.php?4a7or2cp05jqp7eq7asaq1da94

24/10/2015 Olimpiadi di Problem Solving filerighe di una scrittura che l'ufficiale non aveva mai...

Documents

Transcript of 24/10/2015 Olimpiadi di Problem Solving filerighe di una scrittura che l'ufficiale non aveva mai...