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
评论
72天
评论
评论
如果班上的人数改为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
-------------------------------------------------------------------------------------------------------
评论
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
澳洲中文论坛热点
- 悉尼部份城铁将封闭一年，华人区受影响！只能乘巴士（组图）
- 据《逐日电讯报》报导，从明年年中开始，因为从Bankstown和Sydenham的城铁将因Metro South West革新名目而
- 联邦政客们具有多少房产？
- 据本月早些时分报导，绿党副首领、参议员Mehreen Faruqi已获准在Port Macquarie联系其房产并建造三栋投资联