John wishes to walk …

Olimpiadi di Problem Solving

John wishes to walk from corner A to corner B through streets as in the following street map.
A route from A to B is a combination only of northward segments and eastward segments; an example is shown in bold on the map ([N,E,E,N,N,N,E,E]).
Note that at any corner John has only two choices; actually he can neither go backward, nor increase the distance from destination.

How many routes are there from A to B available to John?

Numero di percorsi per raggiungere ciascun incrocio

 

Oppure, numero di anagrammi di lunghezza 8 con 4 lettere E e 4 lettere N

\frac{8!}{4!4!}=70

Categorie OPS

Pseudolinguaggio

LA METAFORA

In una cassettiera ci sono dei cassetti individuati dalle lettere A, B, C, D, E, F. In ciascun cassetto ci può essere un foglietto su cui è scritto un numero intero.

La scrittura

significa: “sommare i numeri scritti sui foglietti dei cassetti A e B, scrivere il risultato su un nuovo foglietto e inserire questo foglietto nel cassetto C, dopo aver eliminato il foglietto (eventualmente) presente in C”.

Se all’inizio nei foglietti di A e B sono scritti rispettivamente i numeri 12 e 7, a operazione eseguita in C si trova un foglietto su cui è scritto 19.

Così, la scrittura:

significa: “sommare i numeri scritti sui foglietti dei cassetti C e A, sottrarre alla somma il numero scritto sul foglietto del cassetto B, scrivere il risultato su un nuovo foglietto e inserire questo foglietto nel cassetto D dopo aver eliminato il foglietto (eventualmente) presente in D”.

N.B. Per brevità diciamo, ad esempio, “il numero contenuto in C” invece di “il numero scritto sul foglietto contenuto in C”.

L’ASPETTO FORMALE

Invece di parlare di cassetti e di numeri scritti su foglietti (come nell’esercizio precedente), si può ricorrere a un’altra descrizione, più astratta.

Le lettere maiuscole A, B, C, … sono chiamate “variabili” (invece di cassetti) e i numeri sui foglietti sono detti “valori” di quelle variabili.

La sequenza di calcoli dell’ESERCIZIO precedente può es-sere presentata come la procedura seguente.

Con la scrittura

si dice che esistono sei cassetti (detti appunto variabili) e che sui foglietti in ognuno dei cassetti può essere scritto (solo) un numero intero.

Con la scrittura “input” si assegnano dei valori a certe variabili (si scrivono dei numeri sui foglietti contenuti in certi cassetti).

Con la scrittura “output” si fa vedere il valore di certe variabili (si leggono i numeri sui foglietti contenuti in certi cassetti).

Se si esegue la procedura PROVA1 e in input alle variabili A, B, C vengono assegnati rispettivamente i valori 5, 8 e 3, in output, per le variabili D, E, F vengono resi visibili rispettivamente i valori 13, 6 e 10 che sono soluzione del problema precedente, di cui PROVA1 è la trascrizione formale.

N.B. Ogni riga della procedura si dice statement (o istruzione).

UN NUOVO ESEMPIO

Si ricordi che quando si assegna un nuovo valore a una variabile (cioè si inserisce un nuovo foglietto in un cassetto) l’eventuale valore in essa preesistente viene distrutto (cioè il vecchio foglietto viene buttato e non è più recuperabile).

Ricapitolando, con le lettere A, B, C, … (o in generale con nomi scritti con lettere maiuscole e numeri) si indicano, in una procedura, delle variabili che possono acquisire valori mediante

  • una istruzione (o statement) “input”,
  • una istruzione (o statement) di assegnazione.

Si consideri la procedura ESEMPIO seguente, brevemente commentata.

Se in input alle variabili A e B vengono assegnati rispettivamente i valori 5 e 9, in output vengono restituiti i valori 32, 14 e 18 rispettivamente per A, C1, D.

L’ALTERNATIVA “if”

Durante la svolgimento di calcoli in una procedura si può porre una “alternativa” decisa dal valore di un predicato: se il predicato è vero si fanno alcune cose, se è falso se ne fanno altre.

In una procedura, l’alternativa può essere descritta, per esempio, con la seguente struttura

Se per esempio il valore di A è 2 e quello di B è 5, dopo l’alternativa il valore in output di M è 5.

Naturalmente al posto di “A > B” si possono usare altri predicati, costruiti confrontando i valori di certe variabili: per esempio “A = B” oppure “A < B”.

Quando manca il ramo “else” (cioè quando occorre fare alcune cose se il predicato è vero, ma non si deve fare nulla se è falso), si può usare la forma abbreviata del costrutto “if” come nel seguente esempio (che ha lo stesso significato del precedente):

LA RIPETIZIONE “for”

In una procedura si può prevedere di eseguire un insieme di operazioni (detto ciclo) un certo numero di volte; nell’esempio che segue il ciclo è fatto di due operazioni che vengono ripetute 4 volte:

I valori di output sono: per A 10 (la somma dei 4 valori di K) e per B 30 (la somma dei quadrati dei valori di K).

LA RIPETIZIONE “while”

La ripetizione di un gruppo di azioni può essere comandata non solo con la struttura “for” già vista, ma anche con la struttura “while”, illustrata dal seguente esempio.

Se il predicato A < B è vero, il ciclo viene ripetuto; quando diventa falso si passa alla esecuzione della istruzione successiva a “endwhile”.

In questo caso il valore di B rimane fisso a 10, mentre quello di A cambia dopo ogni iterazione assumendo i seguenti valori: 1, 5, 14.

Dopo la terza iterazione il valore di A non è più minore di quello di B e il ciclo si arresta: in output si ha quindi 14.

VARIABILI REALI

Oltre a valori interi le variabili possono contenere valori razionali, cioè numeri “con la virgola”: in questo contesto, però, si userà sempre il “.” come separatore decimale. Le variabili di questo tipo si dicono “float”. Corrispondentemente alle variabili di tipo float si usano le costanti di tipo float: si scrivono col punto decimale seguito da almeno una cifra, come in

  • 5.45
  • 5.0
  • 45362.9877

Il seguente è un esempio di procedura che usa variabili float.

Si ricorda che le normali operazioni aritmetiche sono indicate con +, −, ×, / (talvolta con ÷).

Spesso è usato anche l’elevamento a potenza, col simbolo ^.
Per esempio 2^3 = 8; A^B: se A ha valore 2 e B ha valore 3, il risultato dell’espressione è 8; se A ha valore 2.0 e B ha valore 3, il risultato dell’espressione è 8.0.

VARIABILI STRINGA

Oltre a valori numerici le variabili possono contenere stringhe, cioè sequenze di caratteri.

Le variabili di questo tipo si dicono “string”.

Corrispondentemente alle variabili di tipo string si usano le costanti di tipo string: si scrivono come sequenze di caratteri racchiuse tra apici; per esempio:

  • ‘alpha’
  • ‘Giuseppe’
  • ‘1200’
  • ‘’
  • ‘ ’

N.B. La (costante) stringa ‘1200’ non è il numero intero 1200: in particolare non si può sommare o sottrarre; la costante ‘’ è la stringa vuota; la costante ‘ ’ è la stringa spazio.

Consideriamo solo tre operazioni tra stringhe: la concatenazione, la estrazione e la determinazione della lunghezza.

I seguenti sono esempi di procedure che usano variabili string e intere.

 

Per il confronto delle stringhe sono disponibili i predicati: = e ≠.

Seguono esempi di problemi che riguardano lo pseudolinguaggio.

PROBLEMA1

Si consideri la seguente procedura PROVA1.

I valori in input sono: 4 per A, 2 per B; determinare i valori di output di A (8), B (60), C (6), D (8).

COMMENTO

Il problema si risolve eseguendo passo passo le operazioni indicate dalla procedura.

Si noti che i valori di certe variabili cambiano più volte: per esempio le variabili A e B acquisiscono un primo valore nello statement input e successivamente cambiano valore con le ultime due operazioni.

PROBLEMA 2

Si consideri la seguente procedura PROVA2.

I valori di input per A è 5 e per B sono rispettivamente: 9, 3, 7, 2, 8, 5, 1, 4, 4, 5.

Determinare i valori di output (M=25, N=15).

COMMENTO

Basta eseguire, passo a passo, le operazioni indicate: in N va la somma di tante volte il valore di A quante volte questo è più piccolo di (quello di) B (5 volte); in M va la somma di tante volte il valore di A quante volte questo è più piccolo di (quello di) B (3 volte).

PROBLEMA 3

Si consideri la seguente procedura (scritta in maniera sintatticamente scorretta: il simbolo X non è definito).

Trovare, tra le variabili dichiarate nella procedura, il nome da sostituire a X (C) per ottenere in output 21 per D se i valori in input sono 2 per A, 5 per B e 7 per C.

COMMENTO

Poiché A, B, C valgono rispettivamente 2, 5 e 7, occorre che il risultato di A+B+C+X cioè 2+5+7+X valga 21; questo richiede che il valore di X sia 7, cioè quello di C.

Un’altra maniera di procedere alla soluzione è di esaminare tutti i possibili casi: poiché sono dichiarate quattro variabili: A, B, C, D, allora si possono esaminare i risultati delle quattro possibili sostituzioni:

  1. l’espressione A+B+C+A vale 2+5+7+2 = 16
  2. l’espressione A+B+C+B vale 2+5+7+5 = 19
  3. l’espressione A+B+C+C vale 2+5+7+7 = 21
  4. l’espressione A+B+C+D vale 2+5+7+0 = 14

La soluzione segue immediatamente.

PROBLEMA 4

Si consideri la seguente procedura PROVA4.

I valori di input per A è: ‘9, a, b, 2, ac, 5, a, 4, 4a, 5b’.

Determinare il valore di output per C (4).

COMMENTO

Basta eseguire, passo a passo, le operazioni indicate: in C va il numero di volte che la lettera ‘a’ compare nella stringa data in input.

Si noti che |?A (il numero di caratteri di A) vale 31: naturalmente si contano anche le virgole e gli spazi.



ESERCIZIO 3

Si consideri la seguente procedura PROVA1.

Determinare il valore di output di K.

ESERCIZIO 4

Si consideri la seguente procedura PROVA2.

Trovare i valori di output.


Calcolare i 3 valori di P e i 3 di Z corrispondenti ai valori 3, 4 e 5 di N


Categorie OPS

In inglese

I questionari delle Olimpiadi del Problem Solving prevedono 1 o 2 quesiti con il testo in inglese.


In ordine alfabetico


A dozen of friends went to see a show.
After the show, some of them went into a restaurant for a midnight snack.
“Put it all on one bill,” they told the waiter.
The bill amounted to $60.00, and the men agreed to split it equally.
Then it was found out that two of them had slipped away without settling their debts, so that each of the remaining men was charged $2.50 more.
How many men were in the party that went to the restaurant?


Alice and Bob inherited a flock of sheep.
They sold the entire flock, receiving for each sheep the same number of dollars as there were sheep in the flock.
The money was given to them in $10 bills and some change.
They divided the bills by dealing them out alternatively; Alice complained that this was not fair because Bob received both the first and the last bills, thus getting $10 more.
To even things up, Bob gave Alice all the change, but Alice argued that it was still unfair.
Bob agreed to give her a cheque for the difference.
What was the value of the cheque?

Hint: try to figure out what the last digit of the amount paid could be, if this amount is a square and has the next-to-last digit odd (implied by an odd number of $10 bills).


Alice has many grandsons: among them there are Bob (who is a strong athlete) and Charlie (who is a little boy); being in charge of birthday parties, she noted that, in 2017, the ages of both will be equal to the sum of the digits in their birth years.
What years were Bob and Charlie born in?


It took 9 people 5 hours to unload 3 identical pickup trucks.
How many hours will it take 10 people to unload 4 trucks with the same load? How long if the load of each truck is increased by 1/6?


John wishes to walk from corner A to corner B through streets as in the following street map. A route from A to B is a combination only of northward segments and eastward segments; an example is shown in bold on the map ([N,E,E,N,N,N,E,E]).
Note that at any corner John has only two choices; actually he can neither go backward, nor increase the distance from destination.
How many routes are there from A to B available to John?


In a sequence of 10 terms, the first term is 1, the second term is x, and each term after the second is the sum of the previous two terms.
For example, if x = 11, the sequence would be 1; 11; 12; 23; 35; 58; 93; 151; 244; 395.
For some values of x, the number 463 appears somewhere in the sequence.
Let x be a positive integer; what is the sum of all the values of x for which 463 appears somewhere in the sequence?


Let be the set of natural numbers whose digits, in decimal representation, are chosen from {1,2,3} such that no digit is repeated.
Find the sum of all these numbers and put it in the box below.

Hint: note that, for example, the numbers 1, 12, 123 belong to.


Let’s call a positive integer “half-1” when exactly half of the integer numbers up to (written in decimal notation) contains the digit “1”, and half doesn’t.
It is easy to see that 2 is half-1; also 16 is half-1: indeed, consider the list of the all the integer numbers up to 16 [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]; eight numbers [1,10,11,12,13,14,15,16] contain “1” and eight [2,3,4,5,6,7,8,9] don’t.
Put in the box below the list of all half-1 numbers up to 200 (2 and 16 included).


One day two swimmers swim lengths in a pool that is 100 m long.
They start at the same time from the south end (S) of the pool, swim to the north end (N), swim back to S, then to N, and so on.
They each swim at a constant speed and each turns around instantly at both ends of the pool.
The swimmers are said to cross when they pass each other in the pool while swimming in opposite directions.
We also say that they cross if they arrive at an end (N or S) at the same time.
Suppose that two swimmers, Amanda and Bob, cross at S after Amanda has swum 200 m and Bob has swum 400 m.
How many times before this point did they cross?
A day later two different swimmers, Charles and David, cross at S after Charles has swum 400 m and David has swum 600 m.
How many times before this point did they cross?


Paula and Joan were selling oranges and, each day, they had an equal number of fruit but Joan had larger ones and sold them at the rate of two for a dollar, while Paula sold three of hers for a dollar.
Each lady expected to sell her fruits completely (with no oranges left).
Paula had to leave for a day and asked Joan to dispose of her stock.
Upon accepting the responsibility of disposing of her friend’s stock, Joan mixed them together and sold them off at the rate of five oranges for two dollars.
When Paula returned the next day, the oranges had all been disposed of (not one remained), but when they came to divide the money, they found that they were just seven dollars short with respect to the money they would have earned selling oranges separately.
Anyway, they divided the money equally, each taking one-half.
Find how much money Joan lost by the unfortunate partnership.
Enter your answer, as an integer number (of dollars), in the box below.

(Taking into consideration divisors and common multiples could be helpful.)


Three children agreed to share a bag of chocolate in proportion to their ages.
The sum of their ages was 23 years, and the bag contained 92 chocolates.
For every 4 chocolates Alice took, Bob took 2; for every 5 Alice took, Charlie took 4.
How many chocolates did each child take, and what are the respective ages?

Categorie OPS

Knapsack – P3

In un deposito di minerali esistono esemplari di vario peso e valore individuati da sigle di riconoscimento.

Ciascun minerale è descritto da un termine che contiene le seguenti informazioni:

minerale(<sigla del minerale>, <valore in euro>, <peso in Kg>).

Il deposito contiene i seguenti minerali:

  • minerale(m1,591,899)
  • minerale(m2,536,864)
  • minerale(m3,587,833)
  • minerale(m4,562,858)
  • minerale(m5,545,825)
  • minerale(m6,558,842)

Disponendo di un autocarro con portata massima di 1700 Kg, trovare la lista L1 delle sigle di 2 minerali diversi trasportabili con questo autocarro che consente di trasportare il massimo valore possibile.

Disponendo di un autocarro con portata massima di 1800 Kg, trovare la lista L2 delle sigle di 2 minerali diversi trasportabili con questo autocarro che consente di trasportare il massimo valore possibile.

N.B. Nelle liste, elencare le sigle in ordine crescente; per le sigle si ha il seguente ordine: m1<m2<… <m9.

DISCUSSIONE

Dati

Calcoli

Risposte

  1. L1 = [m3,m4], V1 = 1149
  2. L2 = [m1,m3], V2 = 1178
Categorie OPS

Regole e deduzioni – P3

Sono date le seguenti regole:

  • regola(1,[a],b)
  • regola(2,[p,q],v)
  • regola(3,[t],n)
  • regola(4,[v],z)
  • regola(5,[b,c],w)
  • regola(6,[a,b],c)
  • regola(7,[t,n],v)
  • regola(8,[t],v)

Trovare:

  1. la lista L1 che descrive il procedimento per dedurre w conoscendo a;
  2. la lista L2 che descrive il procedimento per dedurre z conoscendo p e q;

DISCUSSIONE

Osserva

       

Risposte

  1. L1 = [1,6,5]
  2. L2 = [2,4]
Categorie OPS