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
澳洲中文论坛热点
- 新西兰总理：出世在新西兰的新纳粹Thomas Sewell是“挺蹩脚的人”，但那是澳洲的问题
- 新西兰总理拉克森称新纳粹Thomas Sewell是坏人，但是没对要求把他从澳大利亚遣返到诞生国去的呼吁置评。
- 撞穿学校栅栏害死十一岁男孩的司机不必坐牢
- 一位女司机撞穿学校栅栏、害死了11岁男孩，被罚2000元罚金、撤消驾照，不必坐牢。Jack Davey 的父母去了