Author |
Topic: School classes (Read 1502 times) |
|
bd
Newbie
Posts: 2
|
 |
School classes
« on: Oct 11th, 2012, 1:33pm » |
 Quote  Modify
|
I do not have an answer to this riddle, any hint is appreciated.
In a school there are n students belonging to m distinct classes, numbered from 1 to m. A sensor placed at the entrance provides two things: the class (that is, the integer that identifies it) of a student who passes through the entrance and if the student is leaving or entering the building. Now, taking into account that in this school everyone is free to come and go as they please, you must describe an algorithm that, looking at the data provided by the sensor, is able at any time to answer the question: "Do all the students currently inside the school belong to the same class? ".
The algorithm can use only a constant number of variables and must answer in O(1) time. You can assume that each variable can contain O(log m + log n) bits of information.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: School classes
« Reply #1 on: Oct 11th, 2012, 10:46pm » |
Quote Modify
|
Do we know the sizes of each class?
There's a fairly simple way using m+1 variables, but the requirements seem to be a bit stricter than than.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
bd
Newbie
Posts: 2
|
|
Re: School classes
« Reply #2 on: Oct 11th, 2012, 11:19pm » |
Quote Modify
|
We don't know the size of each class.
The number of variables can not depend on m or n.
|
| « Last Edit: Oct 12th, 2012, 3:51am by bd » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print