-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathimo2025p6viz.html
More file actions
427 lines (423 loc) · 16.8 KB
/
Copy pathimo2025p6viz.html
File metadata and controls
427 lines (423 loc) · 16.8 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<title>IMO 2025 Problem 6 Visualization (Extended)</title>
<meta name="viewport" content="width=device-width, initial-scale=1" />
<!--
Coded with ❤️ by ChatGPT Agent
Tiling for every k ≥ 2 computed algorithmically.
The uncovered cells are placed in a shifting pattern, the large k×k blocks are positioned
between these holes, and the remaining squares are partitioned into long horizontal
and vertical stripes. This yields exactly k² + 2k − 3 tiles, in accordance with the
formula below. The exploration stops at k = 6 to ensure clarity and performance.
The minimum number of rectangular tiles needed to cover an n×n grid so that
each row and column contains exactly one uncovered unit square is given by
T(n) = n + 2⌊√n⌋ − 3. When n is a perfect square, n = k², this simplifies to
T(n) = k² + 2k − 3. For k = 5, n = 25 and T(n) = 32.
-->
<style>
/* Basic reset and typography */
body {
margin: 0;
padding: 0;
font-family: Arial, sans-serif;
background: #f5f7fa;
color: #333;
line-height: 1.5;
}
h1 {
margin: 0;
margin-bottom: 0.5em;
font-size: 2em;
font-weight: 600;
color: #2c3e50;
}
p {
margin-bottom: 1em;
}
.container {
max-width: 900px;
margin: 2em auto;
background: #ffffff;
padding: 1.5em;
border-radius: 8px;
box-shadow: 0 2px 8px rgba(0, 0, 0, 0.1);
overflow: hidden;
position: relative;
}
.header-image {
width: 100%;
height: 160px;
object-fit: cover;
object-position: center;
display: block;
margin: -1.5em -1.5em 1em -1.5em;
}
.controls {
display: flex;
flex-wrap: wrap;
align-items: center;
gap: 0.5em;
margin-top: 1em;
margin-bottom: 1em;
}
.controls label {
margin-right: 0.5em;
font-weight: 500;
white-space: nowrap;
}
.controls input[type='range'] {
flex: 1;
min-width: 120px;
-webkit-appearance: none;
height: 6px;
border-radius: 3px;
background: #dfe6ed;
outline: none;
}
.controls input[type='range']::-webkit-slider-thumb {
-webkit-appearance: none;
appearance: none;
width: 16px;
height: 16px;
border-radius: 50%;
background: #1f78b4;
cursor: pointer;
box-shadow: 0 0 2px rgba(0, 0, 0, 0.3);
}
.controls input[type='range']::-moz-range-thumb {
width: 16px;
height: 16px;
border-radius: 50%;
background: #1f78b4;
cursor: pointer;
box-shadow: 0 0 2px rgba(0, 0, 0, 0.3);
}
#kValue {
font-weight: 600;
margin-left: 0.5em;
color: #1f78b4;
}
#grid {
display: inline-block;
border: 1px solid #ccc;
border-radius: 4px;
margin-top: 1em;
margin-left: auto;
margin-right: auto;
overflow-x: auto;
max-width: 100%;
box-shadow: 0 1px 4px rgba(0, 0, 0, 0.08);
}
.cell {
width: 20px;
height: 20px;
box-sizing: border-box;
border: 1px solid #f0f0f0;
display: inline-block;
transition: background-color 0.3s ease;
}
.legend {
margin-top: 1em;
font-size: 0.9em;
}
.legend div {
margin-bottom: 0.3em;
display: flex;
align-items: center;
gap: 0.5em;
}
.info {
margin-top: 2em;
max-width: 100%;
}
#tileCount {
font-weight: 600;
color: #1f78b4;
margin-top: 0.5em;
font-size: 1.1em;
}
@media (max-width: 600px) {
h1 {
font-size: 1.6em;
}
.container {
margin: 1em auto;
padding: 1em;
}
.controls {
flex-direction: column;
align-items: flex-start;
}
.controls label {
margin-bottom: 0.3em;
}
.controls input[type='range'] {
width: 100%;
}
.info {
font-size: 14px;
}
}
</style>
</head>
<body>
<div class="container">
<!-- Decorative header image. See imo_header.png in the same directory. -->
<img src="imo_header.png" alt="" class="header-image" />
<h1>IMO 2025 Problem 6 Visualization</h1>
<p>Consider a 2025 × 2025 grid of unit squares. Matlida wishes to place on the grid some rectangular tiles, possibly of different sizes, such that each side of every tile lies on a grid line and every unit square is covered by at most one tile. Determine the minimum number of tiles Matlida needs to place so that each row and each column of the grid has exactly one unit square that is not covered by any tile.</p>
<p>This visualization helps you explore the solution. The problem asks for the minimum number of rectangular tiles needed to cover an n×n grid so that every row and column has exactly one uncovered unit square. You can explore values of k up to 6 (recall n = k², so n = 36 corresponds to k = 6). For n = 2025, k = 45.</p>
<div class="controls">
<label for="kInput">Choose the block size k (where n = k<sup>2</sup>):</label>
<!-- Allow k up to 6. Minimum 2 shows the smallest nontrivial tiling; values above 6 are not displayed in this version. -->
<input id="kInput" type="range" min="2" max="6" value="2" step="1" oninput="updateGrid()" />
<span id="kValue">2</span>
</div>
<div id="grid"></div>
<div class="legend">
<div><span style="display:inline-block;width:18px;height:18px;background:#ffffff;border:1px solid #333;margin-right:0.5em;"></span> Uncovered cell (one per row and column)</div>
</div>
<div class="info">
<p>The minimum number of tiles needed for an n×n grid is given by<br />
T(n) = n + 2 floor(√n) − 3.<br />
When n is a perfect square, n = k², this simplifies to T(n) = k² + 2k − 3. The formula is displayed below for the chosen k.</p>
<p id="tileCount"></p>
<p>This visualiser focuses on the case where n is a perfect square (choose k using the slider). The structures you see here generalise to larger grids.</p>
</div>
</div>
<script>
// Predefined colour palette for off‑diagonal blocks and stripes.
const palette = [
'#a6cee3', '#b2df8a', '#fb9a99', '#fdbf6f', '#cab2d6', '#ffff99',
'#1f78b4', '#33a02c', '#e31a1c', '#ff7f00', '#6a3d9a'
];
function updateGrid() {
const kInput = document.getElementById('kInput');
const k = parseInt(kInput.value);
document.getElementById('kValue').textContent = k;
const n = k * k;
const gridDiv = document.getElementById('grid');
gridDiv.innerHTML = '';
// For small k (≤6) draw every unit cell and compute an explicit tiling.
// For larger k the grid is compressed to a k×k representation to
// maintain performance. This threshold prevents the heavier tiling
// algorithm from running for k ≥ 7.
const blockThreshold = 6;
let cellSize;
if (k > blockThreshold) {
cellSize = Math.max(4, Math.floor(800 / k));
} else {
cellSize = 20;
}
// Set grid width: for small k use n cells per row; for large k compress each block.
gridDiv.style.width = (cellSize * (k > blockThreshold ? k : n)) + 'px';
let tileCount;
// The general algorithm below computes the tiling for all k≥2.
const customTilings = {};
if (customTilings[k]) {
const tiling = customTilings[k];
tileCount = tiling.tileCount;
document.getElementById('tileCount').innerHTML = `For k = ${k} (n = ${n}), the minimum number of tiles is <strong>${tileCount}</strong> (= k² + 2k − 3).`;
const holes = new Set(tiling.holes);
// Determine how many of the first colours should be reserved for block tiles. (k−1)² blocks for k ≥ 2.)
const blockTileCountLookup = {2: 1, 3: 4, 4: 9};
const blockTileCount = blockTileCountLookup[k] || 0;
const tileColours = [];
// Colours for stripe tiles start after the block colours in the palette.
const stripePalette = palette.slice(blockTileCount % palette.length);
for (let i = 0; i < tiling.tileCount; i++) {
if (i < blockTileCount) {
tileColours[i] = palette[i % palette.length];
} else {
if (stripePalette.length > 0) {
tileColours[i] = stripePalette[(i - blockTileCount) % stripePalette.length];
} else {
tileColours[i] = palette[(i - blockTileCount) % palette.length];
}
}
}
for (let r = 0; r < tiling.n; r++) {
for (let c = 0; c < tiling.n; c++) {
const cell = document.createElement('div');
cell.className = 'cell';
cell.style.width = cellSize + 'px';
cell.style.height = cellSize + 'px';
const key = `${r},${c}`;
if (holes.has(key)) {
cell.style.background = '#ffffff';
cell.style.border = '1px solid #333';
} else {
const tileIndex = tiling.mapping[key];
cell.style.background = tileColours[tileIndex % tileColours.length];
}
gridDiv.appendChild(cell);
}
}
return;
}
// For moderate k we compute an explicit tiling based on the shifting hole pattern and a
// family of (k − 1)×(k − 1) big k×k blocks together with 4(k − 1) long
// stripes. This arrangement matches the combinatorial structure used in
// the official solution: the uncovered cells are placed one per row and
// column in a shifted (non‑diagonal) pattern, the k×k squares are placed
// between the holes, and the remaining cells are partitioned into
// horizontal and vertical stripes. The total number of tiles is
// (k − 1)² + 4(k − 1) = k² + 2k − 3.
tileCount = n + 2 * k - 3;
document.getElementById('tileCount').innerHTML = `For k = ${k} (n = ${n}), the minimum number of tiles is <strong>${tileCount}</strong> (= k² + 2k − 3).`;
// If k is very large, compress each k×k block into a single cell to
// maintain performance and provide a miniature view.
if (k > blockThreshold) {
// Compute the column of the uncovered cell for each row for the miniature.
const holeColMini = new Array(n);
for (let r = 0; r < n; r++) {
const j = Math.floor(r / k);
const g = r % k;
holeColMini[r] = k * g + (k - 1 - j);
}
for (let br = 0; br < k; br++) {
for (let bc = 0; bc < k; bc++) {
const cell = document.createElement('div');
cell.className = 'cell';
cell.style.width = cellSize + 'px';
cell.style.height = cellSize + 'px';
// Use grey for the diagonal blocks and palette colours for off‑diagonal blocks.
if (br === bc) {
cell.style.background = '#dddddd';
const mini = document.createElement('div');
mini.style.position = 'absolute';
mini.style.width = Math.max(2, Math.floor(cellSize / 4)) + 'px';
mini.style.height = Math.max(2, Math.floor(cellSize / 4)) + 'px';
mini.style.background = '#ffffff';
mini.style.border = '1px solid #333';
mini.style.top = (cellSize - Math.floor(cellSize / 4)) / 2 + 'px';
mini.style.left = (cellSize - Math.floor(cellSize / 4)) / 2 + 'px';
cell.appendChild(mini);
} else {
const colorIndex = (br * k + bc) % palette.length;
cell.style.background = palette[colorIndex];
}
gridDiv.appendChild(cell);
}
}
return;
}
// For moderate k draw every unit cell and compute the tiling explicitly.
// Precompute the column of the uncovered cell for each row.
const holeCol = new Array(n);
for (let r = 0; r < n; r++) {
const j = Math.floor(r / k);
const g = r % k;
holeCol[r] = k * g + (k - 1 - j);
}
// Build a mapping from cell coordinates to tile indices. First allocate
// indices for the big k×k blocks: there are (k − 1)² such blocks.
const mapping = {};
let tileIndexCounter = 0;
// Place the big squares (between the holes) indexed 0 to (k−1)^2−1.
for (let j = 0; j < k - 1; j++) {
for (let g = 1; g < k; g++) {
const rStart = j * k + g;
const cStart = k * (g - 1) + (k - 1 - j);
for (let r = rStart; r < rStart + k; r++) {
for (let c = cStart; c < cStart + k; c++) {
mapping[`${r},${c}`] = tileIndexCounter;
}
}
tileIndexCounter++;
}
}
// Place the long stripes: for each j from 0 to k−2 we create four stripes.
const blockCount = (k - 1) * (k - 1);
for (let j = 0; j < k - 1; j++) {
const length = k * (k - 1 - j);
// Left vertical stripe at column j, rows 0..length-1.
let tIndex = blockCount + j * 4;
for (let r = 0; r < length; r++) {
// Skip holes and big squares (mapping[r,c] already defined).
const key = `${r},${j}`;
if (mapping[key] === undefined && holeCol[r] !== j) {
mapping[key] = tIndex;
}
}
// Top horizontal stripe at row j, columns (j+1)*k .. (j+1)*k + length - 1.
tIndex = blockCount + j * 4 + 1;
for (let c = (j + 1) * k; c < (j + 1) * k + length; c++) {
const key = `${j},${c}`;
// Skip if hole or already in a block.
if (mapping[key] === undefined && holeCol[j] !== c) {
mapping[key] = tIndex;
}
}
// Right vertical stripe at column n - 1 - j, rows (j+1)*k .. (j+1)*k + length - 1.
tIndex = blockCount + j * 4 + 2;
for (let r = (j + 1) * k; r < (j + 1) * k + length; r++) {
const key = `${r},${n - 1 - j}`;
if (mapping[key] === undefined && holeCol[r] !== (n - 1 - j)) {
mapping[key] = tIndex;
}
}
// Bottom horizontal stripe at row n - 1 - j, columns 0 .. length - 1.
tIndex = blockCount + j * 4 + 3;
for (let c = 0; c < length; c++) {
const key = `${n - 1 - j},${c}`;
if (mapping[key] === undefined && holeCol[n - 1 - j] !== c) {
mapping[key] = tIndex;
}
}
}
// Determine how many of the first colours should be reserved for block tiles.
// Ensure that block tiles use distinct colours.
// Number of big square tiles is (k−1)². We provide explicit entries
// for small k but fall back to this formula for larger k.
const blockTileCountLookup = {2: 1, 3: 4, 4: 9, 5: 16};
const blockTileCount = blockTileCountLookup[k] || ((k - 1) * (k - 1));
const totalTiles = (k - 1) * (k - 1) + 4 * (k - 1);
// Construct the tile colour array: assign the first blockTileCount colours
// from the palette to the square tiles and then cycle through the palette
// for the remaining stripe tiles.
const tileColours = [];
// Create a stripe palette starting after the block colours in the palette.
const stripePalette = palette.slice(blockTileCount % palette.length);
for (let i = 0; i < totalTiles; i++) {
if (i < blockTileCount) {
tileColours[i] = palette[i % palette.length];
} else {
if (stripePalette.length > 0) {
tileColours[i] = stripePalette[(i - blockTileCount) % stripePalette.length];
} else {
tileColours[i] = palette[(i - blockTileCount) % palette.length];
}
}
}
// Now draw every unit cell according to the mapping. Uncovered cells are
// white with a border. Cells in big blocks and stripes use the
// appropriate colour from tileColours.
for (let r = 0; r < n; r++) {
for (let c = 0; c < n; c++) {
const cell = document.createElement('div');
cell.className = 'cell';
cell.style.width = cellSize + 'px';
cell.style.height = cellSize + 'px';
if (c === holeCol[r]) {
// Uncovered cell.
cell.style.background = '#ffffff';
cell.style.border = '1px solid #333';
} else {
const idx = mapping[`${r},${c}`];
// If for some reason mapping is undefined (should not happen), fallback colour.
const colour = tileColours[idx % tileColours.length] || palette[(r + c) % palette.length];
cell.style.background = colour;
}
gridDiv.appendChild(cell);
}
}
return;
}
// Initialise the grid on page load.
window.onload = updateGrid;
</script>
</body>
</html>