Westpac数学题目请教

ghj

A teacher has a class of twelve students. She thinks it would be a nice idea if they change desks every day, so she has painted arrows on the floor from desk to desk. Each desk has one arrow going to it and another going from it. Each morning the students pick up their books and move to the desk indicated by the arrow. By choosing the arrows carefully, the teacher has arranged it so that the longest possible time will pass before all the students are back in their original desks at the same time. How many days is that?

一个老师班里有12名学生。她认为如果学生每一天换一下桌子将是一个不错的主意。因此她在地板上画箭头，从一张桌指向另一张桌。每张桌上有一个进的箭头和出的箭头。每天早晨，学生们拿起自己的书，并移到箭头所指到桌子。她通过仔细选择箭头，需要最长时间使所有的学生都回到原来的书桌同时。这个最长时间是多少天？

A：30
B：35
C：42
D：60
E：72

lily8989

72天

limit-2010

rabbit63

如果班上的人数改为100人.能总结出什么原则或规律?

limit-2010

rabbit63 发表于 2013-5-3 19:38
如果班上的人数改为100人.能总结出什么原则或规律?

100人可以最多有多少天， 比这个问题要算的情况多得多
这个问题是选择题， 知道天数， 算出需要多少人好像更简单
五个选项：
A：30
B：35
C：42
D：60
E：72

30=2*15=3*10=5*6  = 5*2*3
人数：17,13,11,10

35=5*7
人数：12

42=2*21=3*14=6*7=2*3*7
人数：23,17,13,12

60=2*30=3*20=4*15=5*12=6*10= 2^2*3*5
note： greatest common divisor gcd(2,30)=2, gcd(6,10)=2
60=3*20=4*15=5*12=2^2*3*5
人数：23,19,17,12

Observation : The number of people needed is minimised when the number of days is factorised as a product of prime powers
e.g.  if # days=365 = 5*73, we'll need at least 5+73=78 students to have a one year cycle
if #days=366=2*3*61, we'll need 2+3+61=66 students for a leap year cycle

In particular, for E=72=2^3 * 3^2
we'll need at least 2^3 + 3^2= 17 students

Therefore, option D is correct
-------------------------------------------------------------------------------------------------------

limit-2010

rabbit63 发表于 2013-5-3 19:38
如果班上的人数改为100人.能总结出什么原则或规律?

I would guess a rule of thumb is to find numbers N1,N2,...Nk such that all of these are satisfied:
i) gcd (x,y)=1, where x and y can be any numbers from  N1,N2,...Nk
ii) N1+N2+...+Nk= number of students
iii) the number k is maximised

But I don't really know any "nice" algorithm to actually compute it