24/10/2015
Olimpiadi di Problem Solving
C odice te st: Didam atica - Titolo: Didam atica
Domanda numero 1 - C odice 2011-R EG-SUP01 - Live llo di difficoltà: 1.00
PROBLEMA
Nel brano sotto riportato, sostituire a X1, X2, ... le parole più appropriate, elencate di seguito, in modo da dare significato compiuto al
testo.
Saper X1 sulle azioni da X2 per X3 un obiettivo è una X4 essenziale del comportamento intelligente. Questa competenza è stata X5
della ricerca in intelligenza artificiale sin dal suo X6 negli anni X7 del secolo scorso; in particolare è stata oggetto di X8 da parte dei
ricercatori interessati a X9 il comportamento umano nella risoluzione di problemi mediante sistemi X10 basati su computer.
A) riprodurre
E) regole
I) logica
M) raggiungere
Q) sessanta
B) cinquanta
F) artificiali
J) oggetto
N) studio
R) trenta
C) artistici
G) ragionare
K) meccanici
O) metodo
S) elucubrazione
D) novanta
H) esordio
L) competenza
P) compiere
T) obbiettivo
Per indicare le sostituzioni, nella tabella seguente, si deve associare a ciascuna X1, X2, ... la lettera che individua la parola da
inserire nel testo.
N.B. Non tutti i vocaboli della lista devono essere usati.
X1
X2
X3
X4
X5
X6
X7
X8
X9
X10
Domanda numero 2 - C odice 2011-R EG-SUP02 - Live llo di difficoltà: 1.00
PROBLEMA
Nel brano sotto riportato, sostituire a X1, X2, ... le parole più appropriate, elencate di seguito, in modo da dare significato compiuto al
testo.
The best X4 of the day was the journey to London. My train was on X1. I found a X3 in the Quiet Coach, X2 my hearing aid, and
settled down with the Guardian and a new X5 of Hardy. Whether and when to wear your X6 aid on a journey by X8 transport, if you're
travelling alone and don't have to make X7 with anybody, is a complex question. Obviously you need to wear it to X9 your ticket and
hear possible change-of-platform X10 at the station, but it's tempting to take it out once you're on the train ...
A) removed
F) time
N) public
S) buy
B) part
G) side
O) speaking
T) announcements
C) distant
H) history
P) platform
U) sell
D) biography
I) seat
Q) hearing
E) novel
L) acquire
R) conversation
Per indicare le sostituzioni, nella tabella seguente, si deve associare a ciascuna X1, X2, ... la lettera che individua la parola da
inserire nel testo. La prima risposta è data a mo' di esempio.
N.B. Non tutti i vocaboli della lista devono essere usati.
X1
X2
F
X3
X4
X5
X6
X7
X8
http://www.olimpiadiproblemsolving.com/preview2_allenamento.php?4a7or2cp05jqp7eq7asaq1da94&idp=45
1/11
24/10/2015
Olimpiadi di Problem Solving
X9
X10
Domanda numero 3 - C odice 2011-R EG-SUP03 - Live llo di difficoltà: 1.00
PREMESSA
Si chiamano diagrammi di Ferrer (di n caselle o di contenuto n) delle configurazioni di n caselle disposte in una o più righe orizzontali,
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 caselle della
prima riga, il secondo le caselle della seconda riga, e così via. Esempi sono i seguenti: sopra ogni diagramma è riportata la lista che
lo descrive.
2011_re g_s_03a_400
Si chiama tabella di Young un diagramma di Ferrer 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 si dice 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
una delle 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 in
maniera standard.
PROBLEMA
Si considerino i tre diagrammi descritti dalle seguenti liste
A) [4,3,1,1,1] in cui 6 è (fisso) nella terza casella della seconda riga;
B) [4,4,3,2] in cui 4 è (fisso) nella quarta casella della prima riga e 8 è (fisso) nella quarta casella della seconda riga;
C) [3,2,1] in cui 5 è (fisso) nell'ultima casella in basso.
Dire in quanti modi standard è possibile completare ciascun diagramma.
A
B
C
Domanda numero 4 - C odice 2011-R EG-SUP04 - Live llo di difficoltà: 1.00
PROBLEMA
Nella seguente tabella sono elencati alcuni avvenimenti storici; ogni avvenimento è contrassegnato da una sigla.
SIGLA
A
B
C
AVVENIMENTO
La nascita dello stato italiano
La seconda guerra di indipendenza
La terza guerra punica
http://www.olimpiadiproblemsolving.com/preview2_allenamento.php?4a7or2cp05jqp7eq7asaq1da94&idp=45
2/11
24/10/2015
D
E
F
G
H
Olimpiadi di Problem Solving
Gli affreschi della cappella degli Scrovegni
La nascita dell'impero romano
La nascita di Napoleone
L'apertura del canale di Suez
La nascita di Maometto
Associare queste sigle ai simboli X1, X2, ..., X8 nella tabella seguente in modo che gli avvenimenti si susseguano in ordine temporale
crescente: in X1 il più antico e via via in X8 il più recente.
X1
X2
X3
X4
X5
X6
X7
X8
Domanda numero 5 - C odice 2011-R EG-SUP05 - Live llo di difficoltà: 1.00
PREMESSA
Sul fianco di una montagna esistono numerose sorgenti. L'acqua di una sorgente, che si suppone fluire in modo continuo e costante,
può scorrere a valle attraverso uno o più rigagnoli. Può avvenire che uno o più rigagnoli convergano in un punto in cui esiste una
sorgente; in tal caso, la loro acqua si aggiunge a quella fornita dalla sorgente raggiunta. Questa situazione è descrivibile con un
reticolo di nodi (le sorgenti) collegati da archi (i rigagnoli). La situazione quindi è descritta da due tabelle:
s(<sorgente>,<litri d'acqua erogata al minuto>),
che specifica la quantità d'acqua che sgorga da ogni sorgente (che è un nodo del reticolo),
r (<sorgente1>,<sorgente2>),
che specifica la presenza di un rigagnolo che porta acqua dalla sorgente1 alla sorgente2.
Se da una sorgente escono più rigagnoli, l'acqua si divide in parti uguali fra ciascuno di essi.
Nella situazione descritta dal seguente esempio (con radici in a e in b, vedi figura)
s(a,6), s(b,5), s(c,1), s(d,4), s(e,3), s(f,2),
r(a,c), r(a,d), r(b,d), r(c,e),r(d,e), r(d,f),
la quantità d'acqua che esce dai nodi c, e, f è riportata di seguito.
c
e
f
4
13
8
PROBLEMA
Un reticolo è descritto dalle seguenti due tabelle:
s(a,4), s(b,4), s(c,12), s(d,6), s(e,15), s(f,3), s(g,3), s(h,8), s(i,4), s(m,1), s(n,3), s(p,10), s(q,7);
r(a,m), r(i,m), r(g,m), r(h,m), r(h,f), r(q,a), r(q,i), r(b,i), r(n,i), r(n,g), r(d,g), r(d,h), r(c,n), r(e,q), r(p,n), r(e,b), r(c,d), r(e,n).
http://www.olimpiadiproblemsolving.com/preview2_allenamento.php?4a7or2cp05jqp7eq7asaq1da94&idp=45
3/11
24/10/2015
Olimpiadi di Problem Solving
Determinare la quantità di acqua che esce dai nodi f, m.
f
m
Domanda numero 6 - C odice 2011-R EG-SUP06 - Live llo di difficoltà: 1.00
PREMESSA
Si devono consegnare le pizze alle abitazioni poste ai numeri dispari di una stessa via. Per rispettare i tempi delle prenotazioni, le
pizze devono essere consegnate seguendo le istruzioni scritte usando un codice che specifica come spostarsi avanti (per esempio
(a,2), per muoversi di due posti) e indietro (per esempio (i,5), per muoversi di 5 posti) lungo la via a partire da un punto specificato. Un
esempio di consegna di 4 pizze a partire dalla casa al numero 1: se le istruzioni fossero descritte dalla lista [(a,2),(a,1),(i,2)], le
consegne seguirebbero l'ordine indicato nella lista [1,5,7,3] che indica, appunto, i numeri civici successivi a cui avvengono le
consegne. A partire dalla casa al numero 3, con le seguenti istruzioni [(a,1),(i,2),(a,4)], le consegne seguirebbero il seguente ordine
[3,5,1,9].
PROBLEMA
1) Si devono consegnare 9 pizze ad abitazioni che corrispondono ai numeri civici dispari di una via. Le istruzioni per la consegna, a
partire dalla abitazione al numero 7, sono le seguenti:
[(a,1),(a,2),(a,4),(i,2),(i,3),(a,4),(a,6),(i,1)]. Trovare la lista L1 che contiene i numeri civici delle abitazioni disposti secondo l'ordine
di consegna delle pizze.
2) Si devono consegnare 11 pizze ad alcune abitazioni che corrispondono ai numeri civici dispari di una via. Le istruzioni per la
consegna, a partire dalla abitazione al numero 11, sono le seguenti: [(i,5),(a,3),(a,3),(a,4),(i,2),(i,1),(a,6),(a,4),(i,1),(i,2)].Trovare la
lista L2 che contiene i numeri civici delle abitazioni disposti secondo l'ordine di consegna delle pizze.
L1
[
]
L2
[
]
Domanda numero 7 - C odice 2011-R EG-SUP07 - Live llo di difficoltà: 1.00
PREMESSA
In un foglio a quadretti è disegnato un rettangolo di 14 quadretti in orizzontale e 6 in verticale (vedi figura).
Ogni casella può essere individuata da due numeri (interi); per esempio la casella contenente "P" è individuata da essere nella sesta
colonna (da sinistra) e nella terza riga (dal basso): brevemente si dice che ha coordinate (6,3). Le coordinate della casella
contenente "S" sono (10,6) e di quella contenente la freccia sono (1,1).
La freccia, che in figura è nella casella (1,1), può essere pensata come una piccola tartaruga, in questo caso voltata verso destra; la
tartaruga può eseguire tre tipi di comandi:
girarsi di 90 gradi in senso orario: comando o;
girarsi di 90 gradi in senso antiorario: comando a;
avanzare di una casella (nel senso della freccia!): comando f.
Questi comandi possono essere concatenati in sequenze in modo da permettere alla "tartaruga" di compiere vari percorsi; per
esempio la lista [f,f,f,f,f,a,f,f] fa spostare la tartaruga dalla posizione e orientamento iniziali mostrati in figura fino alla casella "P";
risultato analogo si ottiene con la lista [a,f,f,o,f,f,f,f,f]. Tuttavia, nel primo caso l'orientamento finale della tartaruga è verso l'alto,
mentre nel secondo caso l'orientamento finale è verso destra.
PROBLEMA
In un rettangolo 14x9, la tartaruga è nella casella (6,6) ed è orientata verso sinistra (ovest). La tartaruga esegue un percorso diviso in
tre tappe. Trovare l'ascissa X, l'ordinata Y e l'orientamento D in cui si troverà la tartaruga dopo aver effettuato ciascuna tappa.
L'orientamento D è descritto con: n, s, e, o rispettivamente per alto (nord), basso (sud), destra (est), sinistra (ovest). Le descrizioni
http://www.olimpiadiproblemsolving.com/preview2_allenamento.php?4a7or2cp05jqp7eq7asaq1da94&idp=45
4/11
24/10/2015
Olimpiadi di Problem Solving
dei percorsi delle tre tappe sono le seguenti (ogni tappa successiva alla prima inizia con l'orientamento fissato al termine della tappa
precedente):
Prima tappa: [f,f,o,o,f,a,a,f,a,f]; coordinate d'arrivo X1 e Y1, direzione D1.
Seconda tappa: [o,o,f,f,f,f,o,f,f,f]; coordinate d'arrivo X2 e Y2, direzione D2.
Terza tappa: [o,f,f,f,f,o,f,f,o,f]; coordinate d'arrivo X3 e Y3, direzione D3.
Al termine del percorso, la tartaruga deve rientrare nella casella da cui è partita e riprendere l'orientamento iniziale: qual è il numero
minimo N di ordini da impartirle per farla rientrare nella posizione e orientamento iniziali?
X1
Y1
D1
X2
Y2
D2
X3
Y3
D3
N
Domanda numero 8 - C odice 2011-R EG-SUP08 - Live llo di difficoltà: 1.00
PREMESSA
Un fiume scorre tra due rive indicate con D (per destra) e S (per sinistra). Sulla riva D ci sono delle persone, adulti e ragazzi, e vi è
attraccata una piccola barca; il fiume non è guadabile e non può essere attraversato a nuoto; la barca può contenere soltanto un
adulto oppure uno o due ragazzi: comunque tutte le persone sono capaci di manovrarla e passare da una riva all'altra. Si chiama
mossa un percorso della barca (ovviamente con almeno una persona a bordo) da un riva (D o S) all'altra (rispettivamente S o D).
PROBLEMA
Sulla riva D ci sono quattro adulti e due ragazzi; qual è il numero minimo N di mosse occorrenti perché passino tutti all'al​
tra sponda e
la barca rimanga attraccata alla riva S?
N
Domanda numero 9 - C odice 2011-R EG-SUP09 - Live llo di difficoltà: 1.00
PREMESSA
Date due liste (per esempio L1= [r,i,s,o,t,t,o] e L2= [p,r,e,s,t,o]) si definisce distanza di L1 da L2 il numero minimo di "mosse" da
eseguire su L1 per renderla uguale a L2. Una mossa è una delle seguenti tre operazioni:
a) sostituzione di un carattere di L1 con altro carattere,
b) inserimento di un nuovo carattere in L1,
c) cancellazione di un carattere di L1.
Ad esempio, L1 può essere trasformata in L2 con 13 mosse. Con 7 cancellazioni L1 diventa uguale alla lista vuota [ ]. Con cinque
inserimenti successivi (dei 6 caratteri: p, r, e, s, t, o) la lista vuota diventa uguale a L2. In realtà L1 può trasformarsi in L2 con solo 4
mosse: la distanza di L1 da L2 è quindi 4 (le mosse sono [r,i,s,o,t,t,o] ® [r,i,s,o,t,o] ® [r,i,s,t,o] ® [r,e,s,t,o] ® [p,r,e,s,t,o]).
PROBLEMA
Trovare la distanza D1 tra le liste L1 = [v,i,n,c,e,r,e] e L2 = [d,i,p,i,n,g,e,r,e].
Trovare la distanza D2 tra le liste M1 = [e,l,o,g,i,o] e M2 = [p,r,o,l,o,g,o].
Trovare la distanza D3 tra le liste N1 = [p,r,o,m,e,s,s,a] e N2 = [p,e,r,l,o,m,e,n,o].
Trovare la distanza D4 tra le liste O1 = [c,o,m,p,e,t,e,n,t,e]) e O2 = [p,r,o,p,e,l,l,e,n,t,e].
D1
D2
D3
D4
http://www.olimpiadiproblemsolving.com/preview2_allenamento.php?4a7or2cp05jqp7eq7asaq1da94&idp=45
5/11
24/10/2015
Olimpiadi di Problem Solving
Domanda numero 10 - C odice 2011-R EG-SUP10 - Live llo di difficoltà: 1.00
PREMESSA
Alcuni ragazzi, per esempio 9, indicati con le prime lettere dell'alfabeto (A, B, C, D, E, F, G, H, I), organizzano riunioni seduti attorno
a un tavolo rotondo; nella prima riunione A è seduto nel posto numero 1, B nel 2, C nel 3 e così di seguito ordinatamente, H nel posto
8 e I nel 9; quindi, in questa prima riunione, A è seduto fra B e I. Per le riunioni successive, i ragazzi decidono di cambiare di posto
usando la regola descritta dalle coppie presenti in questa lista:
[(1,4),(2,5),(3,7),(4,8),(5,2),(6,9),(7,3),(8,6),(9,1)]
Chi in una riunione occupa il posto indicato dal primo numero della coppia, nella seduta successiva andrà nel posto corrispondente al
secondo numero della coppia. Esempio: A che nella prima riunione è al posto 1, nella seconda andrà nel posto 4, nella terza al posto
8, nella quarta al posto 6. Le posizioni successive di C sono indicate dalla seguente sequenza: 3, 7, 3, 7, 3, 7 e così via; e le
posizioni successive di H sono: 8, 6, 9, 1, 4, 8, 6, 9, 1, 4 e così via.
PROBLEMA
I ragazzi che partecipano alle riunioni sono 11 (A, B, C, D, E, F, G, H, I, J, K) e iniziano seduti nelle posizioni da 1 a 11 in ordine
alfabetico (A in 1, B in 2 e così via, K in 11).
Data la seguente regola che definisce le modalità di scambio dei posti
[(1,5),(2,7),(3,8),(4,2),(5,3),(6,9),(7,1),(8,10),(9,4),(10,11),(11,6)]
trovare le posizioni Pa, Pb, Pc occupate rispettivamente da A, B e C nella undicesima seduta,
le posizioni Pd, Pe e Pf occupate rispettivamente da D, E e F nella quindicesima seduta,
le posizioni Pg, Ph, Pi occupate rispettivamente da G, H e I nella ventesima seduta
e le posizioni Pj e Pk occupate rispettivamente da J e K nella trentesima seduta.
Pa
Pb
Pc
Pd
Pe
Pf
Pg
Ph
Pi
Pj
Pk
Domanda numero 11 - C odice 2011-R EG-SUP11 - Live llo di difficoltà: 1.00
PREMESSA
Siano date due liste di numeri pari Lm, detta lista dei minori, e LM detta lista dei maggiori, come mostrato nel seguente esempio:
Lm = [12,12,14,18,22,24],
LM = [16,20,26,28,28,30,30,30,32].
Un separatore per queste due liste è un numero dispari per il quale si fa l'ipotesi che sia maggiore di tutti i numeri della lista Lm e
minore di tutti quelli della lista LM. Poiché alcuni numeri della prima lista possono essere maggiori di alcuni numeri della seconda (si
veda l'esempio), ad ogni separatore ipotizzato S viene associato un errore E dato dal numero di elementi di Lm maggiori di S più il
numero di elementi di LM minori di S. Con riferimento alle due liste sopra viste, nella tabella seguente sono riportati alcuni esempi di
separatori e dei rispettivi errori.
Separatore
Errore
17
4
19
3
21
4
23
3
25
2
27
3
29
5
Si dice separatore ottimale il numero dispari cui corrisponde l'errore minimo. In questo caso il se​
paratore ottimale è il numero 25, in
grassetto nella tabella).
PROBLEMA
Date le seguenti tre coppie di liste
L1m =[30, 28, 24, 28, 28, 20, 30, 28, 2, 2, 2, 10, 8, 22, 30, 22, 8, 4, 24, 22, 18, 28, 12, 26, 24]
L1M =[34, 36, 16, 18, 26, 26, 36, 22, 34, 36, 12, 40, 34, 12, 26, 38, 16, 24, 30, 12, 12, 20, 28, 26, 20, 24, 24, 24, 30, 12]
L2m=[22, 2, 26, 28, 10, 28, 2, 26, 26, 4, 16, 22, 26, 26, 2, 6, 8, 14, 30, 14, 20, 30, 14, 22, 18]
http://www.olimpiadiproblemsolving.com/preview2_allenamento.php?4a7or2cp05jqp7eq7asaq1da94&idp=45
6/11
24/10/2015
Olimpiadi di Problem Solving
L2M=[36, 36, 18, 28, 40, 14, 18, 38, 34, 12, 36, 20, 40, 14, 12, 40, 32, 38, 22, 18, 28, 32, 26, 12, 28]
L3m=[26, 4, 4, 2, 24, 14, 30, 10, 20, 6, 6, 24, 4, 24, 26, 12, 12, 2, 26, 12]
L3M=[40, 16, 24, 20, 20, 20, 34, 12, 30, 38, 12, 20, 40, 40, 40, 38, 30, 18, 40, 20]
trovare i corrispondenti separatori ottimali S1, S2, S3 e i relativi errori E1, E2, E3.
S1
S2
S3
E1
E2
E3
Domanda numero 12 - C odice 2011-R EG-SUP12 - Live llo di difficoltà: 1.00
PROBLEMA
The land of Fantasia is centered upon a large circular lake. Around this lake is a circular highway, with seven cities placed along the
highway. The distances between the cities are as follows:
Distance
City a
City b
City c
City d
City e
City f
Cyty g
City a
39
13
11
27
33
24
City b
39
27
28
13
6
15
City c
13
27
24
14
33
37
City d
11
28
24
38
22
13
City e
27
13
14
38
19
28
City f
33
6
33
22
19
City g
24
15
37
13
28
9
9
Note that there are always two different ways of travelling from one city to another (corresponding to the two different directions around
the lake); the table above lists the shorter distance in each case.
You are travelling along the highway in a constant direction around the lake. In which order might you travel past the seven cities?
Write the list L = [c,e,...] of the cities, starting from c direction e.
L
[
]
Domanda numero 13 - C odice 2011-R EG-SUP13 - Live llo di difficoltà: 1.00
PROBLEMA
Alcuni ragazzi decidono di costruire un ipertesto multimediale sugli avvenimenti storici significativi della loro regione. Per organizzare
il progetto, dividono il lavoro in singole attività e assegnano ogni attività a un gruppo di loro.
La tabella che segue descrive le attività (indicate rispettivamente con le sigle a1, a2, a3, ...), riportando per ciascuna di esse il
numero di ragazzi assegnato e il numero di giorni per completarla.
attività
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
ragazzi
6
4
3
6
4
4
5
3
8
6
7
3
8
giorni
1
3
2
2
3
2
3
3
1
2
1
1
1
Le precedenze fra le attività sono descritte da termini del tipo p(<precedente>,<seguente>); ogni termine esprime il fatto che l'attività
associata alla sigla di destra può iniziare solo quando l'attività associata alla sigla a sinistra è terminata. L'attività che non ha
precedenti è la prima, quella che non ha seguenti è l'ultima. In questo caso le precedenze sono:
p(a1,a2), p(a1,a3), p(a1,a4), p(a2,a5), p(a3,a6), p(a4,a7), p(a5,a7), p(a6,a8), p(a6,a9),
http://www.olimpiadiproblemsolving.com/preview2_allenamento.php?4a7or2cp05jqp7eq7asaq1da94&idp=45
7/11
24/10/2015
Olimpiadi di Problem Solving
p(a7,a9), p(a8,a10), p(a9,a10), p(a9,a11), p(a10,a11), p(a10,a12), p(a11,a13), p(a12,a13).
Una attività, se ha più precedenti, può iniziare solo quando tutte le precedenti sono terminate.
Trovare quanti giorni N1 sono necessari per completare il progetto, tenuto presente che alcune attività possono essere svolte in
parallelo e che ogni attività deve iniziare prima possibile (nel rispetto delle precedenze).
Trovare inoltre:
il numero N2 che individua il giorno in cui lavorano 10 ragazzi,
il numero N3 di ragazzi che lavorano il giorno 12,
il numero complessivo N4 di giorni in cui lavorano 8 ragazzi.
N1
N2
N3
N4
Domanda numero 14 - C odice 2011-R EG-SUP14 - Live llo di difficoltà: 1.00
PROBLEMA
La lista seguente contiene in ordine alfabetico le sigle automobilistiche di alcuni capoluoghi di provincia italiani.
[an,ao,ar,ap,at,ba,bg,bz,bs,cl,cb,cz,co,cs,cr,kr,cn,fe,fi,fg,fo,ge,go,sp,aq,
le,lc,li,lo,lu,ms,mt,mi,mo,na,nu,or,pd,pa,pv,pg,pe,pi,pt,pz,po,rg,re,ri,rn,roma,
ss,sv,si,sr,so,ta,te,tr,to,tp,tn,ts,va,ve,vv].
Facendo riferimento solo alle città rappresentate in questa lista, trovare la lista L1 delle sigle automobilistiche delle città che si
trovano a nord ovest di Palermo e a sud est di Lucca e la lista L2 di quelle che si trovano a sud est di Rimini e a nord ovest di Bari.
Elencare le sigle in modo da rispettare l'ordine crescente di latitudine delle città.
L1
[
]
L2
[
]
Domanda numero 15 - C odice 2011-R EG-SUP15 - Live llo di difficoltà: 1.00
PREMESSA
Si ricorda che un grafo (stradale) è costituito da nodi (possono essere pensati come città) e tratti che li congiungono (possono essere
pensati come strade); il termine a(<nodo1>,<nodo2>,<distanza>) descrive un tratto stradale che unisce nodo1 e nodo2, con la
indicazione della relativa distanza (per esempio in chilometri). Un percorso tra due nodi di questo grafo viene descritto con la lista dei
nodi attraversati, ordinati dal nodo di partenza al nodo di arrivo; la sua lunghezza è la somma delle distanze dei tratti che uniscono
due nodi successivi (nella lista).
PROBLEMA
Sia dato il grafo stradale descritto dai seguenti tratti:
a(n5,n1,4)
a(n5,n3,6)
a(n3,n8,5)
a(n2,n8,6)
a(n4,n6,9)
a(n6,n7,5)
a(n1,n7,7).
a(n3,n7,3)
a(n2,n6,5)
a(n7,n5,2)
a(n4,n7,7)
a(n1,n4,6)
Disegnare il grafo (in modo che gli archi non si incrocino) e trovare:
1) il numero N1 di percorsi diversi (che non passino più di una volta per lo stesso nodo) fra i nodi n1 e n8 che abbiano una lunghezza
minore di 20;
2) il numero N2 di percorsi diversi (che non passino più di una volta per lo stesso nodo) fra i nodi n1 e n8 che abbiano una lunghezza
superiore a 30;
N1
N2
Domanda numero 16 - C odice 2011-R EG-SUP16 - Live llo di difficoltà: 1.00
Nelle lezioni di educazione alimentare, i ragazzi hanno classificato alcuni alimenti in relazione al contenuto proteico e al loro costo. I
risultati di questa classificazione sono descritti da una tabella avente la dichiarazione:
tabx(<sigla dell'alimento>,<tipo>, <contenuto proteico>, <costo>).
Il tipo si riferisce all'origine dell'alimento: a per vegetali, b per latticini, c per carni.
http://www.olimpiadiproblemsolving.com/preview2_allenamento.php?4a7or2cp05jqp7eq7asaq1da94&idp=45
8/11
24/10/2015
Olimpiadi di Problem Solving
Il contenuto della tabella riporta i dati relativi agli alimenti ed è il seguente:
tabx(m1,a,190,148).
tabx(m4,c,173,120).
tabx(m7,b,192,138).
tabx(m10,a,192,140).
tabx(m13,b,185,141).
tabx(m16,c,177,135).
tabx(m19,a,185,140).
tabx(m22,a,196,142).
tabx(m2,a,166,142).
tabx(m5,a,196,150).
tabx(m8,c,197,151).
tabx(m11,c,188,149).
tabx(m14,c,182,132).
tabx(m17,c,177,140).
tabx(m20,b,195,140).
tabx(m23,b,180,140).
tabx(m3,b,180,131).
tabx(m6,b,199,150).
tabx(m9,b,199,149).
tabx(m12,a,179,130).
tabx(m15,c,199,148).
tabx(m18,c,182,155).
tabx(m21,c,184,198).
tabx(m24,c,198,140).
Trovare le risposte ai seguenti quesiti; se la risposta è una lista di sigle, riportare le sigle in ordine crescente; per le sigle si ha il
seguente ordine m1<m2< ... .
N.B. Le liste sono scritte tra parentesi quadre; gli elementi della lista si susseguono separati da virgole senza spazi.
Con i dati sopra descritti si vogliono calcolare diete senza mescolare tipi diversi; calcolare il numero Na, Nb, Nc di diete che si
possono costruire, ciascuna con quattro elementi omogenei rispettivamente di tipo a, di tipo b e di tipo c; le diete devono avere un
costo non superiore a 560 e un valore proteico maggiore di 755. Tra queste diete, trovare la lista L delle sigle degli elementi che
compongono la dieta di costo minimo.
Na
Nb
Nc
L
[
]
Domanda numero 17 - C odice 2011-R EG-SUP17 - Live llo di difficoltà: 1.00
PREMESSA
Una nota catena di fast food vende bocconcini di pollo (fritto) in scatole da 6, 9 o 20 pezzi. La Mad Chicken & Co. vuole entrare in
questo mercato; una indagine infatti ha rilevato che molti clienti sono insoddisfatti perché non riescono ad acquistare il numero esatto
di bocconcini che vogliono mangiare, per esempio 5 o 23 (ma devono acquistarne di più o di meno). Una ricerca su Internet ha poi
svelato che il numero più grande di bocconcini che attualmente non si può comprare (esattamente) è 43.
PROBLEMA
La Mad Chicken & Co. decide di mettere in vendita solo scatole da 5 e da 9 pezzi. Qual è il numero più grande, N, di bocconcini che
non si può comprare (esattamente) presso la nuova catena?
N
Domanda numero 18 - C odice 2011-R EG-SUP18 - Live llo di difficoltà: 1.00
PREMESSA
Il (semplice!) metodo crittografico usato da Giulio Cesare consiste nel sostituire ogni lettera presente nel messaggio originale (detto
in chiaro) con quella che, nell'ordine alfabetico, segue a una distanza predefinita detta chiave (di Cesare), ottenendo così un
messaggio crittografato (detto in scuro). Per esempio, volendo crittografare un messaggio con chiave 3, si deve usare la
traslitterazione definita dalla seguente tabella:
in cui la prima riga contiene le lettere dell'alfabeto nell'ordine standard e la seconda riga inizia con la lettera individuata dalla chiave
(poiché, nell'esempio, la chiave è 3 il nuovo ordinamento inizia dalla terza lettera dopo la a). Se la chiave è 0 oppure 26, il messaggio
in scuro coincide col messaggio in chiaro. Si assume sempre che, se la chiave è indicata con K, 0 < K < 26. La stringa (lista)
[r,o,m,a] crittografata con chiave K = 5 diventa [w,t,r,f]. Dato un messaggio crittografato si può decifrarlo, cioè ricostruire quello in
chiaro; per esempio data la stringa in scuro [d,q,n,q,i,p,c], sapendo che rappresenta una città capoluogo di una regione italiana, si
verifica che è di 7 lettere e che la seconda e la quarta sono uguali; la stringa originale non può che essere una fra [v,e,n,e,z,i,a] e
[b,o,l,o,g,n,a]. Con qualche tentativo si può verificare che si tratta della versione crittografata con chiave 2 della stringa [b,o,l,o,g,n,a].
N.B. Per crittografare, la chiave si usa per avanzare rispetto all'ordine alfabetico, per decifrare, la chiave si usa per retrocedere.
PROBLEMA
http://www.olimpiadiproblemsolving.com/preview2_allenamento.php?4a7or2cp05jqp7eq7asaq1da94&idp=45
9/11
24/10/2015
Olimpiadi di Problem Solving
Sono date alcune liste corrispondenti a nomi crittografati di fiumi, sistemi montuosi, città o altri elementi geografici dell'E​
uropa; si
devono trovare i nomi in chiaro e le rispettive chiavi usate.
NB. I nomi sono crittografati con due chiavi, una (CHIAVE1) per le lettere in posizione dispari e una (CHIAVE2) per quelle in posizione
pari.
NOME CRITTOGRAFATO
[o, v, q, k, r, u]
[
NOME IN CHIARO
]
CHIAVE1
[n, y, w, f]
[
]
[r, y, g, n, p, x, x]
[
]
[n, q, i, z, v]
[
]
[p, f, j, o, j, w, z, f, r, g, r, c]
[
]
CHIAVE2
Domanda numero 19 - C odice 2011-R EG-SUP19 - Live llo di difficoltà: 1.00
PREMESSA
Con il termine
regola(<sigla>,<lista degli antecedenti>,<conseguente>)
si può descrive una regola che consente di dedurre (o calcolare) il conseguente conoscendo tutti gli elementi contenuti nella lista
degli antecedenti; ogni regola è identificata in modo univoco da una sigla. Per esempio, dato il seguente insieme di regole:
regola(1,[c1,c2],i)
regola(4,[h,p2],c2)
regola(7,[p1,p2],i)
regola(2,[i,h],a)
regola(5,[c1,c2],a)
regola(8,[c1,i],c2)
regola(3,[h,p1],c1)
regola(6,[p1,p2],h)
regola(9,[i,a],h)
si osserva che, conoscendo gli elementi contenuti nella lista [p1,p2], è possibile, per esempio, dedurre o calcolare (direttamente) h
con la regola 6 e i con la regola 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 o calcolare c1
da [p1,p2]; la lista contiene infatti l'indicazione delle regole che devono essere applicate. Per esempio, la lista [6,3,4,5] rappresenta il
procedimento per calcolare a da [p1,p2].
PROBLEMA
Sia dato il seguente insieme di regole:
regola(1,[c1,c2],i).
regola(4,[h,p2],c2).
regola(7,[p1,p2],i).
regola(10,[h,c1],p1).
regola(13,[p1,h],p2).
regola(16,[a,h],i).
regola(19,[c2,a],c1).
regola(22,[p1,c1],i).
regola(25,[p2,c2],i).
regola(2,[i,h],a).
regola(3,[h,p1],c1).
regola(5,[c1,c2],a).
regola(6,[p1,p2],h).
regola(8,[c1,i],c2).
regola(9,[i,a],h).
regola(11,[h,c2],p2).
regola(12,[c1,a],c2).
regola(14,[p1,i],p2).
regola(15,[c2,i],c1).
regola(17,[p1,c1],h). regola(18,[p2,c2],h).
regola(20,[p2,h],p1). regola(21,[p2,i],p1).
regola(23,[p1,i],c1).
regola(24,[c1,i],p1).
regola(26,[p2,i],c2).
regola(27,[c2,i],p2).
Trovare il procedimento che richiede il maggior numero di regole (senza cicli o regole banalmente ripetute o regole il cui risultato non
venga utilizzato) per dedurre "i" dai dati [p2,c2]. Descrivere questo procedimento con la lista L delle sigle delle regole elencate
nell'ordine di applicazione.
L
[
]
Domanda numero 20 - C odice 2011-R EG-SUP20 - Live llo di difficoltà: 1.00
PREMESSA
Allineati sul bordo di un lungo sentiero rettilineo si trovano dei recipienti cilindrici, aventi tutti la medesima altezza ma diametro
diverso. Camminando lungo il sentiero è possibile raccogliere alcuni di questi recipienti, col vincolo che è possibile raccoglierne uno
solo se o è il primo raccolto o ha un diametro minore di quello raccolto in precedenza; i recipienti devono infatti essere via via posti
uno nell'altro, quindi la sequenza delle misure dei diametri dei recipienti via via raccolti deve risultare decrescente. Se la lista dei
diametri dei recipienti disposti lungo il sentiero è la seguente
[5,4,1,5,9,8,6,2,5,3,2,4,1]
alcune possibilità di raccolta consentite dal vincolo imposto sono descritte dalle seguenti liste
1) [5,4,1]
2) [5,4,3,2,1]
3) [9,8,6,5,3,2,1]
http://www.olimpiadiproblemsolving.com/preview2_allenamento.php?4a7or2cp05jqp7eq7asaq1da94&idp=45
10/11
24/10/2015
Olimpiadi di Problem Solving
In questo esempio, la soluzione 3) è quella che consente di raccogliere il massimo numero di recipienti (si dice anche la più lunga
successione decrescente estraibile da quella data).
PROBLEMA
Data la seguente distribuzione dei diametri dei recipienti disposti lungo il sentiero:
[226,128,227,126,225,123,215,313,121,216,229,
126,216,115,214,225,121,124,327,230,123,126,225,224,122]
trovare il massimo numero N di recipienti che si possono raccogliere, col vincolo che la sequenza dei relativi diametri deve risultare
decrescente.
N
Stampa questa pagina
Torna alla gestione allenamenti
http://www.olimpiadiproblemsolving.com/preview2_allenamento.php?4a7or2cp05jqp7eq7asaq1da94&idp=45
11/11