Title

Written Problem Task (30%)

MA2011 Discrete Mathematics for Computing

A step-by-step guide to Assessment Item 2

HOW TO USE THIS GUIDE

Work through it on your own, at your own pace. Use the arrow keys to move.

Press T at any time for the contents list, so you can jump back to a part you need again.

Always check LearnJCU for the official dates and the grade rubric. If anything here disagrees with the subject outline, the subject outline wins.

0.1

0.1 The whole assessment on one screen

What is it?	A short written report about one puzzle. You explore it, solve it, explain it, then make it harder.
How much is it worth?	30% — the same as two problem sheets put together.
How many problems?	You choose one. Forged Coin or Tower of Hanoi. Not both.
Can I work with others?	Yes — talk to as many people as you like. But the words you submit must be written by you, alone.
What is due first?	A proposal and draft outline, Tuesday of Week 9, 4pm. Compulsory, but not graded.
What is due at the end?	The full report, Wednesday 3 December, 11:59pm.

DO THIS NOW

Put both dates in your phone calendar before you go any further. It takes twenty seconds.

0.2

0.2 The one idea that matters most

READ THIS TWICE

You are not being marked on whether you get the right answer.
You are being marked on how you go looking for it.

This is different from most maths you have done. In this task:

A wrong attempt that you wrote down and explained is worth marks.
A correct answer with no explanation of how you found it is worth very little.
"I could not solve this part, but here is what I think happens and why" is worth marks.
Finishing with more questions than you started with is a good outcome, not a failure.

WHY

Both puzzles have been solved by other people already. Your lecturer knows the answers. What nobody else can hand in is a record of your thinking.

0.3

0.3 "Low floor, high ceiling"

Both problems are chosen because of two properties:

LOW FLOOR

You need almost no maths to start. You can begin today with a pen, paper, and some coins or coasters. Nothing is stopping you from starting.

HIGH CEILING

You can take them as far as you like. Logic, proof, induction, sets, counting, trees — all of it becomes useful once you go deep enough.

WHAT THIS MEANS FOR YOU

There is no "getting stuck at the start". If you feel stuck, you have simply not made the problem small enough yet. Section 2 shows you exactly how to do that.

Note: this guide is for the MA2011 version of the task. MA2211 students write up a theorem and its proof instead — ask your lecturer for that version.

Part 1 — Choosing your problem

Two puzzles. Pick one. Do not pick both.

1.1

1.1 Problem A — The Forged Coin

THE PUZZLE

You have 9 coins. One of them is fake.

The fake coin weighs a different amount from the others — but you do not know whether it is heavier or lighter.

You have a two-sided balance. It tells you: left side heavier, right side heavier, or perfectly equal.

Find the fake coin in at most 3 weighings.

PICK THIS IF

You like drawing branching diagrams and thinking about searching and strategy. This one connects naturally to decision trees and to how search algorithms work.

1.2

1.2 Problem B — The Tower of Hanoi

THE PUZZLE

Three poles. Three discs of different sizes, stacked on one pole — biggest at the bottom, smallest on top.

You may move one disc at a time onto another pole.

You may never put a bigger disc on top of a smaller one.

What is the smallest number of moves needed to shift the whole stack to another pole?

PICK THIS IF

You like counting, patterns, and formulas. This one connects naturally to recursion and induction — and it is easy to write code for.

1.3

1.3 How to choose between them

	Forged Coin	Tower of Hanoi
Main question	Which coin, and how do I always find it?	How many moves, and why can't I do better?
You will mostly draw	Branching trees of outcomes	Tables of numbers, and stacks
Maths it leads to	Trees, counting outcomes, strategy, probability	Recursion, induction, formulas, powers of 2
Easiest way to start	Grab 9 identical objects and shuffle them around	Use 3 coins of different sizes, or 3 stacked books
Coding it is	Harder, but interesting	Very easy (a few lines of recursion)

HOW TO DECIDE

Spend twenty minutes playing with both, physically, with real objects. Choose the one you found yourself still thinking about afterwards. Do not choose based on which looks easier — you will be living with it for five weeks.

1.Q

Check yourself — Part 1

Q1. You try a strategy for your puzzle and it does not work. What should you do with it?

Failed attempts are explicitly asked for in the task. They show your reasoning, and understanding why something fails usually points straight at the thing that works.

Q2. How many of the two problems should you hand in?

One only. Depth in a single problem earns far more than shallow coverage of two.

Part 2 — The method

Five steps that work on any puzzle of this kind

2.1

2.1 The five steps

Whichever puzzle you chose, you follow the same five steps. This is the shape of your whole project.

IMPORTANT

These five steps are also, roughly, the sections of your report. If you do the steps and write down what you did as you go, the report almost writes itself.

2.2

2.2 A practice puzzle (not yours)

To show you the five steps without spoiling your project, we will run them on a third, different puzzle.

THE PRACTICE PUZZLE

I am thinking of a whole number between 1 and 100. You may only ask me questions I can answer yes or no.

What is the smallest number of questions that always works?

Notice this puzzle has the same shape as yours: there is a hidden thing, you get limited information each step, and you want a strategy that always works in as few steps as possible.

TO BE CLEAR

Do not hand in this puzzle. It is a worked demonstration only. Watch the method, then apply that method to your own problem.

2.3

2.3 Step 1 — Play, and record your failures

Do not sit and think. Actually try things.

FIRST ATTEMPT (a bad one)

"Is it 1? Is it 2? Is it 3? ..."

This works, but in the worst case it takes 99 questions. Too slow. Why? Because each question only ever removes one number from the list.

SECOND ATTEMPT

"Is it less than 50?" Whatever the answer, roughly half the numbers are gone at once. That feels much better.

WHAT TO WRITE DOWN

Write the failed attempt and the reason it failed. "Each question only removes one option" is the sentence that led directly to the better idea. That sentence is worth marks.

2.4

2.4 Step 2 — Make it smaller, and get organised

100 is too big to think about. So do not think about 100. Ask the same question for tiny cases first, and put the answers in a table.

How many numbers	Questions needed
1	0
2	1
4	2
8	3
16	4

A picture like this is called a decision tree. It is the single most useful drawing in this whole assessment, because it shows every possible thing that could happen — so you can see that you have not missed a case.

2.5

2.5 Step 3 — Spot the pattern, and say it out loud

Look at the table again: 1, 2, 4, 8, 16 need 0, 1, 2, 3, 4 questions.

THE PATTERN

Each extra question doubles how many numbers I can handle. With $k$ questions I can cope with up to $2^k$ numbers.

Now turn that observation into a clear claim about every case, not just the ones in the table:

CONJECTURE

To find one hidden number out of $n$ possibilities, the smallest number of yes/no questions that always works is the smallest $k$ with $$2^k \ge n.$$

A conjecture is just a careful guess that you believe but have not proved yet. Writing "I conjecture that..." is completely normal and expected. It is not a weak thing to say.

2.6

2.6 Step 4 — Justify it (two halves)

A good justification almost always has two separate halves. Students usually only do the first and lose marks.

HALF 1 — I CAN DO IT

Describe a method and show it always works. "Always ask about the middle of the remaining list. That halves it every time, so after $k$ questions at most $n/2^k$ options remain."

HALF 2 — NOBODY CAN DO BETTER

Show fewer steps is impossible. "With $k$ questions there are only $2^k$ different answer-sequences. If $2^k < n$, two different numbers give the same sequence, so I cannot tell them apart."

THIS IS THE BIG ONE

Half 1 alone proves a method works. Only Half 2 proves it is the best possible. Your task explicitly asks you to discuss whether your solution is optimal — that means Half 2.

Ask yourself now: in your puzzle, how much information does one step give you? Coin weighings and disc moves do not behave like yes/no questions. What changes?

2.7

2.7 Step 5 — Stretch it

Now change one rule and ask the same question again. This is where the higher marks live.

Change one rule...	...and ask
What if I am allowed to lie once?	How many extra questions do I need?
What if answers can be yes / no / maybe?	Does the $2^k$ become $3^k$?
What if some numbers are more likely?	Should I still split down the middle?
What if questions cost money?	Do I now want the fewest questions on average, not in the worst case?

YOU DO NOT HAVE TO SOLVE THESE

Writing "if I changed X, I would expect Y to happen, because Z" earns marks even without a full answer — as long as your reasoning is sensible. Guessing with a reason is maths. Guessing with no reason is not.

2.8

2.8 Now do exactly this to your problem

Step	Practice puzzle	Forged Coin	Tower of Hanoi
1. Play	Ask silly questions, see what fails	Weigh coins at random, notice what you learn nothing from	Move discs by hand, get stuck, restart
2. Organise	Table for 1, 2, 4, 8, 16 numbers	Try 2 coins, then 3, then 4...	Try 1 disc, then 2, then 3...
3. Spot	$2^k \ge n$	How many coins can $k$ weighings handle?	How does the count for $n{+}1$ discs relate to $n$?
4. Justify	Method works + nobody can beat it	Draw the full decision tree; check no case is missed	Prove your formula by induction
5. Stretch	Lies, three answers, costs	More fakes? Different balance? Costly weighings?	More poles? Move two discs at once?

START HERE, TODAY

Do row 2 for your chosen problem. Just the smallest cases. That single table is the foundation of everything else you will write.

2.Q

Check yourself — Part 2

Q1. Your problem feels too hard. What is the correct first move?

Shrinking the problem is the core technique of this whole assessment. The small cases are where the pattern shows up.

Q2. You show your method always finds the answer in 5 steps. What is still missing?

Showing your method works proves 5 is enough. Optimality also needs you to rule out anything faster.

Q3. What is a conjecture?

It must be precise enough to be tested. "It's about doubling" is vague; "the answer is $2^n - 1$" is a conjecture.

Part 3 — Writing the report

What goes in each section, and what to actually type

3.1

3.1 The seven required sections

Your report must have these, in this order. Use these as your headings — do not invent your own structure.

1	Title and abstract — the problem in a nutshell, and what you found
2	Introduction — state the problem clearly, and preview the whole project
3	Strategy — first observations, small cases, attempts that failed, then your method or conjecture
4	Analysis — proofs where relevant, plus is it complete? is it optimal?
5	Extensions — how you would change the problem, and what you'd expect to happen
6	Conclusion — what you'd do with more time; what you still wonder about
7	References — anything you read, plus your AI declaration if you used AI

TIP

Open a document today and type these seven headings with nothing under them. Then fill them in as you go. You will never face a blank page.

3.2

3.2 Sections 1 and 2 — Title, abstract, introduction

ABSTRACT — about 4 to 6 sentences

One short paragraph: what the problem was, what you did, what you found, how far you got. Write this last, once you know what you actually found.

EXAMPLE SHAPE (fill in your own)

"This report investigates [problem]. I first solved the case of [small case] by hand, and used it to build a general method. I conjecture that [claim], and prove this using [method]. I also consider what happens when [changed rule], and argue that [expected outcome]."

INTRODUCTION — about half a page

State the problem so precisely that a stranger could not misunderstand it. Then tell the reader what is coming: "In Section 3 I..., in Section 4 I...". Add background reading here if you did any.

Being precise matters. "Find the fake coin" is vague. "Find which of 9 coins differs in weight, and whether it is heavy or light, using at most 3 weighings on a balance" is precise.

3.3

3.3 Section 3 — Strategy (your longest section)

This is the story of your thinking, in order. Include all four of these:

Assumptions	State them at the start. e.g. "I assume exactly one coin is fake." Later, check: did you actually use each one? Did you quietly add more?
Small cases	Your table from Step 2. Show the actual working for at least one small case, not just the answer.
Failed attempts	What you tried, and precisely why it did not work. This is asked for explicitly.
Your method	Written so someone else could follow it without asking you a single question. Numbered steps are ideal.

THE TEST FOR "IS MY METHOD CLEAR ENOUGH?"

Hand your written method to a classmate doing the other problem. If they can carry it out correctly without you speaking, it is clear. If they ask you anything, that answer belongs in the report.

3.4

3.4 Section 4 — Analysis: two words you must address

COMPLETE

Does it cover every possible case?

If any situation could arise where your method does not tell you what to do next, it is not complete. Say so honestly, and say which cases are missing.

How to show it: list every branch of your decision tree, or argue by cases, and show each one ends with an answer.

OPTIMAL

Could anyone possibly do better?

Not "is mine the best I could think of" — "is it impossible for anyone to beat it". These are very different claims.

How to show it: count how many different outcomes are even possible in $k$ steps, and show that is too few to distinguish all the cases.

IF YOU CANNOT PROVE OPTIMALITY

Say exactly that, and explain what you would need in order to prove it. Honest limitations are marked well. Claiming something you have not shown is marked badly.

3.5

3.5 Sections 5 and 6 — Extensions and conclusion

EXTENSIONS

Take your problem and change one parameter at a time. For each change, write:

what you changed,
what you expect to happen,
why you expect that — pointing back to something in your own analysis,
whether the problem got easier or harder, and how you can tell.

CONCLUSION

Summarise what you established. Then list the questions you would chase with more time. Ending with open questions is a strength — it is how real research papers end.

REFERENCES

List anything you read — Rosen, Wikipedia, articles, videos. Consistent format, and every source you list must actually be cited somewhere in your text.

3.6

3.6 Sentences you can steal

If you freeze when writing, start with one of these and complete it.

Getting started

I began with the simplest case, where n = ... Throughout, I assume that ... My first idea was to ..., because ...

When something failed

This attempt failed because ... This showed me that I needed to ...

Finding a pattern

From the table, the values appear to ... I therefore conjecture that ...

Justifying

I prove this by induction on n. Base case: ... My method is complete because every case ends in ... No faster method exists, because in k steps there are only ... possible outcomes.

Being honest

I was not able to prove ..., but I believe ... because ... A limitation of my approach is ...

Stretching

If ... were changed to ..., I would expect ..., because ... With more time, I would investigate ...

3.7

3.7 How long should it be?

THE OFFICIAL ANSWER

There is no minimum and no maximum. It is worth 30%, which is two problem sheets — so spend about that much effort.

Practical guidance

Use pictures, tables and trees instead of long paragraphs wherever you can. They are clearer and faster to produce.
If your report is a wall of text with no diagrams, you are making it harder for yourself and harder to mark.
Read it once and delete every sentence that says something you already said. Repetition is the most common way reports get long without getting better.
Do not try to do everything. A smaller project finished properly beats a large one abandoned halfway.

IF YOU RUN OUT OF TIME

Finish the smaller version, and write your original bigger plan into the "further work" part of the conclusion. This is exactly what researchers do, and it is not penalised.

3.Q

Check yourself — Part 3

Q1. "My solution is optimal" means:

C is completeness, not optimality. Optimality is a claim about every possible method, so it needs a counting or impossibility argument.

Q2. When should you write the abstract?

It summarises results you don't have yet at the start. It is required, so do not skip it — just write it at the end.

Part 4 — Marks, mistakes and AI

How to avoid losing marks you did not need to lose

4.1

4.1 What earns marks, and what does not

Earns marks	Earns little or nothing
A table of small cases with your working shown	Jumping straight to a formula with no working
A failed attempt, with the reason it failed	A tidy report that hides all the struggle
A decision tree covering every case	"It works, I tried a few examples"
A proof, or a clear reasoned argument	A claim with the word "obviously" in front of it
Honest statements of what you could not do	Claiming results you did not establish
Extensions with reasoning, even unsolved	A list of extensions with no thoughts attached
Your own voice, even if imperfect	Polished text that does not sound like you

4.2

4.2 The five most common mistakes

Starting in Week 10. This task needs thinking time spread over weeks. A weekend is not enough, and it shows immediately in the writing.
Looking up the answer first. Once you have read the solution, you cannot un-read it — and the marks are for your investigation, which you have just thrown away.
Only doing the original case. The 9-coin case, or the 3-disc case, is the starting point. Generalising is where most of the marks are.
Deleting the messy parts. Your dead ends are evidence of reasoning. Clean them up, do not remove them.
Never asking anything. You are explicitly allowed to discuss this with classmates and staff, in class and on Padlet. Students who ask questions write better reports.

MISTAKE ZERO

Skipping the Week 9 proposal because it is not graded. It is compulsory, and it is your one chance to find out you are heading the wrong way while you still have time to turn.

4.3

4.3 Using AI — the actual rules

You are not banned from using AI, and you will not lose marks for using it. But if you use it, you must declare it fully. Failing to declare it can count as academic misconduct.

YOU MUST STATE

Which software you used
The exact prompts you gave it
The output you got back
How you changed and used that output

YOU MUST ALSO EVALUATE

Why you used it for that task
How useful and reliable it was, and its problems
How it supported your own thinking

A REAL WARNING FROM YOUR LECTURER

In 2024, ChatGPT consistently got the forged coin problem wrong. In 2025 it reached a correct answer, but with a badly argued and needlessly complicated explanation. AI is unreliable on exactly this kind of puzzle — and the argument quality is precisely what is being marked.

4.4

4.4 What a declaration looks like

Put this in an appendix. Copy the shape, fill in your own truth.

AI USE DECLARATION

Software:  [name and version, e.g. ChatGPT, GPT-4, October 2025]

Prompt 1:  "Check the grammar and clarity of the following paragraph: [...]"
Output 1:  It rewrote the paragraph and shortened two sentences.
Used how:  I accepted two wording changes and rejected one that changed
           my meaning. The mathematical content is unchanged.
Why:       English is not my first language and I wanted the writing clearer.
Evaluation: Useful for wording. I did not use it for the mathematics, because
           the reasoning is the part I am being assessed on, and because it
           has a known record of getting this problem wrong.

GOOD JUDGEMENT

Sensible uses: checking grammar, tidying wording, explaining a term you met in Rosen. Poor uses: asking it to solve your problem, or to write your analysis. You would be handing over the exact part that earns the marks.

4.Q

Check yourself — Part 4

Q1. You used AI to fix your grammar. What must you do?

All AI use must be declared, however small. Declaring it costs you nothing; not declaring it risks a misconduct case.

Q2. The Week 9 proposal is ungraded. So you can skip it?

Ungraded is not the same as optional. It exists so you can be redirected before it is too late.

Part 5 — Your plan

What to do, week by week

5.1

5.1 The timeline

Time is set aside in tutorials and seminars in Weeks 6–10 to work on this and to ask questions. Use it — it is the cheapest help you will ever get.

CONFIRM YOUR DATES

Always check LearnJCU for the official deadlines and submission process before you rely on this diagram.

5.2

5.2 Do these three things this week

Choose your problem, and physically play with it for thirty minutes.
Nine coins or nine identical objects. Or three books of different sizes. Real objects, not just thinking.
Build the smallest-cases table.
Coins: what happens with 2 coins? 3? 4? Hanoi: 1 disc? 2 discs? 3? Write the answers in a table, in order.
Find one other person doing the same problem, and talk to them for ten minutes.
In class, or on Padlet. Ask them what they noticed. Tell them what confused you.

THAT IS IT

Do not try to plan the whole project today. These three things will take you about an hour, and after them you will know far more than you do now.

5.3

5.3 The Week 9 proposal — what to hand in

Roughly one page. It is not marked, so do not polish it. Answer these five questions:

1. Which problem am I doing?

2. What have I worked out so far?
   (Include your small-cases table, even if it is messy.)

3. What is my current conjecture or method?
   (A guess is fine here. Say it is a guess.)

4. What am I planning to do next?
   (Which extension am I heading towards?)

5. What am I stuck on, or unsure about?
   (This is the most useful part. Be specific.)

GET THE MOST FROM IT

Question 5 is where you get real value. Being vague — "I'm a bit stuck" — gets you vague help. "I can prove my method works but I have no idea how to show nothing faster exists" gets you exactly the help you need.

5.4

5.4 Final submission checklist

All seven sections are present, with headings
My assumptions are stated near the start, and I have checked whether I used them
My small cases are shown with working, not just answers
At least one failed attempt is included, with the reason it failed
My method is written clearly enough for a classmate to follow unaided
I have said whether my solution is complete, and why
I have said whether my solution is optimal, and why — or honestly why I could not show it
I have at least one extension with reasoning about what I expect
My conclusion lists questions I would pursue with more time
References are listed, and every one is cited in the text
My AI declaration is included (or I genuinely used none)
I have read it once and deleted repeated sentences
I have done a test submission and checked the formatting survived

5.5

5.5 Where to get help

Tutorials and seminars	Time is set aside in Weeks 6–10 specifically for this project. Bring your table and your stuck questions.
Your classmates	You are allowed and encouraged to discuss the problem as much as you like. Only the final writing must be yours alone.
Padlet	Post questions, and answer someone else's. Explaining something to another person is the fastest way to find the gaps in your own understanding.
Your lecturer	Ask. Especially about probability and expected cost if you head that way — that help was explicitly offered.
Rosen	Section 8.1, Example 2 (p. 529) is directly relevant to the Tower of Hanoi.

FINALLY

These are recreational puzzles. The best way in is to be curious, try things, talk to people, and keep asking "what would happen if...?". If you are enjoying it, you are doing it right.