Vrijeme: 02:06

Mentorski snovi | Dreams of five mentors #5

Stella u svome snu vidi 100 različito numeriranih ovaca (od 1 do 100) i planira ih pojesti.
Stella je dosta neodlučna kod izbora ovaca koje misli staviti na ražanj, no ipak je odlučila da će za svake dvije ovce numerirane s a i b u skupu ovaca koje će pojesti (nazovimo taj skup S) vrijediti ova dva pravila:
- postoji ovca iz skupa S čiji je broj c takva da je c relativno prost s a i b
- postoji ovca iz skupa S čiji broj d (d \neq a,b) nije relativno prost s a i b
Koliko će maksimalno ovaca Stella pojesti?
In her dream, Stella sees 100 distinctly numbered sheep (from 1 to 100) and plans to eat them.
Stella is quite indecisive about the choice of sheep she wants to put on the spit, but she still decided that for every two sheep numbered a and b in the set of sheep she will eat (let's call that set S) these two rules will apply :
- there is a sheep from the set S whose number c is such that c is relatively prime with a and b
- there is a sheep from the set S whose number d (d \neq a,b) is not relatively prime with a and b
How many sheep will Stella eat at most?