» Informatics

Solve this problem

The sniffer dog at the airport stops beside a trolley piled high with 60 suitcases. One of the suitcases contains contraband peanuts. The dog can tell whether peanuts are hidden in any one of the group of suitcases, but it gets tired if it has to do too much sniffing.

What is the smallest number of groups of suitcases it must sniff in order to isolate the suitcase with the peanuts? (2008 Australian Informatics Competition, Intermediate problem 2)

» See the solution

 

‘Mathematics provides a framework for dealing precisely with notions of “what is”. Computation provides a framework for dealing precisely with notions of “how to”.’ – Harold Abelson and Gerald Jay Sussman (Structure and Interpretation of Computer Programs 1985)

 
 

Informatics defined

Like never before, computational thinking is becoming part of our everyday world. Informatics is the study of the structure and behaviour of natural and artificial systems that generate, process, store, and communicate information. Across a broad range of fields from biomedical research to speed dating, and using the power and possibility of technology, informatics turns data into solutions that people can use every day.

Informatics is a rapidly growing discipline based in mathematics. Students studying informatics learn the basic algorithms, data structures and computational techniques that underlie information and communication, and demonstrate the learning through computer programming tasks. The Australian Curriculum has introduced achievement standards in the Digital Technologies Curriculum. By the conclusion of Year 6, ‘Students define problems in terms of data and functional requirements and design solutions by developing algorithms to address the problems’.

The Australian Mathematics Trust is a leader in providing informatics competitions, enrichment materials, training and support for talented Australian students and those selected for the International Olympiad in Informatics. Our programs and activities in informatics are conducted by the Australian Informatics Olympiad Committee, which is made up of notable academics, former Olympians and informatics professionals.

 

Computational and Algorithmic Thinking (CAT)

formerly Australian Informatics Competition (AIC)

Tuesday 22 March 2016

» 2015 CAT Results

» 2014 AIC Results

 

The Computational and Algorithmic Thinking (CAT) is a one-hour problem-solving competition which seeks to identify computer programming potential—something which students might not normally have an opportunity to demonstrate.

The CAT is not a programming competition and no programming experience is required. Results in the CAT often enable a talent to be discovered that is not always apparent or sought in normal classroom activities. Some questions test the ability to accurately perform procedures; others require logical thought, while the more challenging problems require the identification and application of algorithms.

The papers are: Upper Primary, Years 5–6; Junior, Years 7–8; Intermediate, Years 9–10; Senior, Years 11–12. Each paper includes six multiple-choice questions, followed by nine more challenging questions where an integer constitutes the solution to a problem.

 

Australian Informatics Olympiad

Thursday 1 September 2016

» Enter now

 

The Australian Informatics Olympiad (AIO) is a national computer programming competition held annually in early September. Students write short computer programs to solve three problems that range in difficulty. The competition does not test computer literacy or knowledge, but is focused on problem solving through programming skills.

There are two papers: Intermediate for students up to Year 10, Senior for students up to Year 12. The AIO is a suitable exercise for an IT class that has learnt some programming, or enthusiastic students who have taught themselves. Students will require some programming experience: in particular, they must be able to write code that can open, read and write to files; declare variables and arrays; use loops, conditional (if) statements and simple arithmetic operations.

 

AIOC Informatics Training Site

All Year

This site has a training hub with past AIO questions, forums, and detailed information about AIOC activities and invitational events. Submit your solutions to past questions here!

More information about the AIOC training, click on the link below.

» AIOC Training Site

 

Australian Informatics Olympiad Committee Invitational Program

All Year

Students who perform well in the open events, particularly the AIO, may be invited to participate in invitational events, which can eventually lead to Olympian selection. The first of these is the training school held in December each year. Further opportunities include individual mentoring, participation in the Australian Invitational Informatics Olympiad (AIIO) and the French Australian Regional Informatics Olympiad (FARIO) and, if selected, participation in the International Olympiad of Informatics (IOI). The IOI is the pinnacle of competition between students of pre-university level from different countries.

» More information on Olympiad Program | » Previous IOI Results | » Informatics Olympians

 

Solution

This is a classic binary search.

A binary search is similar to looking for a name in a telephone book. The first operation compares the middle element in the list with the target. This halves the portion of the list that the target could be in. Then the middle element of the half is compared with the target. This process is repeated until the target is found.

In this problem, the operation is ‘sniff a group of suitcases’. The dog is given a group of 30 suitcases to sniff, and whether or not it detects the peanuts, the suitcase containing them is now one of 30. It is then given a group of 15 of those suitcases, then 8, then 4, then 2, then 1, by which time the contraband suitcase has been identified.

So only 6 sniffs are required.

If you enjoyed this problem, visit our Shop for more past problems and solutions.